代码随想录刷题记录

代码随想录复习

这篇博客是二刷代码随想录过程中的一些笔记以及记录。

ch1 数组

二分查找

704. 二分查找 - 力扣（LeetCode）

二分查找相对简单，重点是要搞清楚边界，我记二分模版的方法是：

  1. while (l <= r) 为什么是<=，可以这样考虑，如果数组只有一个数据，那么也应当执行一次循环。
  2. 根据nums[mid] > target，nums[mid] < target，nums[mid] == target，三种情况分别讨论，保证不重不漏。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            }  else {
                return mid;
            }
        }
        return -1;
    }
};

相关题目：

35. 搜索插入位置 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;

        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                return mid;
            }
        }
        // 如果跳出了循环则 ==> l一定大于r
        return l;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int left = -1, right = -1;

        int l = 0, r = nums.size() - 1;
        
        // 寻找left
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                left = mid;
                r = mid - 1; // 继续寻找左边的答案
            }
        }

        l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (nums[mid] > target) {
                r = mid - 1;
            } else if (nums[mid] < target) {
                l = mid + 1;
            } else {
                right = mid;
                l = mid + 1;
            }
        }

        return {left, right};
    }
};

69. x 的平方根 - 力扣（LeetCode）

注意这里在求mid的时候，不能使用（l + r) >> 1

因为数据范围可能爆int

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) return 0;
        int l = 1, r = x;

        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (x / mid > mid) {
                l = mid + 1;
            } else if (x / mid < mid) {
                r = mid - 1;
            } else {
                return mid;
            }
        }
        return r;
    }
};

367. 有效的完全平方数 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool isPerfectSquare(int num) {
        int l = 1, r = num;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (num * 1.0 / mid > mid) {
                l = mid + 1;
            } else if (num * 1.0 / mid < mid) {
                r = mid - 1;
            } else {
                return true;
            }
        }
        return false;
    }
};

双指针

27. 移除元素 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0, j = 0;

        for (; i < nums.size(); i ++ ) {
            if (nums[i] != val) {
                nums[j] = nums[i];
                j ++;
            }
        }

        return j;
    }
};

26. 删除有序数组中的重复项 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i = 1, j = 1;
        for (; i < nums.size(); i ++ ) {
            if (nums[i] != nums[i - 1]) {
                nums[j] = nums[i];
                j ++;
            }
        }
        return j;
    }
};

283. 移动零 - 力扣（LeetCode）

(灵神的代码，非常简洁)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0;
        for (int& x : nums) { // 注意 x 是引用
            if (x) {
                swap(x, nums[i]);
                i++;
            }
        }
    }
};

844. 比较含退格的字符串 - 力扣（LeetCode）

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
// 栈写法
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        stack<char> st1, st2;

        for (int i = 0; i < s.size(); i ++ ) {
            if (s[i] != '#') {
                st1.push(s[i]);
            } else {
                if (!st1.empty()) st1.pop();
            }
        }

        for (int i = 0; i < t.size(); i ++ ) {
            if (t[i] != '#') {
                st2.push(t[i]);
            } else {
                if (!st2.empty()) st2.pop();
            }
        }

        if (st1.size() != st2.size()) return false;

        while (!st1.empty()) {
            char a = st1.top(), b = st2.top();
            if (a != b) return false;
            st1.pop(), st2.pop();
        }

        return true;
    }
};
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
// 双指针写法
class Solution {
public:
    bool backspaceCompare(string s, string t) {
        int i = s.size() - 1, j = t.size() - 1;
        int skip_s = 0, skip_t = 0;

       while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (s[i] == '#') skip_s++, i --;
                else if (skip_s > 0) skip_s--, i --;
                else {
                    break;
                }
            }

            while (j >= 0) {
                if (t[j] == '#') skip_t ++, j --;
                else if (skip_t > 0) skip_t --, j --;
                else {
                    break;
                }
            }

            if (i >= 0 && j >= 0) {
                if (s[i] != t[j]) return false;
            } else {
                if (i >= 0 || j >= 0) return false;
            }
            i --, j --;
       }
       return true;
    }
};

977. 有序数组的平方 - 力扣（LeetCode）

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
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int index = 0;
        while (index < nums.size() && nums[index] <= 0) index ++;

        vector<int> a(index, 0);
        vector<int> b(nums.size() - index, 0);

        int i = index - 1, j = index, k = 0;
        for (; i >= 0; i -- ) {
            a[k ++ ] = nums[i] * nums[i];
        }

        k = 0;
        for (; j < nums.size(); j ++ ) {
            b[k ++ ] = nums[j] * nums[j];
        }

        // 合并两个数组
        i = 0, j = 0, k = 0;
        while (i < a.size() && j < b.size()) {
            if (a[i] <= b[j]) nums[k ++ ] = a[i ++ ];
            else nums[k ++ ] = b[j ++ ]; 
        }

        while (i < a.size()) nums[k ++ ] = a[i ++ ];
        while (j < b.size()) nums[k ++ ] = b[j ++ ];

        return nums;
    }
};

滑动窗口

209. 长度最小的子数组 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i = 0, j = 0, sum = 0, ans = INT_MAX;

        // 窗口 (i - j + 1)
        for (; i < nums.size(); i ++ ) {
            sum += nums[i];

            while (j <= i && sum >= target) {
                ans = min(ans, i - j + 1);
                sum -= nums[j], j ++;
            }
        }

        if (ans == INT_MAX) return 0;
        else return ans;
    }
};

904. 水果成篮 - 力扣（LeetCode）

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
class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        int cnt = 0;
        int ans = 0;
        pair<int, int> p1 = {-1, 0};
        pair<int, int> p2 = {-1, 0};

        int i = 0, j = 0;
        for (; i < fruits.size(); i ++ ) {
            if (fruits[i] == p1.first) {
                p1.second ++;
            } else if (fruits[i] == p2.first) {
                p2.second ++;
            } else {
                // 新水果
                while (cnt >= 2) {
                    if (fruits[j] == p1.first) {
                        p1.second --;
                        if (p1.second == 0) cnt --;
                    } else {
                        p2.second --;
                        if (p2.second == 0) cnt --;
                    }
                    j ++;
                }

                if (p1.second == 0) {p1.first = fruits[i]; p1.second = 1;}
                else {p2.first = fruits[i]; p2.second = 1;}

                cnt ++;
            }
            ans = max(ans, p1.second + p2.second);
        }
        return ans;
    }
};

76. 最小覆盖子串 - 力扣（LeetCode）

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
class Solution {
public:
    string minWindow(string s, string t) {
        if (s.size() < t.size()) return "";

        unordered_map<char, int> umap;
        for (auto c : t) umap[c] ++;

        int left = 0, right = s.size() + 10;
        int i = 0, j = 0, cnt = 0;
        for (; i < s.size(); i ++ ) {
            if (umap.find(s[i]) != umap.end()) {
                umap[s[i]] --;
                if (umap[s[i]] >= 0) cnt ++;
            }

            while (cnt == t.size()) {
                if (right - left > i - j) {
                    left = j;
                    right = i;
                }

                if (umap.find(s[j]) != umap.end()) {
                    umap[s[j]] ++;
                    if (umap[s[j]] > 0) cnt --;
                }
                j ++;
            }
        }
        if (right == s.size() + 10) return "";
        string ans = s.substr(left, right - left + 1);
        return ans;
    }
};

模拟

59. 螺旋矩阵 II - 力扣（LeetCode）

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
class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        int count = n * n;
        int k = 1;
        int up = 0, down = n - 1, left = 0, right = n - 1;

        while (k <= count) {
            for (int i = left; i <= right && k <= count; i ++ ) matrix[up][i] = k ++;
            up ++;

            for (int i = up; i <= down && k <= count; i ++ ) matrix[i][right] = k ++;
            right --;

            for (int i = right; i >= left && k <= count; i -- ) matrix[down][i] = k ++;
            down --;

            for (int i = down; i >= up && k <= count; i -- ) matrix[i][left] = k ++;
            left ++;
        }

        return matrix;
    }
};

54. 螺旋矩阵 - 力扣（LeetCode）

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:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ans;

        int m = matrix.size(), n = matrix[0].size();
        int k = 1, count = m * n;
        int up = 0, down = m - 1, left = 0, right = n - 1;

        while (k <= count) {
            for (int i = left; i <= right && k <= count; i ++, k ++ ) ans.push_back(matrix[up][i]);
            up ++;

            for (int i = up; i <= down && k <= count; i ++, k ++ ) ans.push_back(matrix[i][right]);
            right --;

            for (int i = right; i >= left && k <= count; i --, k ++ ) ans.push_back(matrix[down][i]);
            down --;

            for (int i = down; i >= up && k <= count; i --, k ++ ) ans.push_back(matrix[i][left]);
            left ++;
        }

        return ans;
    }
};

LCR 146. 螺旋遍历二维数组 - 力扣（LeetCode）

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
class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        if (array.size() == 0) return {};
        vector<int> ans;

        int m = array.size(), n = array[0].size();
        int k = 1, count = m * n;
        int up = 0, down = m - 1, left = 0, right = n - 1;

        while (k <= count) {
            for (int i = left; i <= right && k <= count; i ++, k ++ ) ans.push_back(array[up][i]);
            up ++;

            for (int i = up; i <= down && k <= count; i ++, k ++ ) ans.push_back(array[i][right]);
            right --;

            for (int i = right; i >= left && k <= count; i --, k ++ ) ans.push_back(array[down][i]);
            down --;

            for (int i = down; i >= up && k <= count; i --, k ++ ) ans.push_back(array[i][left]);
            left ++;
        }

        return ans;
    }
};

前缀和

58. 区间和（第九期模拟笔试）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n;
int a[N], b[N];
int main() {
    cin >> n;

    for (int i = 1; i <= n; i ++ ) {cin >> a[i]; b[i] = b[i - 1] + a[i];}

    int l, r;
    while (cin >> l >> r) {
        cout << b[r + 1] - b[l] << endl;
    }

    return 0;
}
Leetcode
#代码随想录
代码随想录刷题记录
http://example.com/2025/03/25/leetcode/
Author
yuanyuan
Posted on
March 25, 2025
Licensed under