记录leetcode网站面试经典150题的思路和心得。仅含中等难度以上的题目或值得记录的。

数组/字符串

88.合并两个有序数组

归并排序合并过程。

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    vector<int> b;
    b.clear();
    int i = 0, j = 0;
    for( ; i < m || j < n;) {
        if((j == n) || ( i < m && nums1[i] <= nums2[j])) {
            b.push_back(nums1[i++]);
        }
        else b.push_back(nums2[j++]);
    }
    
    for(i = 0; i < n+m; i++) nums1[i] = b[i];
}

26.删除有序数组中的重复项

按照条件筛选元素，条件为不与前驱相同的元素。

用覆盖的思路处理即可。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(nums[i] != nums[i-1]) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
};

80.删除有序数组中的重复项 II

在上一题基础上加一个前驱的前驱即可。

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        int k = 2;
        for(int i = 2; i < nums.size(); i++) {
            if(nums[i] != nums[k-1] || nums[i] != nums[k-2]) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
};

169.多数元素

求众数方法。计数，相同则加，不同则减，减到0更换预选数。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ans = nums[0];
        int k = 1;
        for(int i = 1; i < nums.size(); i++) {
            if(ans == nums[i]) k++;
            else k--;
            if(!k) {
                k = 1;
                ans = nums[i];
            }
        }
        return ans;
    }
};

189.轮转数组

前后调换，三次逆转即可。

121.买卖股票的最佳时机

维护一个前缀最小值，动态更新答案。

122.买卖股票的最佳时机 II

贪心。记录折现转折点，在最低点买入最高点卖出即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n <= 1) return 0;
        int l = prices[0], r = prices[0], ans = 0;
        for(int i = 1; i < n; i++) {
            if(prices[i] >= prices[i-1]) {
                r = prices[i];
            }
            else {
                ans += r-l;
                l = r = prices[i];
            }
        }
        ans += r-l;
        return ans;
    }
};

55.跳跃游戏

维护一个能跳到的最大范围即可。

45.跳跃游戏 II

正向DP，用当前值更新后面的值即可。

274.H 指数

枚举即可。显然答案具有单调性，可以用二分进一步优化。

380.O(1) 时间插入、删除和获取随机元素

数组+哈希表双向绑定。删除时尾部交换删除来做到O(1)删除。

class RandomizedSet {
public:
    vector<vector<int> > vec;
    vector<int> value;
    RandomizedSet() {
        value.clear();
        for(int i = 0; i <= 10007; i++) {
            vector<int> u;
            u.clear();
            vec.push_back(u);
        }
    }
    
    int hash(int val) {
        return abs(val)%10007;
    }

    int indexOfVal(int val) {
        int H = hash(val);
        if(vec[H].empty() || value.empty()) return -1;
        for(int i = 0; i < vec[H].size(); i++) {
            int index = vec[H][i];
            if(index == -1) continue;
            if(value[index] == val) return index;
        }
        return -1;
    }

    bool insert(int val) {
        if(indexOfVal(val) != -1) 
            return false;
        value.push_back(val);
        int index = value.size()-1;
        int H = hash(val);
        vec[H].push_back(index);
        return true;
    }
    
    bool remove(int val) {
        int index = indexOfVal(val);
        if(index == -1) return false;
        int n = value.size();
        int last = value[n-1];

        int H = hash(last);
        for(int i = 0; i < vec[H].size(); i++) {
            if(vec[H][i] == n-1) vec[H][i] = index;
        }

        H = hash(val);
        for(int i = 0; i < vec[H].size(); i++) {
            if(vec[H][i] == index) vec[H][i] = -1;
        }

        swap(value[n-1], value[index]);
        if(n > 1) value.resize(n-1);
        else value.clear();

        return true;
    }
    
    int getRandom() {
        int n = value.size();
        int r = rand()%n;
        return value[r];
    }
};

238.除自身以外数组的乘积

求前缀乘和后缀乘即可。

134.加油站

尝试走完全程即可，失败则从失败点继续尝试。

135.分发糖果

想象成折线图的话，任何谷底（严格下降序列的终点）都一定是1，一段相同的区间两端点可以任意，区间内部也一定是1.

由于谷底一定是1，则在谷底向两边上升一直加1即可。

为了方便编程，可以在上升的时候不断加一，在下降过程中不断减一，如果遇到谷底，且当前值小于1，则把整段下降序列向上抬一下即可。

注意特殊情况：

上抬时可以把峰值更新小，最后特殊处理一下即可。
当遇到连续相同区间时，也需要把左端点抬一下。
最后也要尝试抬一下。

class Solution {
public:
    void lift(vector<int>& b, vector<int>& ratings, int p) {
        int x = 1;
        b[p] = 1;
        while (p >= 1 && ratings[p] < ratings[p - 1]) {
            b[p - 1] = x + 1;
            x++;
            p--;
        }
    }
    int candy(vector<int>& ratings) {
        vector<int> b;
        b.push_back(1);
        int n = ratings.size();
        if (n <= 1)
            return 1;
        int x = 1;
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                if (x < 1) {
                    lift(b, ratings, i-1);
                    x = 1;
                }
                x++;
                b.push_back(x);
            } else if (ratings[i] == ratings[i - 1]) {
                if (x < 1) {
                    lift(b, ratings, i-1);
                }
                x = 1;
                b.push_back(1);
            } else {
                if (x > 1)
                    x = 1, b.push_back(1);
                else
                    x--, b.push_back(x);
            }
        }
        if (x < 1) {
            lift(b, ratings, n-1);
        }
        for (int i = 1; i < n - 1; i++) {
            if (ratings[i] > ratings[i - 1] && ratings[i] > ratings[i + 1]) {
                b[i] = max(b[i - 1], b[i + 1]) + 1;
            }
        }
        int sum = 0;
        for (int i = 0; i < n; i++)
            sum += b[i];
        return sum;
    }
};

42.接雨水

单调栈。维护一个凸形即可。

class Solution {
public:
    int trap(vector<int>& height) {
        int n = height.size();
        stack<pair<int, int> >st;
        int sum = 0;
        for(int i = 0; i < n; i++) {
            int h = height[i];
            if(st.empty() || h < st.top().first) {
                st.push(make_pair(h, i));
            }
            else if(h == st.top().first) {
                st.top().second = i;
            }
            else {
                while(st.size() > 1 && h > st.top().first) {
                    int th = st.top().first, j = st.top().second;
                    st.pop();
                    if(th >= st.top().first) break;
                    sum += (i-st.top().second-1) * (min(st.top().first, h)-th);
                }
                if(h == st.top().first) st.top().second = i;
                else st.push(make_pair(h, i));
            }
        }
        
        return sum;
    }
};

58.最后一个单词的长度

使用python一行代码

class Solution(object):
    def lengthOfLastWord(self, s):
        """
        :type s: str
        :rtype: int
        """
        return len(s.strip().split(' ')[-1])

14.最长公共前缀

trie树模板

class Solution {
public:
    int ch[40005][26];
    int size[40005];
    int cnt[40005];
    vector<int> vec[40006];
    int num = 0;
    int newNode() {
        return ++num;
    }
    void insert(string s) {
        int u = 0;
        int n = s.size();
        for(int i = 0; i < n; i++) {
            int c = s[i]-'a';
            if(!ch[u][c]) {
                int v = newNode();
                ch[u][c] = v;
                size[u]++;
                vec[u].push_back(v);
            }
            cnt[u]++;
            u = ch[u][c];
        }
    }

    string longestCommonPrefix(vector<string>& strs) {
        memset(ch, 0, sizeof(ch));
        int n = strs.size();
        for(int i = 0; i < n; i++) insert(strs[i]);

        int u = 0, len = 0;
        while(size[u] == 1 && cnt[u] == n) {
            u = vec[u][0];
            len++;            
        }

        string ans = "";
        for(int i = 0; i < len; i++) ans += strs[0][i];
        
        return ans;
    }
};

151.反转字符串中的单词

使用python即可。

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        lst = s.strip().split(' ')
        n = len(lst)
        ans = ''
        for i in reversed(lst):
            if(i.strip() == ''):
                continue
            ans = ans + ' ' + i.strip()
        return ans.strip()

双指针

11.盛最多水的容器

水位一定与某个柱子相等，且另一个柱子大于当前柱子。

将柱子从高到低排序，枚举每个柱子的高度为水位线，让其与比他更高的柱子组合。选择距离最远的即可。

可以排序后维护一个前缀最大值与最小值，来快速求最远的柱子。

class Solution {
public:
    struct Node{
        int val, idx;
        Node(int val, int idx):val(val), idx(idx){}
        bool operator < (const Node &b) const{ return val > b.val; }
    };
    int abs(int x) {
        return x > 0 ? x : x*-1;
    }
    int maxArea(vector<int>& height) {
        int n = height.size();
        vector<Node> nodes;
        for(int i = 0; i < n; i++) {
            nodes.push_back(Node(height[i], i));
        }
        sort(nodes.begin(), nodes.end());
        vector<int> preMax, preMin;
        preMax.push_back(nodes[0].idx);
        preMin.push_back(nodes[0].idx);
        for(int i = 1; i < n; i++) {
            preMax.push_back(max(preMax[i-1], nodes[i].idx));
            preMin.push_back(min(preMin[i-1], nodes[i].idx));
        }

        int ans = 0;
        for(int i = n-1; i >= 1; i--) {
            int idx = nodes[i].idx;
            int dst = max(abs(idx-preMax[i-1]), abs(idx-preMin[i-1]));
            ans = max(ans, nodes[i].val * dst);
        }
        return ans;
    }
};

15.三数之和

排序后，枚举中间点k，使用双指针i，j扫描即可。

注意以下特殊处理：

每个相同的数最多保留3个
对结果进行去重

滑动窗口

209.长度最小的子数组

二分长度，用滑动窗口判断即可。

3.无重复长度的最长子串

双指针l, r异步扫描。 r 遇见重复字符时，向前调整l。在这个过程中动态更新答案。

30.串联所有单词的子串

将单词分组，然后每组用滑动窗口进行统计。

使用队列来存储窗口中的单词序号，来动态更新。

注意两种失败情况，一种为重复单词出现，一种为查找失败，处理策略不同。

class Solution {
public:
    int b[5005];
    int check(string s, vector<string>& words) {
        int n = words.size();
        for (int i = 0; i < n; i++) {
            if (!b[i] && s == words[i]) {
                b[i] = 1;
                return i;
            }
        }
        for (int i = 0; i < n; i++) {
            if (s == words[i])
                return -2;
        }
        return -1;
    }

    vector<int> findSubstring(string s, vector<string>& words) {
        int n = s.size();
        vector<int> ans;
        if (n == 0 || words.size() == 0)
            return ans;
        int m = words[0].size();
        queue<int> que;
        for (int i = 0; i < m; i++) {
            int p = i, l = i;
            memset(b, 0, sizeof(b));
            while(que.size()) que.pop();
            while (p < n) {
                string ss = s.substr(p, m);
                int idx = check(ss, words);
                if (idx == -2) {
                    int h = que.front();
                    que.pop();
                    b[h] = 0;
                    
                    l += m;
                    continue;
                }
                if(idx == -1) {
                    memset(b, 0, sizeof(b));
                    while(!que.empty()) que.pop();
                    p += m;
                    l = p;
                   
                    continue;
                }
                b[idx] = 1;
                p += m;
                que.push(idx);
                if (que.size() == words.size()) {
                    ans.push_back(l);
                    b[que.front()] = 0;
                    que.pop();
                    
                    l += m;
                }
            }
        }

        return ans;
    }
};

76.最小覆盖子串

双指针动态更新次数即可。

class Solution {
public:
    int ch[305];
    int b[305];
    string minWindow(string s, string t) {
        int n = s.size(), m = t.size();
        int K = 0;
        for (int i = 0; i < m; i++){
            ch[t[i]]++;
            if(ch[t[i]] == 1) K++;
        }
            
        int k = 0;
        int l = 0, r = 0;
        string ans;
        int minL = 0x3f3f3f3f;
        while (!ch[s[r]] && r < n) {
            l++;
            r++;
        }
        if (r == n)
            return ans;

        while (r < n) {
            while (r < n) {
                b[s[r]]++;
                if(b[s[r]] == ch[s[r]]) k++;
                if(k == K) {
                    while(!ch[s[l]] || b[s[l]] > ch[s[l]]) {
                        b[s[l]]--;
                        l++;
                    }
                    if(r-l+1 < minL) {
                        minL = r-l+1;
                        ans = s.substr(l, minL);
                    }
                    r++;
                    break;
                }
                r++;
            }
            b[s[l]]--;
            l++;
            k--;
        }

        return ans;
    }
};

矩阵

36.有效的数独

矩阵下标的枚举

54.螺旋矩阵

蛇形填数，注意边界。

48.旋转图像

每个格子都能计算出对应的变换，四个一组枚举即可。

注意边界。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for(int i = 0; i < n/2; i++) {
            for(int j = i; j < n-i-1; j++) {
                int k = matrix[i][j];
                matrix[i][j] = matrix[n-j-1][i];
                matrix[n-j-1][i] = matrix[n-i-1][n-j-1];
                matrix[n-i-1][n-j-1] = matrix[j][n-i-1];
                matrix[j][n-i-1] = k;
            }
        }
    }
};

73.矩阵置零

记录0的坐标依次处理即可。

289.生命游戏

同上。

哈希表

205.同构字符串

注意s到t，而且单一映射。

49.字母异位词分组

异位词排序后相同，用map记录即可。

128.最长连续序列

哈希表+并查集。注意去重。

class Solution {
public:
    int f[100005];
    int S[100005];
    vector<vector<int>> ht;
    int n;
    int findF(int x) {
        return x == f[x] ? x : f[x] = findF(f[x]);
    }

    void link(int x, int y) {
        int fx = findF(x), fy = findF(y);
        f[fx] = fy;
    }

    int findIdx(int x, vector<int>& nums) {
        int h = abs(x%n);
        for(int i = 0; i < ht[h].size(); i++) {
            if(nums[ht[h][i]] == x) return ht[h][i];
        }
        return -1;
    }

    int longestConsecutive(vector<int>& nums) {
        n = nums.size();
        for(int i = 0; i < n; i++) f[i] = i;
        
        for(int i = 0; i < n; i++) {
            vector<int> v;
            ht.push_back(v);
        }
        for(int i = 0; i < n; i++) {
            if(findIdx(nums[i], nums) != -1) {
                f[i] = -1;
                continue;
            }
            int h = abs(nums[i] % n);
            ht[h].push_back(i);
        }
        for(int i = 0; i < n; i++) {
            if(f[i] == -1) continue;
            int x = nums[i];
            int idx = findIdx(x-1, nums);
            if(idx != -1) link(i, idx);
            idx = findIdx(x+1, nums);
            if(idx != -1) link(i, idx);
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(f[i] == -1) continue;
            int x = findF(i);
            S[x]++;
            ans = max(ans, S[x]);
        }

        return ans;
    }
};

区间

56.合并区间

排序后逐个合并即可。

57.插入区间

注意一些特殊情况。

452.区间最少点覆盖

贪心的区间最少点覆盖模版题。

栈

71.简化路径

分词并用栈处理即可，注意特殊条件较多。

class Solution {
public:
    vector<string> split(string s) {
        string x;
        int n = s.size();
        vector<string> vec;
        for (int i = 0; i < n; i++) {
            if (s[i] == '/') {
                if (!x.empty())
                    vec.push_back(x);
                x.clear();
                continue;
            }
            x += s[i];
        }
        if (!x.empty())
            vec.push_back(x);
        return vec;
    }

    string simplifyPath(string path) {
        vector<string> vec = split(path);
        stack<string> st;
        int n = vec.size();
        for (int i = 0; i < n; i++) {
            if (vec[i] == ".." && !st.empty()) {
                st.pop();
                continue;
            }
            if (vec[i] != ".." && vec[i] != ".")
                st.push(vec[i]);
        }
        vec.clear();
        while (!st.empty()) {
            vec.push_back(st.top());
            st.pop();
        }
        string s;
        n = vec.size();
        for (int i = n - 1; i >= 0; i--) {
            s += '/';
            s += vec[i];
        }
        if (s.empty())
            s = "/";
        return s;
    }
};

155.最小栈

维护一个前缀最小值即可。

150.逆波兰表达式求值

模板题。

链表

138.随机链表的复制

先把链复制，再复制随机指针即可。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyNode(Node* u) {
        Node* v = new Node(0);
        v->val = u->val;
        return v;
    }
    int findNodeIdx(Node* h, Node* u) {
        Node* p = h;
        int idx = 0;
        while(p != NULL) {
            if(p == u) return idx;
            p = p->next;
            idx++;
        }
        if(p == NULL) return -1;
        return idx;
    }

    Node* findNode(Node* h, int idx) {
        if(idx == -1) return NULL;
        Node* p = h;
        while(idx--) p = p->next;
        return p;
    }

    Node* copyRandomList(Node* head) {
        if(head == NULL) return NULL;
        Node* nhead = copyNode(head);
        Node* p = head;
        Node* q = nhead;
        while(p->next != NULL) {
            Node* _new = copyNode(p->next);
            q->next = _new;
            q = q->next;
            p = p->next;
        }
        q = nhead, p = head;
        while(q != NULL) {
            int idx = findNodeIdx(head, p->random);
            Node* r = findNode(nhead, idx);
            q->random = r;
            q = q->next;
            p = p->next;
        }
        return nhead;
    }
};

92.反转链表2

把节点去除，然后再头插进去。

19.删除链表的倒数第 N 个结点

计算出正数第n个节点，然后找出第n-1个节点删除即可。注意加入虚拟头结点来简化判断逻辑。

82.删除排序链表中的重复元素 II

注意把次数大于1的数全部删掉，而不是所有数只保留一个。

先统计次数，然后删节点即可。

61.旋转链表

把值取出来旋转再放回即可。

86.分割链表

把小于x的值取出来放到另一条链中，然后在剩余链的第一个大于等于x的节点前插入该链。

二叉树

105/106.从（前序与中序）（中序与后序）遍历序列构造二叉树

分割左子树和右子树递归即可。

117.填充每个节点的下一个右侧节点指针 II

层次遍历即可。

114.二叉树展开为链表

递归操作，先把左子树做成链，返回链尾，然后拼接再去处理右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* dfs(TreeNode* u) {
        if(u == NULL) return NULL;
        if(u->left == NULL && u->right == NULL) return u;
        if(u->left == NULL) return dfs(u->right);
        if(u->right == NULL) {
            u->right = u->left;
            u->left = NULL;
            return dfs(u->right);
        }
        TreeNode* l = dfs(u->left);
        l->right = u->right;
        u->right = u->left;
        u->left = NULL;
        return dfs(l->right);
    }
    void flatten(TreeNode* root) {
        dfs(root);
    }
};

124.二叉树中的最大路径和

对于一颗树，其最大路径和有两种可能：

过根节点：根节点+左右子树最长链。
不过根节点：左右子树中的最大值。

因此对于每个节点，维护其过根节点的最长链和最大值即可。

需要注意维护最长链时，不去考虑子树中的负链，求过根节点的最大值时同理。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    map<TreeNode*, pair<int, int> > mp;
    // first: 过根最长链
    // second: 最优解
    int ans = -0x3f3f3f3f;
    void dfs(TreeNode* u) {
        if(u == NULL) return ;
        if(u->left == NULL && u->right == NULL) {
            mp[u].first = u->val;
            mp[u].second = u->val;
            ans = max(ans, u->val);
            return ;
        }

        if(u->left) dfs(u->left);
        if(u->right) dfs(u->right);
        
        int res1 = u->val, res2 = -0x3f3f3f3f;
        mp[u].first = u->val;
        if(u->left != NULL) {
            if(mp[u->left].first > 0) {
                res1 += mp[u->left].first;
                mp[u].first = max(mp[u].first, u->val + mp[u->left].first);
            }
            res2 = max(res2, mp[u->left].second);
             
        }
        if(u->right != NULL) {
            if(mp[u->right].first > 0){
                res1 += mp[u->right].first;
                mp[u].first = max(mp[u].first, u->val + mp[u->right].first);
            } 
            res2 = max(res2, mp[u->right].second);
        }

        mp[u].second = max(res1, res2);
        ans = max(ans, mp[u].second);
    }
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

236.二叉树的最近公共祖先

一个节点先向上跳，然后标记沿途节点。另一个节点跳到第一个标记节点即为最近公共祖先。

二叉树层次遍历

199.二叉树的右视图

层次遍历，取每一层最后一个。

102.二叉树的层序遍历

每一层存起来

103.二叉树的锯齿形层序遍历

和上一题相似，每隔一层反转一下结果即可。

二叉搜索树

230.二叉搜索树中第 K 小的元素

统计子树节点数，然后根据情况查找即可。

注意一些特殊条件的判断。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    map<TreeNode*, int> size;
    void dfs(TreeNode* u) {
        if(u == NULL) return;
        dfs(u->left);
        dfs(u->right);
        size[u] = 1;
        if(u->left != NULL) size[u] += size[u->left];
        if(u->right != NULL) size[u] += size[u->right];
    }

    int find(TreeNode* u, int k) {
        if(u->left != NULL){
            if(k == size[u->left]+1) return u->val;
            if(k <= size[u->left]) return find(u->left, k);
        }
        if(u->right != NULL) {
            if(k == 1) return u->val;
            int ls = 0;
            if(u->left != NULL) ls = size[u->left];
            return find(u->right, k-ls-1);
        }
        return u->val;
    }

    int kthSmallest(TreeNode* root, int k) {
        dfs(root);
        return find(root, k);
    }
};

98.验证二叉搜索树

维护子树最大值最小值即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    map<TreeNode*, pair<int, int> >mp;
    bool isValidBST(TreeNode* root) {
        TreeNode* u = root;
        if(u->left && !isValidBST(u->left)) return false;
        if(u->right && !isValidBST(u->right)) return false;
        mp[u] = make_pair(u->val, u->val);
        if(u->left == NULL && u->right == NULL) {
            return true;
        }
        
        if(u->left != NULL) {
            if(u->val <= mp[u->left].second) return false;
            mp[u].first = min(mp[u].first, mp[u->left].first);
        }
        if(u->right != NULL) {
            if(u->val >= mp[u->right].first) return false;
            mp[u].second = max(mp[u].second, mp[u->right].second);
        }
        return true;
    }
};

二分查找

33.搜索旋转排序数组

倍增寻找旋转点，之后二分。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int n = nums.size();
        int k = 0, p = 1;
        while(p) {
            if(k+p < n && nums[k+p] > nums[k]) {
                k += p;
                p <<= 1;
            }
            else p >>= 1;
        }
        k = n-1-k;
        int l = 0, r = n-1;
        int ans = -1;
        while(l <= r) {
            int mid = (l+r)/2;
            int idx = (mid-k+n)%n;
            if(nums[idx] == target) {
                ans = idx;
                break;
            }
            if(nums[idx] < target) l = mid+1;
            else r = mid-1;
        }
        return ans;
    }
};

leetcode

#leetcode

Java-多线程上一篇

鱼的个体识别-数据集处理下一篇

leetcode 面试经典150题-中等难度以上