热题100学习笔记

热题100学习笔记

哈希

字母异位词分组

  • 字母异位词分组：49.字母异位词分组
  • 思路：这道题目通过长度为 26 的 string 记录字母数量一样的字符串（由于 unordered_map 要求 Key 是可哈希的，因此 Key 不能够存 vector 类型），通过 unordered_map 来找到属于相同字母异位词的字符串，最后将其合并到数组中。

字母异位词分组的存储结构

  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> result;
        unordered_map<string, vector<string>> mp;
        for(int i=0; i<strs.size(); i++){
            string index(26, 0);
            for(int j=0; j<strs[i].size(); j++){
                index[strs[i][j] - 'a']++;
            }
            mp[index].push_back(strs[i]);
        }
        for(unordered_map<string, vector<string>>::iterator it = mp.begin(); it!=mp.end(); it++){
            result.push_back((*it).second);
        }
        return result;
    }
};

最长连续序列

  • 最长连续序列：128.最长连续序列
  • 思路：用 unordered_set 存所有数，再遍历数组，以其中数为起点向左右扩展判断是否连续，把已经访问过的数删掉避免重复。这样每个数只会被访问一次，整体 O(n)O(n)。
  • 代码：
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
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> se;
        int ans = 0;
        for(int i=0; i<nums.size() ; i++){
            se.insert(nums[i]);
        }
        for(int i=0; i<nums.size(); i++){
            unordered_set<int>::iterator it = se.find(nums[i]);
            if(it!=se.end()){
                int i=1;
                while(se.find(*it-i)!=se.end()){
                    se.erase(*it-i);
                    i++;
                }
                int j=1;
                while(se.find(*it+j)!=se.end()){
                    se.erase(*it+j);
                    j++;
                }
                se.erase(*it);
                ans = max(ans, i+j-1);
            }
        }
        return ans;
    }
};

双指针

移动零

  • 移动零：283.移动零
  • 思路：这道题目采用双指针的解法，首先定义 left 和 right 同时指向 0 位置，移动 right 指针，当 right 所指的元素不等于 0 时，交换 left 和 right 所指的元素，并且 left 右移一位。
    • 需要注意的是不需要保证 left 初始指向的是 0，left 如果初始指向的是非 0，那么 left 和 right 就会指向同一个位置，同一个位置互换等于没有操作，之后 left 和 right 指针一起往右边移动一位。只有当 left 第一次值为 0 的时候，right 就会和 left 指针分离，直到找到一个非 0 的数然后跟 left 去进行交换。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int left = 0;
        for(int right = 0; right<nums.size(); right++){
            if(nums[right] != 0){
                swap(nums[left], nums[right]);
                left++;
            }
        }
    }
};

盛最多水的容器

  • 盛最多水的容器：11.盛最多水的容器
  • 思路：
    • 采用双指针法：
      • 用两个指针 i 和 j 分别指向数组的开头和末尾，代表选取的两条竖线。
        • 计算当前容器的水量：用一个变量 ans 记录最大面积。
      • 指针移动策略：
        • 如果 height[i] < height[j]，说明高度受限于左边的竖线，只有右移 i 才有可能找到更高的竖线，从而可能获得更大的面积。
        • 反之，如果 height[j] <= height[i]，则左边已经不再是瓶颈，右边才是短板，因此左移 j。
        • 如此不断缩小区间，直到两个指针相遇。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxArea(vector<int>& height) {
        int ans = 0;
        int min_h = 0;
        int i=0;
        int j=height.size()-1;
        while(i<j){
            min_h = min(height[i], height[j]);
            ans = max(ans, min_h*(j-i));
            if(height[i]<height[j])
                i++;
            else
                j--;
        }
        return ans;
    }
};

滑动窗口

无重复字符的最长子串

  • 无重复字符的最长子串：3.无重复字符的最长子串
  • 思路：用两个指针 left 和 right 表示当前考察的窗口区间 [left, right)。unordered_set<char> 用来存储窗口内的字符，保证窗口内不出现重复。（滑动窗口+哈希集合）的问题。
    • 当 s[right] 不在集合里时，说明窗口可以安全扩张，将 s[right] 插入集合，right++ 向右移动，更新最大长度 result = max(result, right - left) 。
    • 当 s[right] 已经在集合中时，说明出现重复字符，删除 s[left]， left++ 收缩窗口，直到窗口内没有重复字符。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> se;
        int left = 0;
        int right = 0;
        int result = 0;
        while(right<s.size() && left<=right){
            if(se.find(s[right]) == se.end()){
                se.insert(s[right]);
                right++;
            }
            else{
                se.erase(s[left]);
                left++;
            }
            result = max(result, right-left);
        }
        return result;
    }
};

找到字符串中所有字母异位词

  • 找到字符串中所有字母异位词：438.找到字符串中所有字母异位词
  • 思路：
    • 滑动窗口：
      • 由于我们需要检查 s 中所有长度为 p.size() 的子字符串是否是 p 的字母异位词，我们可以使用 滑动窗口 方法。
      • 滑动窗口的长度固定为 p.size()，并且每次移动一位，检查当前窗口内的子字符串是否是 p 的字母异位词。
    • 主要步骤：
      • 统计 p 中字符的频率：首先我们通过哈希表统计字符串 p 中每个字符出现的频率。
      • 滑动窗口遍历 s：
        • 使用两个哈希表：umapP 用于存储 p 中字符的频率，umapS 用于存储当前窗口内字符的频率。
        • 使用一个计数器 have 来记录当前窗口内与 p 相同频率的字符数。当 umapS 中的字符频率与 umapP 相等时，have 增加。
    • 滑动窗口操作：
      • 初始化时，将窗口的前 p.size() 个字符添加到 umapS 中，并更新 have 计数器。
      • 然后，每次将窗口右移一位：删除左侧字符，添加右侧新字符，更新 umapS 和 have。
    • 判断条件：如果 have 等于 umapP 中不同字符的数目（即 Pcount），说明当前窗口内的字符串是 p 的字母异位词，将该窗口的左边界索引添加到结果列表中。
  • 代码：
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:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char, int> umapP;
        for(int i=0; i<p.size(); i++){
            umapP[p[i]]++;
        }
        int Pcount = umapP.size();
        int have = 0;
        int left = 0;
        int right = p.size()-1;
        unordered_map<char, int> umapS;
        for(int i=0; i<p.size(); i++){
            umapS[s[i]]++;
            if(umapP[s[i]] == umapS[s[i]])
                have++;
        }
        vector<int> ans;
        while(right < s.size()){
            if(have == Pcount)
                ans.push_back(left);
            if(umapP.find(s[left])!=umapP.end() && umapS[s[left]] == umapP[s[left]])
                have--;
            umapS[s[left]]--;
            left++;
            right++;
            umapS[s[right]]++;
            if(umapP.find(s[right])!=umapP.end() && umapS[s[right]] == umapP[s[right]])
                have++;
        }
        return ans;
    }
};

子串

和为 K 的子数组

  • 和为 K 的子数组：560.和为 K 的子数组
  • 思路：这道题是典型的前缀和+哈希表解法，用来统计和为 k 的连续子数组个数。
    • 在开始时放入 mp[0] = 1，表示「前缀和为 0 出现过 1 次」，这样可以处理从数组开头开始的子数组。
    • 用一个哈希表 mp 存储某个前缀和出现的次数。在遍历过程中，此时前缀和为 sum 时，只要 sum - k 在哈希表中存在，说明之前有某个前缀和能让子数组和刚好为 k。于是把 mp[sum - k] 累加到答案 ans 中。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int sum = 0;
        int ans = 0;
        unordered_map<int, int> mp;
        mp[0] = 1;
        for(int i=0; i<nums.size(); i++){
            sum+=nums[i];
            if(mp.find(sum-k)!=mp.end()){
                ans+=mp[sum-k];
            }
            mp[sum]++;
        }
        return ans;
    }
};

最小覆盖子串

  • 最小覆盖子串：3.无重复字符的最长子串
  • 思路：
    • 哈希表统计需求
      • 用一个哈希表 umpT 统计字符串 t 中每个字符的需求频次。
      • 用另一个哈希表 umpS 记录当前滑动窗口中各字符出现的次数。
    • 滑动窗口
      • 用两个指针 left 和 right 表示窗口的左右边界。
      • right 每次右移，扩展窗口，把新字符加入统计。
      • 当窗口满足条件（即窗口中所有字符频次均达到要求时），尝试收缩 left，尽量缩小窗口长度，同时更新最优解。
    • 满足条件的判断
      • tCount：t 中不同字符的个数。
      • have：窗口中已经满足要求的字符种类数。
      • 当 have == tCount 时，说明当前窗口已覆盖了 t 的所有字符。
    • 更新答案
      • 每次满足条件时，如果窗口长度比之前记录的更小，就更新最短子串的起点和长度。
    • 正确性核心
      • 右扩：保证窗口最终能覆盖所有需要的字符。
      • 左缩：保证在满足条件的情况下尽可能缩短窗口，找到最优解。
      • 利用哈希表准确维护每个字符的需求量，保证不会遗漏或冗余。
  • 代码：
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
class Solution {
public:
    string minWindow(string s, string t) {
        // 如果s或t中有一个空串就返回空串
        if(s == "" || t == "")
            return "";
        // 将字符串t加入到哈希表中
        unordered_map<char, int> umpT;
        for(int i=0; i<t.size(); i++){
            umpT[t[i]]++;
        }
        // 定义滑动窗口变量
        unordered_map<char, int> umpS;
        int tCount = umpT.size();
        int have = 0;
        int right = 0;
        int left = 0;
        // 定义子串长度和起点
        int resLen = INT_MAX;
        int resStart = 0;
        // 滑动窗口遍历字符串
        while(right<s.size()){
            if(umpT.find(s[right]) != umpT.end()){
                umpS[s[right]]++;
                if(umpT[s[right]] == umpS[s[right]]){
                    have++;
                }
            }
            // 移动左边界的情况
            while(have == tCount){
                if(right-left+1 < resLen){
                    resLen = right-left+1;
                    resStart = left;
                }
                if(umpT.find(s[left]) != umpT.end()){
                    umpS[s[left]]--;
                    // 关键：umpS[s[left]] 的数量有可能减少一个后还比 umpT[s[left]] 多
                    if(umpT[s[left]] > umpS[s[left]])
                        have--;
                }
                left++;
            }
            // 移动右边界
            right++;
        }
        if(resLen == INT_MAX)
            return "";
        else
            return s.substr(resStart, resLen);
    }
};

普通数组

轮转数组

  • 轮转数组：189.轮转数组
  • 思路：先翻转整个数组，再翻转前 k 个元素和后 k 个元素就能得到答案。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    void reverse(vector<int>& nums, int left, int right){
        while(left < right){
            swap(nums[left], nums[right]);
            right--;
            left++;
        }
    }
    void rotate(vector<int>& nums, int k) {
        if(nums.size() == 1)
            return;
        int mv = k % nums.size();
        // 先翻转整个数组
        reverse(nums, 0, nums.size()-1);
        // 再翻转前k个和后k个
        reverse(nums, 0, mv-1);
        reverse(nums, mv, nums.size()-1);
    }
};

除自身以外数组的乘积

  • 除自身以外数组的乘积：238.除自身以外数组的乘积
  • 思路：
    • 一个数的结果 = 左边所有元素的乘积 × 右边所有元素的乘积。
    • 构造前缀积和后缀积：
      • prefix[i] = 从 nums[0] 到 nums[i-1] 的乘积（不包含 nums[i]）。
      • postfix[i] = 从 nums[i+1] 到 nums[n-1] 的乘积（不包含 nums[i]）。
    • 合并结果
      • 遍历数组，用 ans[i] = prefix[i] * postfix[i] 得到答案。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // 除去第i个元素自身的前缀积和后缀积
        vector<int> prefix(nums.size(), 1);
        vector<int> postfix(nums.size(), 1);
        vector<int> ans(nums.size(), 1);
        // 生成前缀积和后缀积
        for(int i=1; i<nums.size(); i++){
            prefix[i] = prefix[i-1]*nums[i-1];
        }
        for(int i=nums.size()-2; i>=0; i--){
            postfix[i] = postfix[i+1]*nums[i+1];
        }
        for(int i=0; i<nums.size(); i++){
            ans[i] = prefix[i]*postfix[i];
        }
        return ans;
    }
};

矩阵

矩阵置零

  • 矩阵置零：73.矩阵置零
  • 思路：首先找到找到 0 元素所在位置，再分别按照 0 元素所在位置的行和列都置为 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
27
28
29
30
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        vector<int> row; // 行
        vector<int> col; // 列
        int m = matrix.size();
        int n = matrix[0].size();
        // 找到 0 元素所在位置
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(matrix[i][j] == 0){
                    row.push_back(i);
                    col.push_back(j);
                }
            }
        }
        // 按列置为0
        for(int i=0; i<row.size(); i++){
            for(int j=0; j<n; j++){
                matrix[row[i]][j] = 0;
            }
        }
        // 按行置为0
        for(int i=0; i<col.size(); i++){
            for(int j=0; j<m; j++){
                matrix[j][col[i]] = 0;
            }
        }
    }
};

螺旋矩阵

  • 螺旋矩阵：54.螺旋矩阵
  • 思路：

    1. 初始化边界：

      • 为了逐步收缩矩阵，我们需要维护四个边界：top, bottom, left, right。这些边界表示当前有效矩阵的四条边，它们会逐渐向内收缩，直到所有的元素都被遍历。
      • top：上边界，初始值为 0。
      • bottom：下边界，初始值为矩阵的行数 m。
      • left：左边界，初始值为 0。
      • right：右边界，初始值为矩阵的列数 n。

    2. 按螺旋顺序遍历：

      • 我们的遍历过程按照螺旋顺序进行，依次走四个方向：
        • 向右：遍历当前 top 行，从 left 到 right-1。
        • 向下：遍历当前 right-1 列，从 top 到 bottom-1。
        • 向左：遍历当前 bottom-1 行，从 right-1 到 left。
        • 向上：遍历当前 left 列，从 bottom-1 到 top。
      • 每遍历完一个方向后，更新对应的边界：
        • 向右遍历后，top 增加。
        • 向下遍历后，right 减少。
        • 向左遍历后，bottom 减少。
        • 向上遍历后，left 增加。

    3. 边界条件：

      • 每次遍历后，我们检查新的边界条件，确保当前的有效区域仍然有效。如果 top >= bottom 或 left >= right，则表示矩阵已经遍历完，退出循环。

    4. 结束条件：

      • 当所有元素被遍历完时，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
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> ans;
        // bottom 和 right 为有效数据的后一位
        int top = 0, bottom = m, left = 0, right = n; 
        while(left<right && top<bottom){
            // 向右
            for(int i=left; i<right; i++){
                ans.push_back(matrix[top][i]);
            }
            top++;
            if(top>=bottom)
                break;
            // 向下
            for(int i=top; i<bottom; i++){
                ans.push_back(matrix[i][right-1]);
            }
            right--;
            if(left>=right)
                break;
            // 向左
            for(int i=right-1; i>=left; i--){
                ans.push_back(matrix[bottom-1][i]);
            }
            bottom--;
            if(top>=bottom)
                break;
            // 向上
            for(int i=bottom-1; i>=top; i--){
                ans.push_back(matrix[i][left]);
            }
            left++;
        }
        return ans;
    }
};

旋转图像

  • 旋转图像：48.旋转图像
  • 思路：
    • 定义四个指针：top、bottom、left、right，分别表示当前处理层的四个边界。
      • 在 left < right 的前提下，每次循环处理一层（从外到内）。
    • 对于每层：
      • 逐个元素进行四边交换（top → right → bottom → left → top），利用一个 tmp 做中转。
      • 完成一圈后，收缩边界：top++, bottom--, left++, right--，进入内层。
    • 最终所有层完成后，矩阵即被原地旋转 90°。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int top = 0, bottom = matrix.size()-1;
        int left = 0, right = matrix[0].size()-1;
        int tmp = 0;
        while(left<right){
            for(int i=0; i<right-left; i++){
                tmp = matrix[top][left+i];
                matrix[top][left+i] = matrix[bottom-i][left];
                matrix[bottom-i][left] = matrix[bottom][right-i];
                matrix[bottom][right-i] = matrix[top+i][right];
                matrix[top+i][right] = tmp;
            }
            left++;
            right--;
            top++;
            bottom--;
        }
    }
};

搜索二维矩阵 II

  • 搜索二维矩阵 II：240.搜索二维矩阵 II
  • 思路：
    • 利用矩阵的有序性，从右上角 ( matrix[0][n-1] ) 作为起点开始搜索。
      • 如果 target < 当前值：说明目标数一定在左边，列指针 lie--；
      • 如果 target > 当前值：说明目标数一定在下边，行指针 hang++；
      • 如果相等，则直接返回 true
    • 不断缩小搜索范围，直到行或列越界结束。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int hang = 0, lie = n-1;
        while( hang<m && lie>=0 ){
            if(target < matrix[hang][lie])
                lie--;
            else if(target > matrix[hang][lie])
                hang++;
            else
                return true;
        }
        return false;
    }
};

链表

回文链表

  • 回文链表：234.回文链表
  • 思路：该题的思路分为三部分：
    • 通过快慢指针找到链表中间，初始的时候（ ListNode* slow = head;、ListNode* fast = head->next; ）
    • 翻转后半部分链表 (从 slow->next 开始， ListNode* node = reverse(slow->next); )
    • 判断链表的前后两部分是否相等。
  • 代码：
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    // 反转链表函数
    ListNode* reverse(ListNode* head){
        ListNode* pre = nullptr;
        ListNode* node = nullptr;
        ListNode* cur = head;
        while(cur!=nullptr){
            node = cur->next;
            cur->next = pre;
            pre = cur;
            cur = node;
        }
        return pre;
    }
    
    bool isPalindrome(ListNode* head) {
        if(head == nullptr)
            return false;
        ListNode* slow = head;
        ListNode* fast = head->next;
        // 找到链表中间
        while(fast!=nullptr && fast->next!=nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        // 翻转后半部分链表
        ListNode* node = reverse(slow->next);
        // 判断前后两部分是否相等
        ListNode* cur = head;
        while(cur!=nullptr && node!=nullptr){
            if(cur->val != node->val)
                return false;
            cur = cur->next;
            node = node->next;
        }
        return true;
    }
};

两数相加

  • 两数相加：2.两数相加
  • 思路：
    • 使用指针遍历两个链表：
      • 定义指针 cur1 和 cur2，分别从 l1 和 l2 的头开始。
      • 定义变量 jinwei 存储进位。
    • 同时遍历相加：
      • 当 cur1 和 cur2 都非空时：
        • 计算当前位：num = cur1->val + cur2->val + jinwei
        • 新节点的值 = num % 10，新的进位 jinwei = num / 10
        • 把新节点接到结果链表后面
    • 处理剩余链表：
      • 如果 l1 还没走完，就继续把 cur1->val + jinwei 加进结果。
      • 如果 l2 还没走完，就继续把 cur2->val + jinwei 加进结果。
    • 处理最后的进位：
      • 如果遍历结束后 jinwei != 0，说明最高位还有进位，需要再创建一个节点。
    • 返回结果：
      • 结果链表从 head->next 开始，因为 head 是虚拟头结点。
  • 代码：
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        int jinwei = 0;
        ListNode* head = new ListNode();
        ListNode* cur = head;
        while(cur1!=nullptr && cur2!=nullptr){
            int num = cur1->val+cur2->val+jinwei;
            cur->next = new ListNode(num%10);
            jinwei=num/10;
            cur = cur->next;
            cur1 = cur1->next;
            cur2 = cur2->next;
        }
        while(cur1!=nullptr){
            int num = cur1->val+jinwei;
            cur->next = new ListNode(num%10);
            jinwei=num/10;
            cur = cur->next;
            cur1 = cur1->next;
        }
        while(cur2!=nullptr){
            int num = cur2->val+jinwei;
            cur->next = new ListNode(num%10);
            jinwei=num/10;
            cur = cur->next;
            cur2 = cur2->next;
        }
        if(jinwei!=0){
            cur->next = new ListNode(jinwei);
        }
        return head->next;
    }
};

随机链表的复制

  • 随机链表的复制：138.随机链表的复制
  • 思路：
    • 本解法使用 哈希表（unordered_map） 来建立 旧节点 → 新节点 的映射关系，分两步完成：
    • 第一步：复制所有节点（仅 val）
      • 遍历原链表，把每个节点 cur 的副本节点 tmp 创建出来。
      • 用 map[cur] = tmp 保存映射关系。
      • 此时，副本节点只存了值，next 和 random 都还没处理。
    • 第二步：建立指针关系
      • 再次遍历原链表。
      • 对于每个旧节点 cur，通过映射关系补全副本节点的指针：
        • mp[cur]->next = mp[cur->next]
        • mp[cur]->random = mp[cur->random]
    • 这样，新节点的 next 和 random 就正确指向新链表中的节点。
  • 代码：
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
/*
// 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* copyRandomList(Node* head) {
        unordered_map<Node*, Node*> mp;
        Node* cur = head;
        while(cur != nullptr){
            Node* tmp = new Node(cur->val);
            mp[cur] = tmp;
            cur = cur->next;
        }
        cur = head;
        while(cur != nullptr){
            mp[cur]->next = mp[cur->next];
            mp[cur]->random = mp[cur->random];
            cur = cur->next;
        }
        return mp[head];
    }
};

K 个一组翻转链表

  • K 个一组翻转链表：25.K 个一组翻转链表
  • 思路：
    • 虚拟节点辅助：创建 dummy 指向头结点，方便处理头部被翻转的场景。用 groupPre 表示当前要翻转这一组的前驱节点（初始为 dummy）。
    • 定位一组范围 [groupPre->next, cur]
      • 从 groupPre 出发向前数 k 个节点，到达该组的末尾 cur。
      • 若不足 k 个（cur == nullptr），说明剩余节点不足一组，直接结束（保持不变）。
    • 记录下一段起点：groupNxt = cur->next，翻转只在 [groupPre->next, cur] 这段闭区间内进行。
    • 原地翻转这一组
      • pre = groupPre->next（组内的第一个结点，翻转后会变成该组的最后一个）。
      • cur = pre->next，循环把 cur 指向 pre，逐步逆转直到 cur == groupNxt 为止。
      • 这一段标准链表原地反转模板，不额外开空间。
    • 接回链表
      • 翻转完成后，pre 指向该组新的头；groupPre->next 应该连到 pre。
      • 原组头（翻转前的 groupPre->next，此时用临时变量 tmp 保存）变成组尾，需要连到 groupNxt。
      • 更新 groupPre = tmp，准备处理下一组。
    • 循环直到无法再成组，返回 dummy->next。
  • 代码：
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* groupPre = dummy;
        while(true){
            int kth = k;
            ListNode* cur = groupPre;
            while(kth>0 && cur!=nullptr){
                kth--;
                cur = cur->next;
            }
            if(cur == nullptr)
                break;
            ListNode* groupNxt = cur->next;
            // 翻转组内节点
            ListNode* pre = groupPre->next;
            cur = pre->next;
            ListNode* tmp = nullptr;
            while(cur != groupNxt){
                tmp = cur->next;
                cur->next = pre;
                pre = cur;
                cur = tmp;
            }
            tmp = groupPre->next;
            tmp->next = groupNxt;
            groupPre->next = pre;
            groupPre = tmp;
        }
        return dummy->next;
    }
};

排序链表

  • 排序链表：148.排序链表
  • 思路一：使用 multimap<int, ListNode*> mp; 数据结构中 key 有序的特性遍历存储链表的节点，最后再按 key 的顺序从 map 中取出连接链表得到结果。
  • 代码：
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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        multimap<int, ListNode*> mp;
        ListNode* cur = head;
        while(cur != nullptr){
            mp.insert({cur->val, cur});
            cur = cur->next;
        }
        ListNode* dummy = new ListNode(0);
        cur = dummy;
        for(auto& p : mp){
            cur->next = p.second;
            cur = cur->next;
        }
        cur->next = nullptr;
        return dummy->next;
    }
};
  • 思路二：
    • 1、分割链表
      • 使用 快慢指针 找到中点：
        • slow 每次走一步，fast 每次走两步。
        • 主要快慢指针的起始点：ListNode* slow = head; 、ListNode* fast = head->next;
        • 当 fast 到尾部时，slow 正好在中点。
      • 把链表切成两半：ListNode* second = slow->next; 和 slow->next = nullptr;
    • 2、递归排序
      • 对左右两个子链表分别递归调用 sortList。
      • 递归直到子链表为空或只有一个元素（天然有序）。
    • 3、合并有序链表
      • 用双指针遍历两个有序链表，像归并排序数组一样合并。
      • 时间复杂度 O(n)O(n)。
  • 代码：
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
52
53
54
55
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeList(ListNode* first, ListNode* second){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(first != nullptr && second != nullptr){
            if(first->val < second->val){
                cur->next = first;
                first = first->next;
            }else{
                cur->next = second;
                second = second->next;
            }
            cur = cur->next;   
        }
        while(first != nullptr){
            cur->next = first;
            first = first->next;
            cur = cur->next;
        }
        while(second != nullptr){
            cur->next = second;
            second = second->next;
            cur = cur->next;
        }
        cur->next = nullptr;
        return dummy->next;
    }
    ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr)
            return head;
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* first = head;
        ListNode* second = slow->next;
        slow->next = nullptr;
        first = sortList(first);
        second = sortList(second);
        return mergeList(first, second);
    }
};

合并 K 个升序链表

  • 合并 K 个升序链表：23.合并 K 个升序链表
  • 思路一：
    • 定义一个辅助函数 mergeList，合并两个有序链表（和归并排序合并步骤一样）。
    • 从 lists[0] 开始，依次和下一个链表合并：
      • 先合并 lists[0] 和 lists[1]
      • 再把结果和 lists[2] 合并
      • 直到处理完所有链表
    • 返回最终链表。
  • 代码：
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
52
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeList(ListNode* first, ListNode* second){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(first != nullptr && second != nullptr){
            if(first->val < second->val){
                cur->next = first;
                first = first->next;
            }else{
                cur->next = second;
                second = second->next;
            }
            cur = cur->next;   
        }
        while(first != nullptr){
            cur->next = first;
            first = first->next;
            cur = cur->next;
        }
        while(second != nullptr){
            cur->next = second;
            second = second->next;
            cur = cur->next;
        }
        cur->next = nullptr;
        return dummy->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0)
            return nullptr;
        if(lists.size() == 1)
            return lists[0];
        ListNode* dummy = new ListNode(0);
        dummy->next = mergeList(lists[0], lists[1]);
        for(int i=2; i<lists.size(); i++){
            dummy->next = mergeList(dummy->next, lists[i]);
        }
        return dummy->next;
    }

};
  • 思路二：
    • 定义一个辅助函数 mergeList，合并两个有序链表（和归并排序合并步骤一样）。
    • 初始 lists 里有 k 个链表。
    • 每次遍历，按下标 0&1, 2&3, ... 两两合并，放入 tmp_lists。
    • 然后用 tmp_lists 替换原 lists，数量减半。
    • 直到 lists.size() == 1。
    • 返回最终链表。
  • 代码：
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
52
53
54
55
56
57
58
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeList(ListNode* first, ListNode* second){
        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        while(first != nullptr && second != nullptr){
            if(first->val < second->val){
                cur->next = first;
                first = first->next;
            }else{
                cur->next = second;
                second = second->next;
            }
            cur = cur->next;   
        }
        while(first != nullptr){
            cur->next = first;
            first = first->next;
            cur = cur->next;
        }
        while(second != nullptr){
            cur->next = second;
            second = second->next;
            cur = cur->next;
        }
        cur->next = nullptr;
        return dummy->next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0)
            return nullptr;
        if(lists.size() == 1)
            return lists[0];
        while(lists.size()>1){
            vector<ListNode*> tmp_lists;
            for(int i=0; i<lists.size(); i+=2){
                ListNode* l1 = lists[i];
                ListNode* l2 = nullptr;
                if(i+1 < lists.size()){
                    l2 = lists[i+1];
                }
                tmp_lists.push_back(mergeList(l1, l2));
            }
            lists = tmp_lists;
        }
        return lists[0];
    }
};

LRU 缓存

  • LRU 缓存：146.LRU 缓存
  • 思路：
    • 1、关键点
      • 哈希表：实现 key -> 节点指针 的 O(1)O(1) 查找
      • 双向链表：维护节点的使用顺序，保证插入/删除 O(1)O(1)
      • 两者结合，实现了 O(1)O(1) 的 get 和 put 操作。
    • 2、数据结构设计
      • 使用 unordered_map<int, node*> mp，存储 key 到双向链表节点的映射；
      • 双向链表（带头尾哨兵节点 head 和 tail），新访问/更新的节点放到链表头（表示最近使用过），淘汰时删除尾部前一个节点（最久未使用）。
    • 3、操作逻辑
      • get(key)，查哈希表：
        • 不存在返回 -1
        • 存在：把该节点移到链表头（表示最近使用过），返回该节点的值
      • put(key, value) 的操作：
        • 如果 key 已存在：
          • 更新节点值
          • 移动到链表头
        • 如果 key 不存在：
          • 创建新节点，插入到链表头，并放入哈希表
          • 如果容量超限：
            • 删除链表尾部节点
            • 同时从哈希表删除对应的 key
      • 链表操作：
        • LRUremove(node* tmp)：把某个节点从链表中摘除
        • insertHead(node* tmp)：把某个节点插入链表头
  • 代码：
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class node{
public:
    int key;
    int val;
    node* pre;
    node* next;
    node(int k, int v){
        key = k;
        val = v;
        pre = nullptr;
        next = nullptr;
    }
};
class LRUCache {
private:
    int cap;
    unordered_map<int, node*> mp;
    node* head = new node(0, 0);
    node* tail = new node(0, 0);
public:
    LRUCache(int capacity) {
        cap = capacity;
        head->next = tail;
        head->pre = nullptr;
        tail->next = nullptr;
        tail->pre = head;
    }
    
    int get(int key) {
        if(mp.find(key) == mp.end())
            return -1;
        LRUremove(mp[key]);
        insertHead(mp[key]);
        return mp[key]->val;
    }
    
    void put(int key, int value) {
        if(mp.find(key) == mp.end()){
            node* temp = new node(key, value);
            insertHead(temp);
            mp.insert({key, temp});
            if(mp.size() > cap){
                node* tmp = tail->pre;
                LRUremove(tail->pre);
                mp.erase(tmp->key);
                delete tmp;
            }
        }else{
            mp[key]->val = value;
            LRUremove(mp[key]);
            insertHead(mp[key]);
        }
    }
    void LRUremove(node* tmp){
        node* pre = tmp->pre;
        node* next = tmp->next;
        pre->next = next;
        next->pre = pre;
    }
    void insertHead(node* tmp){
        node* hnext = head->next;
        head->next = tmp;
        tmp->next = hnext;
        tmp->pre = head;
        hnext->pre = tmp;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

二叉树

二叉树的直径

  • 二叉树的直径：543.二叉树的直径
  • 思路：计算每个节点左子树的高度和右子树的高度相加即为经过该节点的最长直径，主要二叉树的最长直径不一定经过根节点，因此在递归计算每个节点的最长直径后取最大值保存，最终即为答案。
  • 代码：
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
/**
 * 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:
    int travelsal(TreeNode* root, int& ans){
        // 终止条件
        if(root == nullptr)
            return 0;
        int leftH = travelsal(root->left, ans);
        int rightH = travelsal(root->right, ans);
        ans = max(ans, leftH+rightH);
        return max(leftH, rightH)+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int ans = 0;
        int num = travelsal(root,ans);
        return ans;
    }
};

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

  • 二叉搜索树中第 K 小的元素：230.二叉搜索树中第K小的元素
  • 思路：
    • 递归中序遍历：
      • 先递归访问左子树；
      • 访问当前节点，计数 index++；
      • 如果 index == k，说明当前节点就是答案；
      • 最后递归右子树。
    • 通过一个全局变量 index 记录访问了多少个节点。
    • 用 ans 保存结果，一旦找到就停止继续递归（用 if(ans >= 0) return; 剪枝）。
  • 代码：
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
/**
 * 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:
    int index = 0;
    int ans = -1;
    void travelsal(TreeNode* root, int k){
        // 终止条件
        if(root == nullptr)
            return;
        if(ans>=0)
            return;
        travelsal(root->left, k);
        index++;
        if(index == k)
            ans = root->val;
        travelsal(root->right, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        travelsal(root, k);
        return ans;
    }
};

二叉树展开为链表

  • 二叉树展开为链表：114.二叉树展开为链表
  • 思路：
    • 前序遍历：
      • 首先，我们需要对二叉树进行 前序遍历（根节点 -> 左子树 -> 右子树），并将遍历得到的节点值存储在一个列表中。前序遍历确保我们能够按根-左-右的顺序访问每个节点。
    • 将树变成链表：
      • 接下来，我们需要重新构建二叉树，使得每个节点的左子树为 nullptr，并且右子树指向下一个节点。这个链表实际上就是前序遍历得到的节点值的顺序。
    • 实现步骤：
      • 先定义一个辅助函数 travelsal，进行前序遍历并将节点值保存到 list 中。
      • 在 flatten 函数中，我们遍历保存的 list，重新构建树：
        • 根节点的值设为 list[0]。
        • 之后的每个节点都作为当前节点的右子节点，左子节点设为 nullptr。
    • 通过这种方式，我们将树变成了链表。
  • 代码：
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
/**
 * 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:
    vector<int> list;
    void travelsal(TreeNode* root){
        if(root == nullptr)
            return;
        list.push_back(root->val);
        travelsal(root->left);
        travelsal(root->right);
    }
    void flatten(TreeNode* root) {
        if(root == nullptr)
            return;
        travelsal(root);
        TreeNode* cur = root;
        cur->val = list[0];
        for(int i=1; i<list.size(); i++){
            cur->right = new TreeNode(list[i]);
            cur->left = nullptr;
            cur = cur->right;
        }
    }
};

路径总和 III

  • 路径总和 III：437.路径总和 III
  • 思路：
    • 这道题用的是前缀和思想，类似数组中“和为 K 的子数组”的解法，扩展到树结构。
      • 定义：cur 表示从根到当前节点的路径和。
      • 若存在某个前缀和 pre = cur - targetSum，则说明从 pre 节点到当前节点之间的路径和等于 targetSum。
      • 用哈希表 prefix 存储「前缀和 → 出现次数」。
    • 核心逻辑：
      1. 到达当前节点时：更新当前路径和 cur += root->val。
      2. 统计路径数：查找 prefix[cur - targetSum]，说明之前出现过多少次这样的前缀和，它们对应的路径加上当前路径刚好等于目标。
      3. 递归左右子树：继续向下搜索。
      4. 回溯：递归返回时，减少当前前缀和的次数，保证不影响其他路径。
  • 代码：
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
/**
 * 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:
    // 前缀和
    unordered_map<long long, int> prefix;
    int travelsal(TreeNode* root, long long cur, int targetSum){
        // 边界条件
        if(root == nullptr)
            return 0;
        cur+=root->val;
        int count = 0;
        if(prefix.find(cur-targetSum)!=prefix.end()){
            count = prefix[cur-targetSum];
        }
        prefix[cur]++;
        count += travelsal(root->left, cur, targetSum);
        count += travelsal(root->right, cur, targetSum);
        prefix[cur]--;
        return count;
    }
    int pathSum(TreeNode* root, int targetSum) {
        prefix[0] = 1;
        return travelsal(root, 0, targetSum);
    }
};

二叉树中的最大路径和

  • 二叉树中的最大路径和：124.二叉树中的最大路径和
  • 思路：
    • 递归函数 travelsal(root) 的含义：
      • 返回值：以当前节点为起点，向上延伸时能提供的最大路径和（只能选择“左+root” 或 “右+root” 或 “root 自身”）。
      • 过程：
        1. 递归计算左子树和右子树能提供的最大贡献值。如果结果为负，直接取 0，因为负数会拖累路径和。
        2. 用当前节点作为“最高点”，计算 left + right + root->val，更新全局最大值 ans。
        3. 返回“向父节点提供的最大贡献” = max(root->val, root->val+left, root->val+right)。
  • 代码：
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
/**
 * 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:
    int ans = INT_MIN;
    int travelsal(TreeNode* root){
        // 终止条件
        if(root == nullptr)
            return 0;
        // 子节点返回的数值可能是负数，直接取 0
        int left = max(0, travelsal(root->left));
        int right = max(0, travelsal(root->right));
        ans = max(ans, left+right+root->val);
        return max(root->val, max(left+root->val, right+root->val));
    }
    int maxPathSum(TreeNode* root) {
        travelsal(root);
        return ans;
    }
};

回溯

括号生成

  • 括号生成：22.括号生成
  • 思路：定义 left 和 right 分别表示左右括号的数量，终止条件为当左右括号的数量都为 n 的时候。递归过程中有两种情况：
    • 一是左括号数量小于 n ( left < n )，此时能够往 path 里面加入左括号；
    • 二是 right<n && left>right 这个条件下可以往 path 里面加右括号。
  • 代码：
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
class Solution {
public:
    string path = "";
    vector<string> result;
    void backtracking(int n, int left, int right){
        // 终止条件
        if(left == n && right == n){
            result.push_back(path);
            return;
        }
        if(left < n){
            path.push_back('(');
            backtracking(n, left+1, right);
            path.pop_back();
        }
        if(right<n && left>right){
            path.push_back(')');
            backtracking(n, left, right+1);
            path.pop_back();
        }
        return;
    }

    vector<string> generateParenthesis(int n) {
        backtracking(n, 0, 0);
        return result;
    }
};

单词搜索

  • 单词搜索：79.单词搜索
  • 思路：
    • 这是一道典型的回溯搜索（DFS）问题。核心思想是从每个格子出发，尝试走一条路径，如果走不通就回溯。
    • 起点枚举：因为单词可能从任意格子开始，所以在 exist 里用两层循环，把每个格子作为起点尝试。
    • 递归函数设计：
      • 参数带上当前坐标 (i, j)，以及全局的 path 。
      • 判断是否匹配当前字符，不匹配就直接剪枝返回。
      • 如果已经匹配到 word.size() 长度，说明找到了整条路径，返回成功。
    • 四方向扩展：递归尝试上下左右四个方向。
    • 访问标记与回溯：用 visit 数组标记已访问的格子，走完这条路要恢复标记和路径（回溯），保证其他路径能用。
    • 剪枝：
      • 越界时立即返回；
      • 字符不匹配立即返回；
      • 找到答案时立即停止继续搜索。
    • 当前格子字符和 word[path.size()] 相等→ 继续搜索；
    • 否则 → 回溯。直到 path.size() == word.size()，返回 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
35
36
37
38
39
40
41
class Solution {
public:
    string path = "";
    void backtracking(vector<vector<char>>& board, string word, int hang, int lie, bool& flag, vector<vector<bool>>& visit){
        // 终止条件
        if(flag)
            return;
        if(path.size() == word.size()){
            flag = true;
            return;
        } 
        // 越界
        if(hang>=board.size() || lie>=board[0].size() || hang<0 || lie<0 || visit[hang][lie] == true)
            return;
        // 新加入的字符和word中应该要的字符不匹配
        if(board[hang][lie]!=word[path.size()])
            return;
        else{
            path.push_back(board[hang][lie]);
            visit[hang][lie] = true;
            backtracking(board, word, hang+1, lie, flag, visit);
            backtracking(board, word, hang, lie+1, flag, visit);
            backtracking(board, word, hang-1, lie, flag, visit);
            backtracking(board, word, hang, lie-1, flag, visit);
            visit[hang][lie] = false;
            path.pop_back();
        }
    }
    bool exist(vector<vector<char>>& board, string word) {
        bool flag = false;
        vector<vector<bool>> visit(board.size(), vector<bool>(board[0].size(), false));
        // board中任意一个位置为起点
        for(int i=0; i<board.size(); i++){
            for(int j=0; j<board[0].size(); j++){
                path.clear();
                backtracking(board, word, i, j, flag, visit);
            }
        }
        return flag;
    }
};

二分查找

搜索插入位置

  • 搜索插入位置：35.搜索插入位置
  • 思路：经典二分查找问题，可以通过模拟查找的过程找出问题所在。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        int mid = left+(right-left)/2;
        while(left<=right){
            mid = left+(right-left)/2;
            if(nums[mid] == target)
                return mid;
            if(nums[mid]>target){
                right = mid-1;
            }
            else{
                left = mid+1;
            }
        }
        return left;
    }
};

搜索二维矩阵

  • 搜索二维矩阵：74.搜索二维矩阵
  • 思路：
    • 定义搜索范围 [left, right] = [0, m*n-1]，其中 m 是行数，n 是列数。
    • 在二分查找过程中：
      • 计算中点 mid = (left + right) / 2；
      • 将一维下标 mid 转换为二维下标（关键）：
        • 行号 hang = mid / n
        • 列号 lie = mid % n
      • 比较 matrix[hang][lie] 与 target：
        • 相等 → 返回 true；
        • 大于 → 缩小右边界；
        • 小于 → 缩小左边界。
    • 查找结束仍未找到 → 返回 false。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int left = 0;
        int right = m*n-1;
        while(left<=right){
            int mid = left+(right-left)/2;
            // 关键在于二维坐标的转换
            int hang = mid/n;
            int lie = mid%n;
            if(matrix[hang][lie] == target)
                return true;
            else if(matrix[hang][lie]>target)
                right = mid-1;
            else
                left = mid+1;
        }
        return false;
    }
};

在排序数组中查找元素的第一个和最后一个位置

  • 在排序数组中查找元素的第一个和最后一个位置：34.在排序数组中查找元素的第一个和最后一个位置
  • 思路：
    • 定义一个辅助函数 binSearch(nums, target, isLeft)：
    • 当 isLeft = true 时：找到 target 最左边的位置。
      • 如果当前 nums[mid] == target，继续往左缩小范围（right = mid - 1）。
    • 当 isLeft = false 时：找到 target 最右边的位置。
      • 如果当前 nums[mid] == target，继续往右缩小范围（left = mid + 1）。
    • 其余情况正常二分：target > nums[mid] 就往右，否则往左。
    • 这样分别调用两次，就能得到左边界和右边界。
  • 代码：
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
class Solution {
public:
    int binSearch(vector<int>& nums, int target, bool isLeft){
        int left = 0;
        int right = nums.size()-1;
        int mid = left+(right-left)/2;
        int index = -1;
        while(left<=right){
            mid = left+(right-left)/2;
            if(nums[mid] == target && isLeft){
                index = mid;
                right = mid-1;
            }else if(nums[mid] == target && !isLeft){
                index = mid;
                left = mid+1;
            }else if(target>nums[mid]){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return index;
    }
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ans(2, 0);
        ans[0] = binSearch(nums, target, true);
        ans[1] = binSearch(nums, target, false);
        return ans;
    }
};

搜索旋转排序数组

  • 搜索旋转排序数组：33.搜索旋转排序数组
  • 思路：
    • 普通二分查找只适用于完全有序数组。但是旋转后的数组，可以分为两段依然有序的区间：
      • 左半段有序；
      • 右半段有序；
    • 如果 nums[left] <= nums[mid]，说明左半段有序：
      • 如果 target 落在 [nums[left], nums[mid]) 之间，就去左边查找；
      • 否则去右边查找。
    • 否则说明右半段有序：
      • 如果 target 落在 (nums[mid], nums[right]] 之间，就去右边查找；
      • 否则去左边查找。
    • 通过这种方式，每次都能排除一半的区间，保持对数复杂度。
  • 代码：
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:
    int search(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size()-1;
        int mid = left+(right-left)/2;
        while(left<=right){
            mid = left+(right-left)/2;
            if(nums[mid] == target)
                return mid;
            // mid 在前半段
            if(nums[left]<=nums[mid]){
                if(target<nums[mid] && target>=nums[left])
                    right = mid-1;
                else
                    left = mid+1;
            }else{ // mid 在后半段
                if(target>nums[mid] && target<=nums[right])
                    left = mid+1;
                else
                    right = mid-1;
            }
        }
        return -1;
    }
};

寻找旋转排序数组中的最小值

  • 寻找旋转排序数组中的最小值：153.寻找旋转排序数组中的最小值
  • 思路：
    • 在旋转后的有序数组中，总有一半区间是单调递增的。通过比较 nums[mid] 与 nums[left]、nums[right]，可以判断当前 mid 落在哪一半，并决定如何缩小搜索范围。
    • 收缩到单调区间的情况：
      • 如果 nums[left] <= nums[right]，说明当前 [left, right] 区间已经是单调递增的，此时最小值就是 nums[left]。
    • 判断 mid 所在区间
      • 如果 nums[mid] >= nums[left]，说明 mid 在左半段有序区间内，最小值一定在 mid 右边，于是移动 left = mid + 1。
      • 否则（即 nums[mid] <= nums[right]），说明 mid 落在右半段区间，最小值在 [left, mid]，于是移动 right = mid。
    • 不断收缩左右边界，直到区间收缩为单调递增区间，直接返回 nums[left]。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0;
        int right = nums.size()-1;
        int mid = left+(right-left)/2;
        while(left<=right){
            mid = left+(right-left)/2;
            // 当left和right收缩到单调递增区间
            if(nums[left]<=nums[right])
                return nums[left];
            // 在左半段区间
            if(nums[mid]>=nums[left])
                left = mid+1;
            // 在后半段区间
            else if(nums[mid]<=nums[right])
                right = mid;
        }
        return -1;
    }
};

栈

最小栈

  • 最小栈：155.最小栈
  • 思路：这道题首先定义两个栈，一个栈正常存储元素，另一个栈为最小值栈，当入栈的元素小于最小栈元素就将该最小值加入到最小栈中，否则去最小栈的栈顶元素重新加入到最小栈。

最小栈

  • 代码：
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
class MinStack {
public:
    stack<int> st;
    stack<int> min_st;

    MinStack() {   
        min_st.push(INT_MAX);
    }
    
    void push(int val) {
        if(val < min_st.top())
            min_st.push(val);
        else
            min_st.push(min_st.top());
        st.push(val);
    }
    
    void pop() {
        min_st.pop();
        st.pop();
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return min_st.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

字符串编码

  • 字符串编码：394.字符串编码
  • 思路：定义一个 string 类型的辅助栈，
    • 1、遍历字符串并压栈直到遇到 "]" ;
    • 2、定义辅助 string 类型的 tmp 并弹出栈直到遇到 "["，将字符串记录至 tmp，注意从左边加到右边，最后弹出 "[" ;
    • 3、定义辅助 string 类型的 num 并弹出栈直到字符不再是数字，将重复的次数加到 num 中，注意从左边加到右边；
    • 4、通过 stoi(num) 将 string 类型转换为 int 类型，并采用 for 循环构建重复的字符串，并重新压入栈中；
    • 5、最后从左边到右边拼接栈中字符串即可得到结果。
  • 代码：
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
class Solution {
public:
    string decodeString(string s) {
        stack<string> st;
        for(int i=0; i<s.size(); i++){
            if(s[i]!=']'){
                string tmp = "";
                tmp += s[i];
                st.push(tmp);
            }
            if(s[i] == ']'){
                string tmp = "";
                while(st.top()!="["){
                    tmp=st.top()+tmp; // 注意从左边加到右边
                    st.pop();
                }
                st.pop(); // 弹出"["
                // num
                string num = "";
                while(!st.empty() && st.top()[0]<='9' && st.top()[0]>='0'){
                    num=st.top()+num; // 注意从左边加到右边
                    st.pop();
                }
                // 拼接字符串
                string cnt = "";
                int n = stoi(num);
                for(int i=0; i<n; i++){
                    cnt=tmp+cnt;
                }
                st.push(cnt);
            }
        }
        string result;
        while(!st.empty()){
            result=st.top()+result; // 注意从左边加到右边
            st.pop();
        }
        return result;
    }
};

堆

数据流的中位数

  • 数据流的中位数：295.数据流的中位数
  • 思路：直接排序复杂度高，所以引入 两个堆：
    • 大根堆（left_que）：存储较小的一半数，堆顶是这部分的最大值。
    • 小根堆（right_que）：存储较大的一半数，堆顶是这部分的最小值。
    • 为了能直接取出中位数，必须维持两个不变量：
      • 有序性不变量：所有左边的元素 ≤ 所有右边的元素，即：left_que.top() <= right_que.top()，这样两个堆的交界就是中间。
      • 规模平衡不变量：两个堆的元素个数差不超过 1（注意这里不要用 left_que.size() - right_que.size() > 1 来判断，因为 size_t 是无符号数，负数会被解释成一个非常大的正整数），保证总数为奇数时，中位数就是元素更多的那边的堆顶，总数为偶数时，中位数就是两个堆顶的平均。
  • 代码：
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
class MedianFinder {
public:
    // 大根堆（less小于号，从小到大）
    priority_queue<int, vector<int>, less<int>> left_que;
    // 小根堆（greater大于号，从大到小）
    priority_queue<int, vector<int>, greater<int>> right_que;

    MedianFinder() {
        
    }
    
    void addNum(int num) {
        right_que.push(num);
        if(!left_que.empty() && !right_que.empty() && left_que.top()>right_que.top()){
            left_que.push(right_que.top());
            right_que.pop();
        }
        if(right_que.size() > left_que.size()+1){
            left_que.push(right_que.top());
            right_que.pop();
        }
        if(left_que.size() > right_que.size()+1){
            right_que.push(left_que.top());
            left_que.pop();
        }
    }
    
    double findMedian() {
        if(left_que.size()>right_que.size())
            return left_que.top();
        if(right_que.size()>left_que.size())
            return right_que.top();
        return (left_que.top()+right_que.top())/2.0;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

动态规划

杨辉三角

  • 杨辉三角：118.杨辉三角
  • 思路：先特殊处理前两行，然后从第三行开始，每一行的首尾固定为 1，中间元素由上一行相邻两个数相加，逐行生成直至 numRows。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        vector<int> path1(1,1);
        result.push_back(path1);
        if(numRows == 1)
            return result;
        vector<int> path2(2,1);
        result.push_back(path2);
        if(numRows == 2)
            return result;
        for(int i=2; i<numRows; i++){
            vector<int> path(i+1,1);
            for(int j=1; j<=path.size()-2; j++){
                path[j] = result[i-1][j-1]+result[i-1][j];
            }
            result.push_back(path);
        }
        return result;
    }
};

乘积最大子数组

  • 乘积最大子数组：152.乘积最大子数组
  • 思路：
    • 按照动态规划五部曲进行分析：
      • 确定 dp 数组及下标的含义：dp_max[i] 和 dp_min[i] 分别表示以 i 结尾的最大子数组乘积最小值和最大值。
      • 确定递推公式：
        • 由于 nums[i] 可能存在负数的情况，所以要把最小值也记录下来，最后从递推公式中分别取出最大值和最小值。
        • 最大值：dp_max[i] = max(dp_max[i-1]*nums[i], max(dp_min[i-1]*nums[i], nums[i]));
        • 最小值：dp_min[i] = min(dp_max[i-1]*nums[i], min(dp_min[i-1]*nums[i], nums[i]));
      • dp 数组如何初始化：除了 dp_max[0] 和 dp_min[i] 初始化成 nums[0] ，其他全部初始化成 0；
      • 确定遍历顺序：在 i 上正序遍历；
      • 举例推导 dp 数组符合要求。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // 以 i 结尾的最大子数组乘积最小值和最大值
        vector<int> dp_max(nums.size(), 0);
        vector<int> dp_min(nums.size(), 0);
        dp_max[0] = nums[0];
        dp_min[0] = nums[0];
        int ans = nums[0];
        for(int i=1; i<nums.size(); i++){
            dp_max[i] = max(dp_max[i-1]*nums[i], max(dp_min[i-1]*nums[i], nums[i]));
            dp_min[i] = min(dp_max[i-1]*nums[i], min(dp_min[i-1]*nums[i], nums[i]));
            ans = max(ans, dp_max[i]);
        }
        return ans;
    }
};

最长有效括号

  • 最长有效括号：32.最长有效括号
  • 思路：定义 dp[i]：表示以索引 i 结尾的最长有效括号子串长度。遍历字符串，从 i=1 开始（因为 dp[0] 无法形成括号）：
    1. 情况一：s[i] == ')' 且 s[i-1] == '('
      • 形如 "...()"
      • 那么 dp[i] = dp[i-2] + 2 （如果 i-2 >= 0，否则就是 2）。
    2. 情况二：s[i] == ')' 且 s[i-1] == ')'
      • 形如 "...))"
      • 那么需要去找与当前 ')' 匹配的 '('：
      • 找位置 m = i - dp[i-1] - 1（即前一个有效括号子串之前的那个位置）。
        • 如果 m >= 0 且 s[m] == '('，说明匹配成功：
          • dp[i] = dp[i-1] + 2 + dp[m-1]（如果 m-1 >= 0，否则 dp[i] = dp[i-1] + 2）。
    3. 遍历过程中，维护 ans = max(ans, dp[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
class Solution {
public:
    int longestValidParentheses(string s) {
        if(s.size() == 0)
            return 0;
        vector<int> dp(s.size(), 0);
        int ans = 0;
        for(int i=1; i<s.size(); i++){
            if(s[i] == ')'){
                if(s[i-1] == '('){
                    if(i-2>=0)
                        dp[i] = dp[i-2]+2;
                    else
                        dp[i] = 2;
                }
                if(s[i-1] == ')'){
                    int m = i-dp[i-1]-1;
                    if(m>=0 && s[m] == '('){
                        if(m-1>=0)
                            dp[i] = dp[i-1]+dp[m-1]+2;
                        else
                            dp[i] = dp[i-1]+2;
                    }
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

多维动态规划

最小路径和

  • 最小路径和：64.最小路径和
  • 思路：
    • 按照动态规划五部曲进行分析：
      • 确定 dp 数组及下标的含义：dp[i][j] 表示从 grid[0][0] 走到 grid[i-1][j-1] 的最小路径和。
      • 确定递推公式：
        • dp[i][j] 只由它的左边和上边元素递推得到，取两者的最小值即可，即 dp[i][j] = min(dp[i-1][j], dp[i][j-1])+grid[i-1][j-1];
      • dp 数组如何初始化：除了 dp[0][1] 和 dp[1][0] 初始化成 0 ，其他全部初始化成 INT_MAX；
      • 确定遍历顺序：在 i 上正序遍历，在 j 上正序遍历；
      • 举例推导 dp 数组符合要求。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<vector<int>> dp(grid.size()+1, vector<int>(grid[0].size()+1, INT_MAX));
        dp[1][0] = 0;
        dp[0][1] = 0;
        for(int i=1; i<grid.size()+1; i++){
            for(int j=1; j<grid[0].size()+1; j++){
                dp[i][j] = min(dp[i-1][j], dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[grid.size()][grid[0].size()];
    }
};

技巧

只出现一次的数字

  • 只出现一次的数字：136.只出现一次的数字
  • 思路：根据任意数与 0 异或：a ^ 0 = a，任意数与自身异或：a ^ a = 0，数组里所有数异或在一起，成对出现的数会两两抵消为 0，最后只剩下那个只出现一次的数。
  • 代码：
1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i=0; i<nums.size(); i++){
            ans ^= nums[i];
        }
        return ans;
    }
};

多数元素

  • 多数元素：169.多数元素
  • 思路：设置一个候选值 res 和计数器 count。
    • 遍历数组：
      • 如果 count == 0，把当前数设为候选人 res，并把 count 置为 1。
      • 如果当前数等于 res，count++。
      • 如果当前数不等于 res，count--。
    • 遍历完成后，res 就是多数元素。
  • 代码（摩尔投票法）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int res = 0;
        for(int i=0; i<nums.size(); i++){
            if(count == 0){
                res = nums[i];
                count++;
            }
            else if(nums[i] == res){
                count++;
            }else{
                count--;
            }
        }
        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
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int, int> mp;
        vector<int> ans(2, 0);
        for(int i=0; i<nums.size(); i++){
            unordered_map<int, int>::iterator it = mp.find(nums[i]);
            if(it == mp.end()){
                mp.insert({nums[i], 1});
                if(ans[1] < 1){
                    ans[0] = nums[i];
                    ans[1] = 1; 
                }
            }else{ 
                it->second++;
                if(it->second > ans[1]){
                    ans[0] = nums[i];
                    ans[1] = it->second; 
                }
            }
        }
        return ans[0];
    }
};

寻找重复数

  • 寻找重复数：287.寻找重复数
  • 思路：
    • 问题本质：
      • 这道题的核心问题是要找到一个在数组中重复的数字，并且给定了数组的特殊性质：
      • 数组的长度为 n + 1，所以必定有一个重复元素。
      • 数字的值范围是 1 到 n，这意味着每个数字都可以看作是数组的一个“指针”指向另一个位置。
    • 使用快慢指针（Floyd’s Tortoise and Hare）：
      • 这是一个经典的 快慢指针 方法，用于在循环链表中寻找环的入口。
      • 数组中的元素可以看作是指向另一个位置的指针。因此，如果数组中存在重复元素，那么这个重复元素将导致数组形成一个 环。
    • 具体步骤：
      • 初始化：使用两个指针 slow 和 fast。slow 每次向前走一步，fast 每次向前走两步。
      • 第一步：找到相遇点：
        • slow = nums[slow]：slow 每次向前走一步。
        • fast = nums[nums[fast]]：fast 每次向前走两步。
        • 当 slow 和 fast 相遇时，说明数组中存在环。
      • 第二步：找到环的入口（重复的数字）：
        • 重新将 fast 指针指向数组的起始位置，保持 slow 指针在相遇点。
        • 然后，两者同时每次向前走一步：slow = nums[slow] 和 fast = nums[fast]。
        • 当 slow 和 fast 再次相遇时，相遇的位置就是环的入口，也就是重复的数字。

寻找重复数

  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = 0;
        int slow = 0;
        while(true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow == fast)
                break;
        }
        // 寻找环入口
        fast = 0;
        while(true){
            slow = nums[slow];
            fast = nums[fast];
            if(slow == fast)
                return slow;
        }
        return slow;
    }
};

下一个排列

  • 下一个排列：31.下一个排列
  • 思路：
    • 给定序列 nums，我们寻找“下一个更大”的字典序排列。核心是把序列划分为两部分：
      • 前缀部分：[0 .. i]
      • 候选集合：(i .. end]，即从 i+1 到结尾这一段
    • 这里的 候选集合 是当前后缀中“尽可能小但又足以让整体变大的那一段”，也是一个严格非增序列（从右往左看单调不增），这保证了它已经是该后缀的最大排列。
    • 具体步骤
    1. 定位“转折点” i
      • 从右往左找到第一个满足 nums[i] < nums[i+1] 的位置 i。
      • 若找不到，说明整个数组是非增的，已经是全局最大排列，直接对整个数组升序排序即可（最小排列）。
    2. 在候选集合中选交换对象
      • 候选集合是区间 (i .. end]。在这段里找到第一个大于 nums[i] 且尽可能小的元素与之交换。
      • 由于候选集合从右往左是非增的，从左到右扫描到第一个不大于的位置即可停下；你代码用 k 线性前进，最终交换 k-1，等价于“在候选集合中找刚好比 nums[i] 大的最右元素”。
    3. 重置候选集合为最小排列
      • 交换完成后，候选集合内部仍是“最大排列”形态。为了让整个序列成为“刚好比原序列大、但增幅最小”的排列，需要把候选集合 升序排序（也可写成反转，因为原本是非增的）。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size() == 1)
            return;
        // 找到候选集合中位置交换第一个大于nums[i]的数
        int i;
        for(i=nums.size()-2; i>=0; i--){
            if(nums[i]<nums[i+1]){
                int k=i+1;
                while(k<nums.size()){
                    if(nums[i]>=nums[k])
                        break;
                    k++;
                }
                swap(nums[i], nums[k-1]);
                break;
            }
        }
        // 对候选集合进行排序
        sort(nums.begin()+i+1, nums.end());
    }
};

缺失的第一个正数

  • 缺失的第一个正数：41.缺失的第一个正数
  • 思路：
    • 核心思路：
      • 目标：把数组中值在 [1, n]的元素，放到正确的位置 —— nums[i] = i+1。
        • 比如 1 应该在下标 0；2 应该在下标 1。
      • 放置完成后，只要扫描一遍，找到第一个位置不满足 nums[i] == i+1 的下标，答案就是 i+1。
      • 如果都满足，说明数组包含 [1,2,...,n]，缺失的数是 n+1。
    • 实现步骤：
      • 遍历数组，对每个元素 nums[i]：
        • 如果它在 [1, n] 范围内，并且它没有放到正确的位置，就和目标位置的元素交换。
        • 用 while 而不是 if，因为交换过来的数也可能需要再调整。
      • 遍历调整后的数组：
        • 如果发现 nums[i] != i+1，返回 i+1。
        • 如果全部正确，返回 n+1。
  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i=0; i<n; i++){
	        // nums[i] != nums[nums[i]-1] 避免有两个相等的数陷入死循环
            while(nums[i]>=1 && nums[i]<=n && nums[i] != nums[nums[i]-1]){
                swap(nums[i], nums[nums[i]-1]);
            }
        }
        for(int i=0; i<n; i++){
            if(nums[i] != i+1)
                return i+1;
        }
        return n+1;
    }
};
算法学习
#算法学习
热题100学习笔记
http://example.com/2025/09/07/hot100/
作者
Mr.CHUI
发布于
2025年9月7日
许可协议