Leetcode 高频算法题

4. 寻找两个正序数组的中位数

1. 转为求数组的第k个数的问题
2. 比较a数组的中间的那个数x，和b数组中间的那个数y。如果x > y，则可以抛弃b数组的前半部分，否则抛弃a数组的前半部分.

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }

    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
    	// 保证nums1.size() <= nums2.size()
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        if (k == 1) {
            if (nums1.size() == i) return nums2[j]; //nums1是空
            else return min(nums1[i], nums2[j]);
        }
        if (nums1.size() == i) return nums2[j + k - 1];
        //这里的si,sj是中间那个数的下一个位置
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
        	// 扔掉nums2数组的前面部分的数
            return find(nums1, i, nums2, sj, k - (sj - j));
        else
            return find(nums1, si, nums2, j, k - (si - i));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

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

lc26和这一题是差不多的，区别是26是只出现一次，本题

class Solution {
public:
    int removeDuplicates(vector<int>& a) {
        int k = 2; //对应题意中的只出现两次，根据题意可以动态改变为1次，3次都可以
        int u = 0;
        for (int x: a) if (u < k || x != a[u - k]) a[u++] = x;
        return u;
    }
};
1
2
3
4
5
6
7
8
9

42. 接雨水

class Solution {
public:
  int trap(vector<int>& height) {
        int n = height.size(), ans = 0;
        stack<int> st;
        for (int i = 0; i < n; i++) {
            // 这里>和>=都可以AC
            while (st.size() && height[i] >= height[st.top()]) {
                int k = st.top();
                st.pop();
                if (st.empty()) break;
                ans += (i - st.top() - 1) * (min(height[i], height[st.top()]) - height[k]);
            }
            st.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

45. 跳跃游戏 II

和lc55题差不多，区别是本题需要求出跳跃到n-1这个位置的最小次数.
f[i]表示到达位置i的最小次数，定义last为第一次到达位置i的时候上一步的位置。 归纳可知，从小到达遍历过程中，第一次通过x可以到达y时，y的最小步数就是到达x的最小步数+1.因此有f[i] = f[last] + 1.
时间复杂度为O(N)

class Solution {
public:
    int jump(vector<int>& a) {
        int n = a.size(), last = 0;
        vector<int> f(n);
        for (int i = 1; i < n; i++)
        {
            while (last + a[last] < i) last++;
            f[i] = f[last] + 1;
        }
        return f[n - 1];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

55. 跳跃游戏

给你一个非负整数数组，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。
使用一个整数维护当前能调到的最远的位置即可。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        for (int i = 0, k = 0; i < nums.size(); i++) {
            if (k < i) return false;
            k = max(k, i + nums[i]);
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10

75. 颜色分类

三指针处理

class Solution {
public:
    void sortColors(vector<int>& a) {
        int i = 0, j = 0, k = a.size() - 1;
        // 始终满足以下的条件
        // [0, i - 1]都是0
        // [i, j - 1]都是1
        // [k + 1, n - 1]都是2
        // 其余都是还未处理的 也就是[j, k]
        for (;j <= k;) {
            if (a[j] == 0) swap(a[i++], a[j++]);
            else if (a[j] == 2) swap(a[j], a[k--]);
            else j++;
           
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

76. 最小覆盖子串

双指针，然后用hash和cnt维护字符剩余的数量。

class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size();
        unordered_map<char, int> hash;
        // cnt表示t里一共有多少种字符，hash存储每个字符有多少个
        int cnt = 0;
        for (char c: t) {
            hash[c]++;
            if (hash[c] == 1) cnt++;
        }
        string res = "";
        // j, i表示两个指针 c表示当前区间内已经满足的字符的种类数
        for (int i = 0, j = 0, c = 0; i < n; i++) {
            if (hash[s[i]] == 1) c++; //s[i]这个字符还缺一个就够了
            hash[s[i]]--;
            while (c == cnt && hash[s[j]] < 0) hash[s[j++]]++; //移动左指针，尽可能缩小区间
            if (c == cnt && (res.empty() || res.size() > (i - j + 1))) res = s.substr(j, i - j + 1);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

116和本题类似，区别是116是完美二叉树
下面的代码可以AC这两个题目。

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if (root == nullptr) return root;
        Node* cur = root;
        // cur每一层的第一个节点
        while (cur)
        {
            auto head = new Node(-1);
            auto tail = head;
            // 用tail指针把下一层的节点都连了起来. 这些为什么可以使用 p->next遍历的原因.
            // 注意第一次的时候，第一层只有一个根节点，这里只循环一次，然后把第二层的节点横着连了起来
            for (auto p = cur; p; p = p -> next)
            {
                if (p -> left) tail = tail -> next = p -> left;
                if (p -> right) tail = tail -> next = p -> right;
            }
            // head -> next是下一层的第一个节点
            cur = head -> next;
            delete head;
        }
        return root;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

128. 最长连续序列

做法1：维护每个数字以它为左端点和右端点的最长连续长度 时间复杂度:O(N)

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res = 0;
        unordered_map<int, int> tr_left, tr_right;
        for (auto & x : nums)
        {
            int left = tr_right[x - 1];
            int right = tr_left[x + 1];
            tr_left[x - left] = max(tr_left[x - left], left + 1 + right);
            tr_right[x + right] = max(tr_right[x + right], left + 1 + right);
            res = max(res, left + 1 + right);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

做法2：枚举每一段的起点即可 时间复杂度:O(N)

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> S;
        for (auto x: nums) S.insert(x);

        int res = 0;
        for (auto x: nums) {
        	// 保证枚举的是起点
            if (S.count(x) && !S.count(x - 1)) {
                int y = x;
                // 删除掉，避免nums里有重复的数会重复枚举的情况
                S.erase(x);
                while (S.count(y + 1)) {
                    y ++ ;
                    S.erase(y);
                }
                res = max(res, y - x + 1);
            }
        }

        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

133. 克隆图

使用hash表，然后dfs.这个算是一个通用的解法

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector neighbors;
    Node() {
        val = 0;
        neighbors = vector();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector();
    }
    Node(int _val, vector _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/

class Solution {
public:
    unordered_map<Node*, Node*> hash;

    Node* cloneGraph(Node* node) {
        if (!node) return NULL;
        dfs(node);  // 复制所有点

        for (auto [s, d]: hash) {
            for (auto ver: s->neighbors)
                d->neighbors.push_back(hash[ver]);
        }

        return hash[node];
    }

    void dfs(Node* node) {
        hash[node] = new Node(node->val);

        for (auto ver: node->neighbors)
            if (hash.count(ver) == 0)
                dfs(ver);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

165. 比较版本号

class Solution {
public:
    int compareVersion(string v1, string v2) {
        for (int i = 0, j = 0; i < v1.size() || j < v2.size();) {
            int a = i, b = j;
            while (a < v1.size() && v1[a] != '.') a ++ ;
            while (b < v2.size() && v2[b] != '.') b ++ ;
            // 当第一个字符串已经枚举完，也就是i < v1.size()不满足的情况下，会走到 (a == i)的逻辑
            int x = a == i ? 0 : stoi(v1.substr(i, a - i));
            int y = b == j ? 0 : stoi(v2.substr(j, b - j));
            if (x > y) return 1;
            if (x < y) return -1;
            i = a + 1, j = b + 1;
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

215. 数组中的第K个最大元素

是快速排序的一部分代码，我们先看快速排序怎么写的. 这个可以当做模板使用

const int N = 100005;
int n;
int a[N];

void qsort(int a[], int l, int r) {
    if (l >= r) return ;
    int x = a[l + r >> 1], i = l - 1, j = r + 1;
    while (i < j) {
        do i++; while (a[i] < x);
        do j--; while (a[j] > x);
        if (i < j) swap(a[i], a[j]);
    }
    qsort(a, l, j);
    qsort(a, j + 1, r);
}

int main() {
    ios::sync_with_stdio (false);
    cin.tie (0);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    qsort(a, 0, n - 1);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

下面是这部分的代码

class Solution {
public:
    // 找到a[l...r]中第k小的时候，k是从1开始，k=1表示最小的数.
    int findKth(vector<int>& a, int l, int r, int k) {
        if (l == r) return a[l];
        int x = a[(l + r) >> 1], i = l - 1, j = r + 1;
        while (i < j) {
            do i++; while (a[i] < x);
            do j--; while (a[j] > x);
            if (i < j) swap(a[i], a[j]);
        }
        // 把区间分为了[l, j], [j + 1, r]两部分
        int c = j - l + 1;
        if (k <= c) return findKth(a, l, j, k);
        else return findKth(a, j + 1, r, k - c);
    }

    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        // 这个题目是求k大,这里转为求第k小的问题
        k = n + 1 - k;
        return findKth(nums, 0, n - 1, k);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

题解

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* ans;
    bool dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr) return false;
        bool lson = dfs(root->left, p, q);
        bool rson = dfs(root->right, p, q);
        if ((lson && rson) || ((root->val == p->val || root->val == q->val) && (lson || rson))) {
            ans = root;
        }
        return lson || rson || (root->val == p->val || root->val == q->val);
    }
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

比较简单的写法，用state维护状态

class Solution {
public:
    TreeNode* ans = NULL;

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        dfs(root, p, q);
        return ans;
    }

    int dfs(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (!root) return 0;
        // 已经找到答案了
        if (ans != nullptr) return 0;
        int state = 0;
        if (root == p) state |= 1;
        if (root == q) state |= 2;
        state |= dfs(root->left, p, q);
        state |= dfs(root->right, p, q);
        if (state == 3 && !ans) ans = root;
        return state;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

297. 二叉树的序列化与反序列化

这里用前序遍历的方法来做

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:

    void solve(TreeNode* root, string& s) {
        if (root == nullptr) s += "#,";
        else {
            s += to_string(root -> val) + ',';
            solve(root -> left, s);
            solve(root -> right, s);
        }
    }

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string s;
        solve(root, s);
        return s;
    }

    TreeNode* solve(string& data, int& u) {
        if (data[u] == '#') {
            u += 2;
            return nullptr;
        } else {
            int k = u;
            // 找到连续的数字，对应val
            while (data[u] != ',') u++;
            TreeNode* root = new TreeNode(stoi(data.substr(k, u - k)));
            u++;
            root -> left = solve(data, u);
            root -> right = solve(data, u);
            return root;
        }
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int u = 0;
        return solve(data, u);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

384. 打乱数组

循环一遍。假设当前下标为i，数组长度为n, 每次交换索引i，与索引[i, n-1]中的某一个

class Solution {
public:
    vector<int> a;
    Solution(vector<int>& nums) {
        a = nums;
    }
    
    vector<int> reset() {
        return a;
    }
    
    vector<int> shuffle() {
        int n = a.size();
        auto b = a;
        // 每次交换 b[i], 和 b[[i, n - 1]]内的一个数
        for (int i = 0; i < n; i++) swap(b[i], b[rand() % (n - i) + i]);
        return b;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

426. 将二叉搜索树转化为排序的双向链表 VIP

递归处理，null判断掉。对于X的子树，X需要子树转完链表后的头结点和尾节点, 我们定义一个Info结构体来处理。递归结束后要把整个链表的头尾也连上.

class Solution {
    struct Info {
        TreeNode * start;
        TreeNode *end;
        
        Info(TreeNode * start, TreeNode * end) : start(start), end(end){
        }
    };
    
    Info *process(TreeNode *x){
        if(x == nullptr) return new Info(nullptr, nullptr);
        auto left = process(x->left);
        auto right = process(x->right);
        
        //维护当前节点和左右子树的左右指针
        if(left->end != nullptr) left->end->right = x;
        x->left = left->end;
        x->right = right->start;
        if(right->start != nullptr) right->start->left = x;
        auto start = left->start != nullptr ? left->start : x;
        auto end = right->end != nullptr ? right->end : x;
        return new Info(start, end);
    }
public:
    TreeNode* treeToDoublyList(TreeNode *head) {
        if(head == nullptr) return nullptr;
        auto all = process(head);
        all->start->left = all->end;
        all->end->right = all->start;
        return all->start;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

449. 序列化和反序列化二叉搜索树

将树进行前序遍历后的字符串存下来，注意这里不需要存类似于lc297的空节点。因为这是一个二叉搜索树，它的中序遍历是有序的。也就是说前序里后的第一个节点为根节点，那么后面连续的一段小于当前值的节点即为它的左子树。递归处理即可。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
public:
    void solve(TreeNode* root, string& path) {
        if (!root) return;
        path += to_string(root -> val) + ' ';
        solve(root -> left, path);
        solve(root -> right, path);
    }
    string serialize(TreeNode* root) {
        string path;
        solve(root, path);
        return path;
    }
    
    TreeNode* solve(vector<int>& v, int &u, int lower, int upper) {
        if (v.size() == u || v[u] < lower || v[u] > upper) return nullptr;
        TreeNode* root = new TreeNode(v[u++]);
        root -> left = solve(v, u, lower, root -> val - 1);
        root -> right = solve(v, u, root -> val + 1, upper);
        return root;
    }

    TreeNode* deserialize(string data) {
        vector<int> v;
        stringstream ss(data);
        int x, u = 0;
        while (ss >> x) v.push_back(x);
        return solve(v, u, INT_MIN, INT_MAX);
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40