热题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;
    }
};

双指针

移动零

  • 移动零：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++;
            }
        }
    }
};

滑动窗口

无重复字符的最长子串

  • 无重复字符的最长子串：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;
    }
};

子串

和为 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;
    }
};

普通数组

轮转数组

  • 轮转数组：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);
    }
};

矩阵

矩阵置零

  • 矩阵置零：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;
            }
        }
    }
};

链表

回文链表

  • 回文链表：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;
    }
};

二叉树

二叉树的直径

  • 二叉树的直径：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;
    }
};

回溯

括号生成

  • 括号生成：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;
    }
};

栈

最小栈

  • 最小栈：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];
    }
};
算法学习
#算法学习
热题100学习笔记
http://example.com/2025/09/07/hot100/
作者
Mr.CHUI
发布于
2025年9月7日
许可协议