LeetCode 热题 100-能不能吃完饭再说

49、字母异位词分组——哈希表、排序

将异位词进行排序后可以得到相同字符串。遍历字符串数组，对每个字符串排序之后存入哈希表，最后将哈希表转化成数组即可。

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> map;
        int cnt=0;
        for(auto str : strs){
            sort(str.begin(), str.end());
            map[str].emplace_back(strs[cnt]);
            cnt++;
        }
        vector<vector<string>> ret;
        for(auto pair : map){
            ret.emplace_back(pair.second);
        }
        return ret;
    }
};

128、最长连续序列和——哈希表、并查集

首先把数组排序，然后对数组进行遍历，记录当前序列的第一个元素set和最后一个元素pre：当遍历到的数字等于pre+1即可以组成序列时，则放入序列并尝试更新max；当数字等于pre，序列不一定在此中断，直接continue，尝试判断后续数字是否符合序列；若非以上两种情况的话，则说明一定被中断，直接设定新的set与pre。

最后返回记录的max中的第一个元素表示最长连续序列长度。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size()==0){
            return 0;
        }
        sort(nums.begin(), nums.end());
        // 存储最大值和最大序列开头数字
        int max[2] = {1, 0};
        // 用于比较是否线性+1
        int pre = nums[0];
        // 当前序列的开头数字
        int set = nums[0];
        // 计数器
        int cnt = 1;
        unordered_map<int, vector<int>> map;
        map[set].emplace_back(set);
        for(int i=1;i<nums.size();i++){
            // 如果符合序列，则放入该集合
            if(nums[i]-1 == pre){
                map[set].emplace_back(nums[i]);
                pre++;
                cnt++;
                if(cnt>max[0]){
                    max[0] = cnt;
                    max[1] = set;
                }
            // 如果与pre相等，但是序列不一定被中断，后面的元素可能符合
            }else if(nums[i] == pre){
                continue;
            }
            // 完全被中断，直接重开
            else{
                cnt=1;
                set=nums[i];
                pre=set;
                map[set].emplace_back(set);
            }
        }
        return max[0];
    }
};

283、移动零——双指针

暴力方法，很简单，但是时间复杂度很高。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int cnt = 0;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==0){
                if(nums.size()-i == cnt){
                    break;
                }
                cnt++;
                int ptr = i;
                i--;
                for(int j=ptr+1;j<nums.size();j++){
                    int tmp = nums[j];
                    nums[j] = nums[ptr];
                    nums[ptr] = tmp;
                    ptr++;
                }
            }
        }
    }
};

优化

使用双指针，左指针指向当前已经处理好的序列的尾部（要么等于右指针要么指向0），右指针指向待处理序列的头部。右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。所以就是将右指针找到的非零数与处理好的序列的尾部0交换。注意到以下性质：

1、左指针左边均为非零数；

2、右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。动画表示如下

——————————————————————————————————

作者：力扣官方题解链接：https://leetcode.cn/problems/move-zeroes/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int n = nums.size(), left = 0, right = 0;
        while (right < n) {
            if (nums[right]) {
                swap(nums[left], nums[right]);
                left++;
            }
            right++;
        }
    }
};

15、三数之和——哈希表、排序、双指针

暴力方法

先排序。然后两层遍历，最后找到哈希表中是否有0-nums[i]-nums[j]这个元素，如果有则组成一对。这种方法好理解，但是性能很差，时间复杂度为O(n^2logn)。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        unordered_map<int, int> map;
        int len = nums.size();
        sort(nums.begin(), nums.end());
        for(int i=0;i<nums.size();i++){
            map[nums[i]] = i;
        }
        vector<vector<int>> ret;
        int cnt=0;
        int i = 0;
        int pre1;
        int pre2;
        do{
            pre1 = nums[i];
            int j=i+1;
            if(j == len){
                break;
            }
            do{
                pre2=nums[j];
                if(map.find(0-nums[i]-nums[j])!=map.end()){
                    int k = map[0-nums[i]-nums[j]];
                    if(k > j){
                        ret.push_back({nums[i], nums[j], nums[k]});
                        cnt++;
                    }
                }
                while(j<len && nums[j] == pre2){
                    j++;
                }
            }while(j<len);
            while(i<len && nums[i] == pre1){
                i++;
            }
        }while(i<len);
        return ret;
    }
};

双指针

优化后的时间复杂度为O(n^2)。首先进行排序，在第一层循环中，使用双指针来寻找符合条件的另外两个数字。

左指针指向i+1，右指针指向最后一个元素，当两个数字和小于target时，由于数组已被排序，则向右移动左指针，如果大于target，则向左移动右指针，如果相等则将这个组合放入结果。要注意避免获取重复的组合。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ret;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;  // 避免重复的组合
            }
            
            int target = -nums[i];
            int left = i + 1;
            int right = n - 1;
            
            while (left < right) {
                int sum = nums[left] + nums[right];
                
                if (sum < target) {
                    left++;
                } else if (sum > target) {
                    right--;
                } else {
                    ret.push_back({nums[i], nums[left], nums[right]});
                    left++;
                    right--;
                    
                    while (left < right && nums[left] == nums[left - 1]) {
                        left++;  // 避免重复的组合
                    }
                    while (left < right && nums[right] == nums[right + 1]) {
                        right--;  // 避免重复的组合
                    }
                }
            }
        }
        
        return ret;
    }
};

20、有效的括号——栈

栈。

class Solution {
public:
    bool isValid(string s) {
        unordered_map<char, int> cps;
        cps['{']=-1;
        cps['}']=1;
        cps['[']=-2;
        cps[']']=2;
        cps['(']=-3;
        cps[')']=3;
        char tmp;
        stack<char> chs;
        for(auto ch:s){
            if(chs.empty()){
                chs.push(ch);
            }else{
                tmp = chs.top();
                if(cps[tmp]+cps[ch]==0 && cps[tmp] < cps[ch]){
                    chs.pop();
                }else{
                    chs.push(ch);
                }
            }
        }
        return chs.empty();
    }
};

3、无重复字符的最长子串——滑动窗口、哈希表

自己写的又臭又烂的代码

两个指针，以一个指针为基指针，另一个指针向后移动，每次移动当移动到的元素不在哈希表中时，则放入哈希表并更新当前窗口大小和最大窗口大小，如果移动到的元素存在哈希表中，则说明这个无重复字符的子串到头了，将基指针移动到重复元素（左边那个）+1的位置继续移动窗口。直到另一个指针移动到了最后一个元素，返回结果。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(!s.size()){
            return 0;
        }
        int ret = 1;
        int left=0, right=0;
        for(;left<s.size();){
            int cnt = 1;
            unordered_map<char, int> exist;
            exist[s[left]] = left;
            right = left+1;
            if(right == s.size()){
                break;
            }
            while(exist.find(s[right])==exist.end()){
                exist[s[right]] = right;
                cnt++;
                right++;
                if(right == s.size()){
                    ret = max(ret, cnt);
                    return ret;
                }
            }
            if(right == s.size()){
                ret = max(ret, cnt);
                return ret;
            }
            left = exist[s[right]]+1;
            ret = max(ret, cnt);
        }
        return ret;
    }
};

GPT的优雅代码

在循环中，首先判断当前右指针指向的字符是否在窗口内。如果不在窗口内，则将该字符加入窗口，更新结果 ret 为当前窗口长度的最大值，然后右指针向右移动一位。如果当前右指针指向的字符已经在窗口内，则需要收缩窗口。将左指针指向的字符从窗口中移除，然后左指针向右移动直到到达那个重复的元素位置。

使用unordered_set 来存储窗口内的字符，上面的代码使用了 unordered_map。在查找元素的过程中，unordered_set 的查找时间复杂度是 O(1)，而 unordered_map 的查找时间复杂度也是 O(1)，但是由于 unordered_map 需要额外存储键和值的对应关系，会引入一些额外的开销，导致性能上的差异。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        if (n == 0) {
            return 0;
        }

        unordered_set<char> window;
        int left = 0, right = 0;
        int ret = 0;

        while (left < n && right < n) {
            if (window.find(s[right]) == window.end()) {
                window.insert(s[right]);
                ret = max(ret, right - left + 1);
                right++;
            } else {
                window.erase(s[left]);
                left++;
            }
        }

        return ret;
    }
};

438、找到字符串中所有字母异位词——滑动窗口

初始化两个哈希表 pchs 和 schs，用于存储字符串 p 中每个字符的出现次数和滑动窗口中当前字符的出现次数。遍历字符串 p，将字符及其出现次数存储到 pchs 哈希表中。使用双指针 left 和 right 表示滑动窗口的左右边界，初始时都指向字符串的第一个位置。

如果字符 ch 在 pchs 哈希表中存在（即为字符串 p 中的字符），则将 schs 哈希表中对应字符的出现次数加1，然后将右指针 right 向右移动一位。如果滑动窗口的长度超过了字符串 p 的长度，即 right - left > plen，则需要将左指针 left 向右移动一位，并更新 schs 哈希表中相应字符的出现次数。如果某个字符的出现次数减少到0，就从 schs 哈希表中移除该键。当滑动窗口的长度等于字符串 p 的长度时，检查 schs 哈希表是否与 pchs 哈希表相等。如果相等，说明当前滑动窗口是一个字母异位词，将左指针 left 存入结果数组 ret 中。如果字符 ch 不在 pchs 哈希表中，表示当前字符不属于字符串 p 的字符，需要重置左指针 left 和右指针 right，并清空 schs 哈希表。

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int left = 0, right = 0;
        unordered_map<char, int> pchs;
        unordered_map<char, int> schs;
        vector<int> ret;
        int len = s.size();
        int plen = p.size();

        // 初始化 pchs 哈希表
        for (auto ch : p) {
            pchs[ch]++;
        }

        while (right < len) {
            // 右指针移动并更新 schs 哈希表
            char ch = s[right];
            if (pchs.find(ch) != pchs.end()) {
                schs[ch]++;
                right++;

                // 当滑动窗口长度超过 p 的长度时，左指针移动并更新 schs 哈希表
                if (right - left > plen) {
                    char leftCh = s[left];
                    schs[leftCh]--;
                    if (schs[leftCh] == 0) {
                        schs.erase(leftCh);
                    }
                    left++;
                }

                // 当滑动窗口长度等于 p 的长度时，检查 schs 哈希表与 pchs 哈希表是否相等
                if (right - left == plen && schs == pchs) {
                    ret.push_back(left);
                }
            } else {
                // 当遇到不在 pchs 哈希表中的字符时，重置左指针和右指针，并清空 schs 哈希表
                left = right + 1;
                right = left;
                schs.clear();
            }
        }
        return ret;
    }
};

56、合并区间——排序

先对数组排序，比较函数使用 lambda 表达式来定义，它接受两个 vector<int> 类型的参数 a 和 b，分别表示两个区间，按照第一个元素升序排序，如果第一个元素相同，则按照第二个元素升序排序。

然后将第一个区间放入ret数组中。遍历 intervals 的区间作为a，并用一个cnt指向ret数组当前的区间b，判断a是否可以和b合并，如果可以合并则更新ret数组当前的区间的最大值，如果不可以则将该区间放入ret中，并将cnt+1继续寻找可以合并到cnt+1指向的区间。

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ret;
        // 按照第一个元素进行升序排序，第一个元素相同则按照第二个元素升序排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[0] == b[0]) {
            return a[1] < b[1];
        }
            return a[0] < b[0];
        });
        // 将第一个区间放入
        int cnt=0;
        ret.push_back(intervals[0]);
        for(int i=1;i<intervals.size();i++){
            // 如果新的区间可以与ret当前的区间合并
            if(intervals[i][0] <= ret[cnt][1]){
                ret[cnt][1] = max(intervals[i][1], ret[cnt][1]);
            }else{
                // 不能合并
                cnt++;
                ret.push_back(intervals[i]);
            }
        }
        return ret;
    }
};

记录：C++11引入了Lambda表达式作为一种语言特性，允许在C++中使用函数式编程的概念。Lambda表达式可以在需要函数对象的地方定义匿名函数，提供了一种简洁的方式来编写内联函数。官方文档C++ 中的 Lambda 表达式

各部分的含义如下：

capture列表：指定Lambda表达式的捕获列表，用于在Lambda表达式内部访问外部变量。可以通过值捕获、引用捕获或混合捕获的方式捕获变量。
参数列表：指定Lambda表达式的参数列表，与普通函数的参数列表类似。
mutable（可选）：指定Lambda表达式是否可以修改捕获的变量，默认情况下，Lambda表达式是不可变的。
异常属性（可选）：指定Lambda表达式抛出异常的属性。
返回类型（可选）：指定Lambda表达式的返回类型，可以根据上下文自动推断出返回类型，也可以显式指定返回类型。
函数体：指定Lambda表达式的实际代码逻辑。

[capture列表] (参数列表) mutable(可选) 异常属性(可选) -> 返回类型(可选) 
{ 
函数体 
}

简单示例

#include <algorithm>
#include <cmath>

void abssort(float* x, unsigned n) {
    std::sort(x, x + n,
        // Lambda expression begins
        [](float a, float b) {
            return (std::abs(a) < std::abs(b));
        } // end of lambda expression
    );
}

图片[2]-LeetCode 热题 100-能不能吃完饭再说

560、和为K的子数组——哈希表、前缀和

走了一点弯路

先把所有前缀和计算，然后存在哈希表中，值为一个数组，表示以此键为前缀和的元素下标数组。

然后开始遍历哈希表，以当前前缀和为右界的前缀和，如果哈希表种存在一个前缀和比该前缀和小k，则说明可能存在和为k的子数组。

然后遍历右界的下标数组，在其中遍历左界的下标数组，如果存在right大于left的情况，则存在一个和为k的子数组

虽然可以过，但是时间复杂度和空间复杂度都很烂🥲

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        int ret = 0;
        unordered_map<int, vector<int>> pre;
        int tmppre = 0;
        pre[tmppre].push_back(0);
        for(int i=0;i<len;i++){
            pre[tmppre+nums[i]].push_back(i+1);
            tmppre += nums[i];
        }
        for(auto& pair:pre){
            if(pre.find(pair.first-k) != pre.end()){
                for(auto& right:pair.second){
                    for(auto& left:pre[pair.first-k]){
                        if(right > left){
                            ret++;
                        }
                    }
                }
            }
        }
        return ret;
    }
};

优化

上面的代码，我们遍历左右界下标数组来判断是否存在right大于left的情况。但是转念一想，我们好像可以在遍历nums数组建立前缀和表的时候存储前缀和的次数，在计算前缀和的过程中统计和为K的子数组数量。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int len = nums.size();
        int ret = 0;
        unordered_map<int, int> pre;
        int tmppre = 0;
        pre[tmppre] = 1;
        for(int i=0;i<len;i++){
            tmppre += nums[i];
            if(pre.find(tmppre-k)!=pre.end()){
                ret += pre[tmppre-k];
            }
            pre[tmppre]++;
        }
        return ret;
    }
};

94、二叉树的中序遍历——二叉树

中序遍历，简单题不说了🤤

/**
 * 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:
    void in(TreeNode* node){
        if(node == nullptr){
            return;
        }
        in(node->left);
        inorder.push_back(node->val);
        in(node->right);
    }

    vector<int> inorderTraversal(TreeNode* root) {
        in(root);
        return inorder;
    }
private:
    vector<int> inorder;
};

189、轮转数组——队列

暴力方法

开辟一个新的空间，存储原来的数组状态，然后进行旋转。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        queue<int> q;
        int len = nums.size();
        for(auto& num:nums){
            q.push(num);
        }
        for(int i=0;i<len;i++){
            int num = q.front();
            q.pop();
            nums[(i+k)%len]  = num;
        }   
    }
};

优化

实际上可以在原本的空间进行操作。

将轮转数组整个过程简化描述，其实就是将最后k个元素移动到前面。简化操作就是先将整个数组反转，然后再单独反转前k个元素和剩余所有元素就能实现将最后k个元素移动到前面。

比如对于[5, 6, 7, 1, 2, 3, 4]，k=3。反转整个向量：[7, 6, 5, 4, 3, 2, 1]，反转前 k 个元素：[5, 6, 7, 4, 3, 2, 1]，反转剩余的 len – k 个元素：[5, 6, 7, 1, 2, 3, 4]。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int len = nums.size();
        k = k % len; // 处理 k 大于 nums 长度的情况

        reverse(nums, 0, len - 1); // 先反转整个向量
        reverse(nums, 0, k - 1); // 再反转前 k 个元素
        reverse(nums, k, len - 1); // 最后反转剩余的元素
    }

private:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start++;
            end--;
        }
    }
};

238、除自身以外数组的乘积——前缀积、后缀积

要求不能用除法，同时时间复杂度为O(n)。

除自身以外数组的乘积即该元素的前缀积与后缀积的乘积，因此先建立前缀积数组。然后从尾部开始遍历数组，并用tmp保存当前元素后缀积。然后计算前缀与后缀的积并放入answer数组。

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> pre;
        int len = nums.size();
        vector<int> answer(len, 0);
        int tmp = 1;
        pre.push_back(1);
        for(int i = 0;i < len;i++){
            tmp = nums[i]*tmp;
            pre.push_back(tmp);
        }
        tmp = 1;
        for(int i = len-1;i>=0;i--){
            answer[i] = pre[i]*tmp;
            tmp = nums[i]*tmp;
        }
        return answer;
    }
};

73、矩阵置零——哈希表

首先遍历整个矩阵，用哈希集合记录需要置零的行和列。然后分别将这些行列置零。

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        unordered_set<int> cols;
        unordered_set<int> rows;
        for(int i=0;i<matrix.size();i++){
            for(int j=0;j<matrix[i].size();j++){
                if(matrix[i][j] == 0){
                    rows.insert(i);
                    cols.insert(j);
                }
            }
        }
        for(auto& row:rows){
            for(int i=0;i<matrix[row].size();i++){
                matrix[row][i] = 0;
            }
        }
        for(auto& col:cols){
            for(int i=0;i<matrix.size();i++){
                matrix[i][col] = 0;
            }
        }
    }
};

54、螺旋矩阵——模拟

使用left、right、top、bottom存储遍历的上下左右边界，然后遍历四条边同时更新上下左右边界。注意在遍历过程中判断是否还有元素可以遍历，避免重复遍历元素。

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> ret;
        if(matrix.empty()){
            return ret;
        }
        int h = matrix.size();
        int w = matrix[0].size();
        int left=0, right=w-1, top=0, bottom=h-1;
        while(left <= right && top <= bottom){
            for(int i=left;i<=right;i++){
                ret.push_back(matrix[top][i]);
            }
            top++;
            for(int i=top;i<=bottom;i++){
                ret.push_back(matrix[i][right]);
            }
            right--;
            if(top <= bottom){
                for(int i=right;i>=left;i--){
                    ret.push_back(matrix[bottom][i]);
                }
                bottom--;
            }
            if(left <= right){
                for(int i=bottom;i>=top;i--){
                    ret.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        return ret;
    }
};

160、相交链表——哈希表

先遍历一个链表，并插入哈希集合。再遍历另一个链表，找到在哈希集合中的第一个元素并返回。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        unordered_set<ListNode*> nodes;
        ListNode *tmp = headA;
        nodes.insert(headA);
        while(tmp->next){
            nodes.insert(tmp->next);
            tmp = tmp->next;
        }
        tmp = headB;
        while (tmp) {
            if (nodes.find(tmp) != nodes.end()) {
                return tmp;
            }
            tmp = tmp->next;
        }
        return nullptr;
    }
};

48、旋转图像

相通了就很简单，一个矩阵旋转顺时针旋转90°，即先将矩阵转置在将每一行水平翻转即可。

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        // 对矩阵转置
        for(int i=0;i<matrix.size();i++){
            for(int j=i+1;j<matrix[i].size();j++){
                swap(matrix[i][j], matrix[j][i]);
            }
            reverse(matrix[i].begin(), matrix[i].end());
        }
    }
};

240、搜索二维矩阵Ⅱ——二分查找

第一次二分查找找到target可能存在的行的范围，第二次遍历这些行并使用二分法查找其中的target。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int len = matrix.size();
        int potential_row;
        int left = 0, right = len-1;
        while(left <= right){
            int mid = (left+right)/2;
            if(matrix[mid][0] > target){
                right = mid-1;
            }else if(matrix[mid][0] < target){
                left = mid+1;
            }else{
                return true;
            }
        }
        potential_row = left;
        len = matrix[0].size();
        for(int i=0;i<potential_row;i++){
            auto it = lower_bound(matrix[i].begin(), matrix[i].end(), target);
            if(it != matrix[i].end() && *it == target){
                return true;
            }
        }
        return false;
    }
};

234、回文链表——递归、双指针

双指针

先存储原链表的内容，然后递归反转链表，最后遍历新链表和原链表内容，判断是否为回文链表。

这里可以不用反转链表，直接从原链表内容的最后开始往前移动，但是不知道为什么这种方法比先反转时间更长。

/**
 * 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* reverseList(ListNode* node) {
        if(node == nullptr || node->next == nullptr){
            return node;
        }
        ListNode* tmp = reverseList(node->next);
        node->next->next = node;
        node->next = nullptr;
        return tmp;
    }

    bool isPalindrome(ListNode* head) {
        ListNode* tmp = head;
        vector<int> raw_list;
        while(tmp != nullptr){
            raw_list.push_back(tmp->val);
            tmp = tmp->next;
        }
        head = reverseList(head);
        tmp = head;
        int cnt=0;
        while(tmp != nullptr){
            if(tmp->val != raw_list[cnt]){
                return false;
            }
            tmp = tmp->next;
            cnt++;
        }
        return true;
    }
};

递归

定义了一个辅助指针 frontPointer，用于记录链表的当前前向节点。然后，使用递归函数 recursivelyCheck() 来检查链表是否为回文。

1、如果当前节点不为空，首先递归调用 recursivelyCheck() 函数，传入当前节点的下一个节点，并检查返回值是否为 false。如果不是回文，则直接返回 false。

2、如果当前节点的值与 frontPointer 节点的值不相等，则返回 false。

3、将 frontPointer 指针指向下一个节点，以便继续与后续节点比较

/**
 * 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* frontPointer;
public:
    bool recursivelyCheck(ListNode* currentNode) {
        if (currentNode != nullptr) {
            if (!recursivelyCheck(currentNode->next)) {
                return false;
            }
            if (currentNode->val != frontPointer->val) {
                return false;
            }
            frontPointer = frontPointer->next;
        }
        return true;
    }

    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

141、环形链表——哈希表

遍历链表，如果节点在哈希表中，则说明存在环，返回true，否则将指针插入哈希集合。最后如果没找到环返回false。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode *> vistited;
        ListNode *tmp = head;
        while(tmp != nullptr){
            if(vistited.find(tmp) != vistited.end()){
                return true;
            }
            vistited.insert(tmp);
            tmp = tmp->next;
        }
        return false;
    }
};

21、合并两个有序链表——链表、双指针

判断其中一个链表是否为空来处理特殊情况。如果list1为空，则直接返回list2；如果list2为空，则直接返回list1。

在每次循环中，通过比较list1和list2当前节点的值的大小，来确定下一个节点的指向。如果list1的当前节点值小于等于list2的当前节点值，那么将tmp的下一个节点指向list1的当前节点，并将list1指向下一个节点；否则，将tmp的下一个节点指向list2的当前节点，并将list2指向下一个节点。然后，更新tmp为其下一个节点。

在每次循环的末尾，检查list1和list2是否有一个已经遍历完（即为nullptr），如果有，则将tmp的下一个节点指向未遍历完的链表，然后退出循环。

最后，返回newHead的下一个节点，即为合并后的链表的头节点。时间复杂度为O(m+n)，其中m和n分别为两个链表的长度。

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr){
            return list2;
        }else if(list2 == nullptr){
            return list1;
        }
        ListNode* newHead = new ListNode();
        ListNode* tmp = newHead;
        while(true){
            if(list1->val <= list2->val){
                tmp->next = list1;
                list1 = list1->next;
            }else{
                tmp->next = list2;
                list2 = list2->next;
            }
            tmp = tmp->next;
            if(list1 == nullptr){
                tmp->next = list2;
                break;
            }else if(list2 == nullptr){
                tmp->next = list1;
                break;
            }
        }
        return newHead->next;
    }
};

19、删除链表的第N个节点——双指针

两次扫描

两次遍历删除倒数第N个节点

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* node = head;
        int cnt = 0;
        while(node!=nullptr){
            node = node->next;
            cnt++;
        }
        node = head->next;
        ListNode* pre = head;
        int cur=1;
        // 如果要删除第一个
        if(n == cnt){
            delete head;
            head = nullptr;
            return node;
        }
        while(node!=nullptr){
            if(cur == cnt-n){
                pre->next = node->next;
                delete node;
                node = nullptr;
                break;
            }
            pre = pre->next;
            node = node->next;
            cur++;
        }
        return head;
    }
};

一次扫描

先让fast指针移动n步，然后fast和last指针一起移动直到fast指针移动到末尾，那样last指针就指向要删除节点的前一节点了。

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode();
        dummy->next = head;
        
        ListNode* fast = dummy;
        ListNode* slow = dummy;

        // 将 fast 指针向前移动 n 步
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }
        // 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* delnode = slow->next;
        slow->next = slow->next->next;
        ListNode* result = dummy->next;

        delete delnode;
        delete dummy;
        
        return result;
    }
};

24、两两交换链表中的节点——递归

函数首先检查当前节点的下一个节点是否为空，如果为空，则表示当前节点是链表的最后一个节点，无需进行交换，直接返回。接着，函数创建一个指针nx指向当前节点的下一个节点。然后，它检查nx的下一个节点是否为空，如果为空，则表示nx是链表的最后一个节点，即当前节点是倒数第二个节点，这是最后一对节点。在这种情况下，进行节点交换操作，将node的下一个节点指针指向nx的下一个节点，将nx的下一个节点指针指向node，完成节点交换。如果nx的下一个节点不为空，则说明还有至少两个节点需要交换。在这种情况下，函数根据节点的奇偶性来更新node的下一个节点指针，然后递归调用SwitchNode函数，传入nx的下一个节点作为参数。最后，将nx的下一个节点指针指向node，完成节点交换。

/**
 * 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:
    void SwitchNode(ListNode* node){
        if(node->next == nullptr){
            return;
        }
        ListNode* nx = node->next;
        if(nx->next == nullptr){
            node->next = nx->next;
            nx->next = node;
        }else{
            // 下一对为后偶数
            if(nx->next->next != nullptr){
                node->next = nx->next->next;
            }else{
                // 奇数
                node->next = nx->next;
            }
            SwitchNode(nx->next);
            nx->next = node;
        }
    }

    ListNode* swapPairs(ListNode* head) {
        if(head == nullptr){
            return nullptr;
        }else if(head->next == nullptr){
            return head;
        }
        ListNode* ret = head->next;
        SwitchNode(head);
        return ret;
    }
};

148、排序链表——归并排序、递归、分治、双指针

首先，检查链表是否为空或只包含一个节点。如果是，直接返回原链表，因为它已经是有序的。使用快慢指针将链表分成两部分。快指针每次移动两步，慢指针每次移动一步，直到快指针到达链表尾部时，慢指针指向链表的中间节点。然后递归调用对左右两个链表进行排序，排序后对左右两个链表进行归并排序。

/**
 * 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) {
        // 0节点或1节点，直接返回
        if(head==nullptr || head->next == nullptr){
            return head;
        }
        // 快慢节点
        ListNode* last = head;
        ListNode* fast = head->next;
        while(fast != nullptr && fast->next != nullptr){
            last = last->next;
            fast = fast->next->next;
        }
        // 将链表分为左右两个链表
        ListNode* rightHead = last->next;
        last->next = nullptr;
        // 对左右两个链表排序
        ListNode* sortLeft = sortList(head);
        ListNode* sortRight = sortList(rightHead);
        // 进行归并排序
        ListNode* dummy = new ListNode();
        ListNode* cur = dummy;
        while(sortLeft != nullptr && sortRight != nullptr){
            if(sortLeft->val <= sortRight->val){
                cur->next = sortLeft;
                sortLeft = sortLeft->next;
            }else{
                cur->next = sortRight;
                sortRight = sortRight->next;
            }
            cur = cur->next;
        }
        // 处理剩余节点
        if (sortLeft != nullptr) {
            cur->next = sortLeft;
        }
        if (sortRight != nullptr) {
            cur->next = sortRight;
        }
        return dummy->next;
    }
};

226、翻转二叉树——递归

首先简化问题，翻转一个二层的满二叉树，那么就是交换根节点的左右子节点，三层的满二叉树就是先对根节点的左右子节点进行对二层满二叉树的操作之后再交换左右子树，以此类推。

所以可以使用递归，首先检查根节点是否为空，如果为空，则直接返回 nullptr。如果根节点是叶节点（即左右子节点都为空），则直接返回根节点。然后递归调用函数翻转左右子树，再交换左右子树的位置。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        // 根节点为空
        if(root == nullptr){
            return nullptr;
        // 为叶节点 
        }else if(root->left == nullptr && root->right == nullptr){
            return root;
        }
        // 分别翻转左右子树
        invertTree(root->left);
        invertTree(root->right);
        TreeNode* tmp = root->left;
        root->left = root->right;
        root->right = tmp;
        return root;
    }
};

101、对称二叉树——递归

迭代

使用层序遍历的思想来逐层检查二叉树的对称性。使用队列 q 来进行层序遍历。将根节点入队。然后，定义一个变量 levelSize 来表示当前层的节点数，初始值为 1。定义了一个指向 nullptr 的指针 nullNode，用于表示空节点。

接下来，进入一个循环，直到队列为空。在每次循环中，创建一个空的 vector<int>，用于存储当前层的节点值。然后，遍历当前层的节点数，从队列中取出节点。如果当前节点为空，即为 nullptr，则将 INT_MIN 存入 level 中，并将两个空节点（nullNode）入队，表示当前节点的左右子节点为空。如果当前节点不为空，则将其值存入 level 中，并将其左右子节点入队。

在遍历完当前层的节点后，检查 level 是否对称。使用双指针的方式，从两端向中间遍历，如果发现值不相等，则二叉树不对称，直接返回 false。然后，检查当前层是否全为空节点，即所有节点的值都为 INT_MIN。如果是，则认为二叉树已经检查完毕，没有更多的层需要遍历，跳出循环。最后，将 levelSize 乘以 2，以准备遍历下一层。

不过是很蠢的办法😓

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        queue<TreeNode*> q;
        q.push(root);
        int levelSize = 1;
        TreeNode* nullNode = nullptr;
        while (!q.empty()) {
            vector<int> level(levelSize);
            for (int i = 0; i < levelSize; i++) {
                TreeNode* current = q.front();
                q.pop();
                if(current == nullptr){
                    level[i] = INT_MIN;
                    q.push(nullNode);
                    q.push(nullNode);
                    continue;
                }
                level[i] = current->val;
                if (current->left != nullptr) {
                    q.push(current->left);
                }else{
                    q.push(nullNode);
                }
                if (current->right != nullptr) {
                    q.push(current->right);
                }else{
                    q.push(nullNode);
                }
            }
            bool q = true;
            for(int i = 0; i < (levelSize+1)/2; i++){
                if(level[i] != INT_MIN){
                    q=false;
                }
                if(level[i] != level[levelSize-i-1]){
                    return false;
                }
            }
            if(q){
                break;
            }
            levelSize *= 2;
        }
        return true;
    }
};

递归

isSymmetricHelper，该函数接受两个节点指针 left 和 right，用于递归判断左右子树的对称性。

在 isSymmetricHelper 函数内部，首先进行了两个节点的判空情况的判断。如果左节点和右节点均为空，说明当前层对称，返回 true。如果左节点或右节点有一个为空，说明当前层不对称，返回 false。接下来，比较左右节点的值是否相等。如果不相等，说明当前层不对称，返回 false。

递归调用 isSymmetricHelper 函数判断左节点的左子树和右节点的右子树是否对称，以及左节点的右子树和右节点的左子树是否对称。如果两个子树均对称，返回 true，否则返回 false。

/**
 * 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:
    bool isSymmetric(TreeNode* root) {
        if (root == nullptr) {
            return true;
        }
        return isSymmetricHelper(root->left, root->right);
    }

private:
    // 判断左右子树是否相等
    bool isSymmetricHelper(TreeNode* left, TreeNode* right) {
        if (left == nullptr && right == nullptr) {
            return true;
        }
        if (left == nullptr || right == nullptr) {
            return false;
        }
        // 树的根节点相等
        // 左树的左子树与右树的右子树相等
        // 左树的右子树与右树的左子树相等
        return (left->val == right->val) &&
               isSymmetricHelper(left->left, right->right) &&
               isSymmetricHelper(left->right, right->left);
    }
};

142、环形链表Ⅱ——哈希表

遍历链表，如果节点在哈希表中，则说明存在环，返回该节点，否则将指针插入哈希集合。最后如果没找到环返回null。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        unordered_set<ListNode *> vistited;
        ListNode *tmp = head;
        while(tmp != nullptr){
            if(vistited.find(tmp) != vistited.end()){
                return tmp;
            }
            vistited.insert(tmp);
            tmp = tmp->next;
        }
        return nullptr;
    }
};

543、二叉树的直径——递归

deep 函数是一个递归函数，用于计算以当前节点为根节点的子树的深度，并更新直径的值。函数首先判断当前节点是否为空，如果为空则返回深度 0。然后判断当前节点是否为叶子节点，即左右子节点都为空，如果是则返回深度 1。如果当前节点不是叶子节点，则递归计算左子树和右子树的深度，并将左子树深度和右子树深度相加，与当前的最大直径进行比较，更新最大直径的值。最后，返回左子树深度和右子树深度中的较大值加 1，即当前根节点的子树的深度。

/**
 * 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 deep(TreeNode* root){
        if(root == nullptr){
            return 0;
        }
        if(root->left == nullptr && root->right == nullptr){
            return 1;
        }
        int left = deep(root->left);
        int right = deep(root->right);
        max = left+right>max?left+right:max;
        int ret = left>right?left:right;
        return ret+1;
    }
    int diameterOfBinaryTree(TreeNode* root) {
        int ret = deep(root);
        return max;
    }
private:
    int max = 0;
};

102、二叉树的层序遍历——队列

创建一个队列 node_queue，并将根节点入队。

进入循环，判断队列是否为空。如果队列不为空，说明还有节点需要遍历。在每一轮循环中，首先获取当前层的节点数量 level_size，这是为了在每一层结束后创建一个新的层向量。

然后，创建一个一维向量 level，用于存储当前层的节点值。

接下来，通过循环遍历当前层的节点。在循环中，从队列中取出一个节点 cur，将其值存储到当前层的向量 level 的对应位置。然后，如果当前节点的左子节点不为空，将其左子节点入队。如果当前节点的右子节点不为空，将其右子节点入队。

完成当前层的遍历后，将存储当前层节点值的向量 level 插入结果向量 ret 中。

重复以上步骤，直到队列为空，即二叉树的所有节点都遍历完毕。

/**
 * 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<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ret;
        if (root == nullptr) {
            return ret;
        }
        queue<TreeNode*> node_queue;
        node_queue.push(root);
        while(!node_queue.empty()){
            int level_size = node_queue.size();
            vector<int> level(level_size);
            for(int i=0;i<level_size;i++){
                TreeNode* cur = node_queue.front();
                node_queue.pop();
                level[i] = cur->val;
                if(cur->left != nullptr){
                    node_queue.push(cur->left);
                }
                if(cur->right != nullptr){
                    node_queue.push(cur->right);
                }

            }
            ret.push_back(level);
        }
        return ret;
    }
};

138、随机链表的复制——哈希表、深拷贝

深拷贝与浅拷贝

使用了两个哈希映射，node_map和re_node_map，用于建立原始节点与复制节点之间的映射关系。在DeepCopy函数中，通过传入一个节点other，创建一个新的节点node，并将其值初始化为other节点的值。然后，将other节点和node节点作为键值对分别存储在node_map和re_node_map中，以便后续根据原始节点查找对应的复制节点。

遍历原始链表，对于每个节点cur，通过调用DeepCopy函数复制节点，并将复制节点连接到复制链表的末尾。同时，更新cur和tmp指针指向下一个节点。

接下来，再次遍历复制链表，对于每个复制节点tmp，根据re_node_map找到对应的原始节点，并根据random指针的映射关系，设置复制节点的random指针指向正确的节点。

最后，返回复制链表的头节点dummy->next。

/*
// 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* DeepCopy(Node* other){
        Node* node = new Node(other->val);
        node_map[other] = node;
        re_node_map[node] = other;
        return node;
    }
    Node* copyRandomList(Node* head) {
        Node* cur = head;
        Node* dummy = new Node(-1);
        Node* tmp = dummy;
        while(cur != nullptr){ 
            tmp->next = DeepCopy(cur);
            cur = cur->next;
            tmp = tmp->next;
        }
        tmp = dummy->next;
        while(tmp != nullptr){
            tmp->random = node_map[re_node_map[tmp]->random];
            tmp = tmp->next;
        }
        return dummy->next;
    }
private:
    unordered_map<Node*, Node*> node_map;
    unordered_map<Node*, Node*> re_node_map;
};

108、将有序数据转换为平衡二叉搜索树——递归、分治、AVL树

在 insertAVLTree 函数中，通过递归的方式，将有序数组分为左右两部分，并选取中间元素作为根节点，然后构建左子树和右子树。在构建过程中，调用 insertNode 函数插入节点到二叉搜索树中。

insertNode 函数用于将节点插入到二叉搜索树中的正确位置。它按照节点的值大小进行比较，如果节点的值比当前节点大，则进入右子树；如果节点的值比当前节点小，则进入左子树。直到找到合适的位置插入节点。

/**
 * 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:
    void insertNode(TreeNode* node){
        TreeNode* cur = root;
        if(cur == nullptr){
            root = node;
            return;
        }
        while(true){
            if(node->val > cur->val){
                if(cur->right == nullptr){
                    cur->right = node;
                    return;
                }
                cur = cur->right;
            }else if(node->val < cur->val){
                if(cur->left == nullptr){
                    cur->left = node;
                    return;
                }
                cur = cur->left;
            }else{
                return;
            }
        }
    }

    void insertAVLTree(vector<int>& nums, int begin, int end){
        if(begin > end){
            return;
        }
        int mid = (begin + end)/2; 
        TreeNode* node = new TreeNode(nums[mid]);
        insertNode(node);
        if(begin == end){
            return;
        }
        insertAVLTree(nums, begin, mid-1);
        insertAVLTree(nums, mid+1, end);
    }

    TreeNode* sortedArrayToBST(vector<int>& nums) {
        insertAVLTree(nums, 0, nums.size() - 1);
        return root;
    }
private:
    TreeNode* root;
};

98、验证二叉搜索树——二叉树、中序遍历

中序遍历二叉树，然后判断是否为递增的有序数组。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<int> nums;
    void inorderTravel(TreeNode* root){
        if(root == nullptr){
            return;
        }
        inorderTravel(root->left);
        nums.push_back(root->val);
        inorderTravel(root->right);
    }
    bool isValidBST(TreeNode* root) {
        inorderTravel(root);
        for(int i=1;i<nums.size();i++){
            if(nums[i] <= nums[i-1]){
                return false;
            }
        }
        return true;
    }
};

230、二叉搜索树中第K小的元素——中序遍历

首先检查当前节点是否为空，如果为空则返回。然后它递归地调用自身来处理当前节点的左子树。接着，它增加计数器cnt的值，表示已经遍历过一个节点。如果计数器的值等于k，说明找到了第k个节点，将当前节点的值记录在变量find中。最后，getNum函数再递归地处理当前节点的右子树。

最后，kthSmallest函数返回变量find，即第k小的元素的值。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int cnt=0;
    int find;
    void getNum(TreeNode* root, int k){
        if(root == nullptr){
            return;
        }
        getNum(root->left, k);
        cnt++;
        if(cnt == k){
            find=root->val;
        }
        getNum(root->right, k);
    }
    int kthSmallest(TreeNode* root, int k) {
        getNum(root, k);
        return find;
    }
};

199、二叉树的右视图——层次遍历

vector<int> right，用于存储右视图的节点值序列。

实现右视图的关键在于使用层序遍历（广度优先搜索）算法来遍历二叉树。具体而言，代码中的 levelTravel 函数使用队列来进行层序遍历。首先将根节点入队，然后在每一层中依次处理每个节点，并将其左右子节点（如果存在）入队。在每一层的最后一个节点处，将该节点的值加入到 right 向量中，即为右视图的节点值。

在 rightSideView 函数中，首先判断根节点是否为空。如果为空，则直接返回 right 向量。否则，调用 levelTravel 函数对二叉树进行层序遍历，并返回 right 向量作为右视图的结果。

/**
 * 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> right;
    void levelTravel(TreeNode* root){
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int levelSize = q.size();
            for (int i = 0; i < levelSize; i++) {
                TreeNode* current = q.front();
                if(i == levelSize - 1){
                    right.push_back(current->val);
                }
                q.pop();
                if (current->left != nullptr) {
                    q.push(current->left);
                }
                if (current->right != nullptr) {
                    q.push(current->right);
                }
            }
        }
    }

    vector<int> rightSideView(TreeNode* root) {
        if(root == nullptr){
            return right;
        }
        levelTravel(root);
        return right;
    }
};

114、二叉树展开为链表——深度优先搜索

递归，先将左子树展开成单链表，再将右子树展开成单链表。然后将展开后的左子树插入到根节点和展开后的右子树之间。

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

105、从前序与中序遍历序列构造二叉树——分治、递归

在前序遍历序列中，第一个元素即根节点，然后对于中序遍历序列，根节点左边的元素为左子树的中序遍历，右边的元素为右子树的中序遍历。所有整体思路是，在中序遍历序列找到根节点位置，然后得到根节点的左子树的中序遍历序列和右子树的中序遍历序列，再根据根节点位置分割前序遍历序列得到左子树的前序遍历序列和右子树的前序遍历序列，再递归构造左右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* Build(vector<int>& preorder, int bg1, int ed1, vector<int>& inorder,  int bg2, int ed2)
    {
        if (bg1 >= ed1 || bg2 >= ed2) {
            return nullptr;
        }
        TreeNode* root = new TreeNode(preorder[bg1]);
        int mid = find(inorder.begin(), inorder.end(), preorder[bg1]) - inorder.begin();
        root->left = Build(preorder, bg1 + 1, bg1 + 1 + mid - bg2, inorder, bg2, mid);
        root->right = Build(preorder, bg1 + 1 + mid - bg2, ed1, inorder, mid + 1, ed2);
        return root;
    }
    
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        return Build(preorder, 0, preorder.size(), inorder, 0, inorder.size());
    }
};

437、路径总和 Ⅲ——深度优先搜索

在 dfs 函数中，首先检查当前节点是否为空，若为空则直接返回。创建一个新的数组 new_pre，并将当前节点的值添加到 new_pre 中。如果当前节点的值等于目标和 targetSum，则将 ret 自增 1。遍历数组 pre，计算当前节点值与 pre 数组中的每个元素相加的结果，结果等于目标和 targetSum，则将 ret 自增 1。并将结果添加到 new_pre 中。

递归调用 dfs 函数，传入左子节点、new_pre 和 targetSum，继续搜索左子树。

递归调用 dfs 函数，传入右子节点、new_pre 和 targetSum，继续搜索右子树。

/**
 * 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 ret = 0;
    void dfs(TreeNode* root, vector<long>& pre, int targetSum){
        if(root == nullptr){
            return;
        }
        vector<long> new_pre;
        new_pre.push_back(root->val);
        if(root->val == targetSum){
            ret++;
        }
        for(auto& num:pre){
            long tmp = num + root->val;
            if(tmp == targetSum){
                ret++;
            }
            new_pre.push_back(num+root->val);
        }
        dfs(root->left, new_pre, targetSum);
        dfs(root->right, new_pre, targetSum);
    }

    int pathSum(TreeNode* root, int targetSum) {
        vector<long> pre;
        dfs(root, pre, targetSum);
        return ret;
    }
};

236、二叉树的最近公共祖先——深度优先搜索

如果当前节点 root 是空节点或者等于 pv 或 qv 中的任意一个节点的值，那么当前节点就是该元素的最近祖先或者为nullptr，直接返回当前节点。

递归地在左子树中查找 pv 和 qv 的最近公共祖先，得到结果 left。递归地在右子树中查找 pv 和 qv 的最近公共祖先，得到结果 right。

如果 left 和 right 都不为空，说明 pv 和 qv 分别位于当前节点的左右子树中，那么当前节点就是最近公共祖先，直接返回当前节点。

如果 left 不为空，说明 pv 和 qv 都在左子树中，那么结果为 left。

如果 right 不为空，说明 pv 和 qv 都在右子树中，那么结果为 rightt。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* dfs(TreeNode* root, int pv, int qv){
        if (root == nullptr || root->val == pv || root->val == qv) {
            return root;
        }
        TreeNode *left = dfs(root->left, pv, qv);
        TreeNode *right = dfs(root->right, pv, qv);
        if (left != nullptr && right != nullptr) {
            return root;
        } else if (left != nullptr) {
            return left;
        } else {
            return right;
        }
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return dfs(root, p->val, q->val);
    }
};

994、腐烂的橘子——广度优先搜索、队列

首先遍历整个网格，如果遇到腐烂的橘子，将其位置加入队列q；如果遇到新鲜的橘子，将新鲜橘子的数量fresh加1。如果fresh的值为0，表示初始状态下没有新鲜的橘子，直接返回0。定义一个方向数组directions，用于表示四个方向上的移动。接下来进入主循环，直到队列q为空。在每次循环中，首先获取当前队列的大小edge_size，表示当前分钟需要处理的腐烂橘子的数量。然后，依次处理队列中的腐烂橘子。从队列中取出一个橘子的位置pos，获取其坐标(m, n)。接下来，根据方向数组directions，将当前橘子的上下左右四个方向上的橘子状态进行检查。如果邻居位置在网格范围内，并且是新鲜的橘子（状态为1），则将其状态改为腐烂（状态为2），并将新鲜橘子数量fresh减1。同时，将新腐烂橘子的位置加入队列q，以便下一轮处理。完成当前分钟的处理后，分钟数minutes加1。

class Solution
{
public:
    int orangesRotting(vector<vector<int>> &grid)
    {
        int h = grid.size();
        int w = grid[0].size();
        queue<pair<int, int>> q;
        int minutes = -1;
        int fresh = 0;
        for (size_t i = 0; i < h; i++)
        {
            for (size_t j = 0; j < w; j++)
            {
                if (grid[i][j] == 2)
                {
                    q.push({i, j});
                }
                else if (grid[i][j] == 1)
                {
                    fresh++;
                }
            }
        }
        if (fresh == 0)
        {
            return 0;
        }
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (!q.empty())
        {
            int edge_size = q.size();
            for (size_t i = 0; i < edge_size; i++)
            {
                pair<int, int> pos = q.front();
                q.pop();
                int m = pos.first;
                int n = pos.second;
                for (const auto &dir : directions)
                {
                    int nm = m + dir.first;
                    int nn = n + dir.second;

                    if (nm >= 0 && nm < h && nn >= 0 && nn < w && grid[nm][nn] == 1)
                    {
                        grid[nm][nn] = 2;
                        fresh--;
                        q.push({nm, nn});
                    }
                }
            }
            minutes++;
        }

        return fresh == 0 ? minutes : -1;
    }
};

207、课程表——拓扑排序、深度优先搜索

首先根据输入的先修课程信息构建依赖关系图和入度数组。然后找到所有入度为0的课程作为起始节点，对每个起始节点进行深度优先搜索，将搜索过的课程标记为已访问，并更新相关课程的入度。如果最终所有课程的入度都为0，说明课程安排是合理的，返回true；否则，返回false。

class Solution
{
public:
    void dfs(vector<vector<int>> &g, vector<int> &indegree,
             vector<int> &visited, int i)
    {
        visited[i] = 1;
        for (auto course : g[i])
        {
            indegree[course]--;
            if (visited[course] == 0 && indegree[course] == 0)
            {
                dfs(g, indegree, visited, course);
            }
        }
    }
    bool canFinish(int numCourses,
                   vector<vector<int>> &prerequisites)
    {
        vector<vector<int>> g(numCourses);
        vector<int> indegree(numCourses, 0);
        vector<int> visited(numCourses, 0);
        for (auto &p : prerequisites)
        {
            g[p[1]].push_back(p[0]);
            indegree[p[0]]++;
        }
        vector<int> start;
        for (size_t i = 0; i < numCourses; i++)
        {
            if (indegree[i] == 0)
            {
                start.push_back(i);
            }
        }
        if (start.size() == 0)
        {
            return false;
        }
        for (auto &course : start)
        {
            dfs(g, indegree, visited, course);
        }
        int tmp = numCourses;
        for (size_t i = 0; i < numCourses; i++)
        {
            if (indegree[i] == 0)
            {
                tmp--;
            }
        }
        return tmp == 0 ? true : false;
    }
};

208、实现 Tire （前缀树）——前缀树

首先介绍一下前缀树：

当提到前缀树（Prefix Tree），也称为字典树（Trie），它是一种特殊的树状数据结构，用于高效地存储和检索字符串集合。前缀树的设计主要用于处理字符串的前缀匹配问题，例如单词的自动补全、拼写检查和搜索引擎中的关键字搜索等。

前缀树的主要特点是将每个字符串拆分为字符序列，并将其存储在树的节点中。树的根节点不包含任何字符，而是具有多个子节点，每个子节点分别代表可能的字符。通过从根节点开始，沿着路径逐个字符地遍历树，我们可以找到存储在树中的字符串。

下面是一个示例，展示了存储了一些字符串的前缀树：

root
                /    \
               a      b
              / \      \
             p   r      y
            /   / \      \
           p   e   o      e
          /   /     \      \
         l   a       w      s
        /   /         \      \
       e   t           e      t
      /   /             \      \
         t               r

在这个示例中，我们存储了字符串 “apple”、”apricot”、”banana”、”bat” 和 “bee”。根节点没有存储任何字符，而是有两个子节点 “a” 和 “b”，分别代表字符串的第一个字符可能是 “a” 或 “b”。沿着 “a” 的路径，我们可以找到 “apple”、”apricot” 和 “banana”，而沿着 “b” 的路径，我们可以找到 “bat” 和 “bee”。

前缀树的一个重要特性是，它可以高效地执行前缀匹配操作。对于给定的前缀字符串，我们可以在树中沿着相应的路径进行遍历，直到遇到无法继续匹配的节点或者遍历完整个前缀。这样，我们就能找到所有具有相同前缀的字符串。

前缀树还可以用于实现其他功能，例如计算字符串的频率、按照字典序遍历字符串集合等。它是一种非常有用的数据结构，特别适用于需要高效处理字符串集合的问题。

前缀树的节点使用了一个结构体 TrieNode 来表示，其中包含了一个布尔值 isWord，表示该节点是否为一个完整的单词，以及一个哈希表 children，用于存储子节点。树的根节点通过 root 指针进行访问。

构造函数 Trie() 用于创建一个空的前缀树，其中根节点的 isWord 初始化为 false。

插入操作使用 insert(string word) 方法，它从根节点开始遍历字符串的每个字符，检查是否存在对应的子节点。如果不存在，则创建一个新的子节点，并根据当前字符的位置判断是否标记为一个完整的单词。然后，将当前节点指向新的子节点，继续遍历下一个字符，直到遍历完整个字符串。

搜索操作使用 search(string word) 方法，它从根节点开始遍历字符串的每个字符，并检查是否存在对应的子节点。如果遇到不存在的子节点，则说明该字符串不存在于前缀树中，返回 false。如果遍历完整个字符串后，最后访问的节点的 isWord 为 true，则说明该字符串存在于前缀树中，返回 true。

前缀匹配操作使用 startsWith(string prefix) 方法，它与搜索操作类似，从根节点开始遍历前缀字符串的每个字符，并检查是否存在对应的子节点。如果遇到不存在的子节点，则说明前缀不存在于前缀树中，返回 false。如果遍历完整个前缀字符串后，没有遇到不存在的子节点，说明前缀存在于前缀树中，返回 true。

class Trie
{
private:
    struct TrieNode
    {
        bool isWord;
        unordered_map<char, TrieNode *> children;
        TrieNode()
        {
            isWord = false;
        }
        TrieNode(bool isw)
        {
            isWord = isw;
        }
    };
    TrieNode *root;

public:
    Trie()
    {
        root = new TrieNode();
    }

    void insert(string word)
    {
        TrieNode *node = root;
        for (size_t i = 0; i < word.length(); i++)
        {
            if (node->children.find(word[i]) == node->children.end())
            {
                node->children[word[i]] = new TrieNode(i == word.length() - 1);
            }
            else if (i == word.length() - 1)
            {
                node->children[word[i]]->isWord = true;
            }
            node = node->children[word[i]];
        }
    }

    bool search(string word)
    {
        TrieNode *node = root;
        for (size_t i = 0; i < word.length(); i++)
        {
            if (node->children.find(word[i]) == node->children.end())
            {
                return false;
            }
            else
            {
                node = node->children[word[i]];
            }
        }
        return node->isWord;
    }

    bool startsWith(string prefix)
    {
        TrieNode *node = root;
        for (size_t i = 0; i < prefix.length(); i++)
        {
            if (node->children.find(prefix[i]) == node->children.end())
            {
                return false;
            }
            else
            {
                node = node->children[prefix[i]];
            }
        }
        return true;
    }
};

46、全排列——回溯

整个算法使用递归的方式进行回溯。在 backtrack 函数中，有两个关键步骤：

结束条件：当组合 tmp 的长度达到数组的长度 n 时，说明已经生成了一个完整的排列组合，将其添加到结果 res 中，并返回。
递归调用：遍历数组 nums 的元素，在每一次迭代中，判断当前元素是否已经在组合 tmp 中，如果没有出现过，则将其加入 tmp 中，并继续递归调用 backtrack 函数。这样可以保证生成的组合中不会有重复的元素。

在递归调用之后，需要进行回溯操作，即将 tmp 中最后一个加入的元素移除，以便继续尝试其他的选择。

最后，调用 permute 函数时，传入原始的数组 nums 以及结果集合 res 和临时组合 tmp，并返回最终的结果 res。

class Solution
{
public:
    void backtrack(vector<int> &nums, vector<vector<int>> &res,
                   vector<int> &tmp, int n)
    {
        // 最后一个元素
        if (tmp.size() == n)
        {
            res.push_back(tmp);
            return;
        }
        else
        {
            for (size_t i = 0; i < n; i++)
            {
                // 如果这个元素没有被放入组合
                if (find(tmp.begin(), tmp.end(), nums[i]) == tmp.end())
                {
                    // 放入组合
                    tmp.push_back(nums[i]);
                    // 递归
                    backtrack(nums, res, tmp, n);
                    // 回溯
                    tmp.pop_back();
                }
            }
        }
    }

    vector<vector<int>> permute(vector<int> &nums)
    {
        int len = nums.size();
        vector<vector<int>> res;
        vector<int> tmp;
        backtrack(nums, res, tmp, len);
        return res;
    }
};

78、子集——回溯

findSubsets 函数，该函数接受五个参数：原始数组 nums、存储结果的二维向量 res、当前正在形成的子集 tmp、当前处理的元素索引 idx、原始数组的长度 len。

在 findSubsets 函数中，首先将当前子集 tmp 添加到结果向量 res 中。然后从当前索引 idx 开始，遍历原始数组 nums。对于每个元素 nums[i]，将其添加到当前子集 tmp 中，并递归调用 findSubsets 函数来处理下一个元素，传递的索引为 i + 1。在递归调用返回后，将刚刚添加的元素 nums[i] 从当前子集 tmp 中移除，以便尝试其他可能的元素。

class Solution
{
public:
    void findSubsets(vector<int> &nums,
                     vector<vector<int>> &res,
                     vector<int> &tmp,
                     int idx,
                     int len)
    {
        res.push_back(tmp);
        for (size_t i = idx; i < len; i++)
        {
            tmp.push_back(nums[i]);
            findSubsets(nums, res, tmp, i + 1, len);
            tmp.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int> &nums)
    {
        int len = nums.size();
        vector<vector<int>> res;
        vector<int> tmp;
        findSubsets(nums, res, tmp, 0, len);
        return res;
    }
};

17、电话号码的字母组合——回溯、哈希表

findCombinations，该函数接受五个参数：数字字符串 digits、存储结果的向量 res、当前正在形成的组合 tmp、当前处理的数字的索引 idx、以及目标组合的长度 len。

首先判断当前组合 tmp 的长度是否等于目标长度 len。如果相等，将当前组合添加到结果向量 res 中。如果组合长度不足目标长度，遍历从索引 0 开始的字符集合中的字符。对于每个字符，将其添加到当前组合 tmp 中，并递归调用 findCombinations 函数来处理下一个数字，传递的数字索引为 idx + 1。在递归调用返回后，将刚刚添加的字符从当前组合 tmp 中移除，以便尝试其他可能的字符。

class Solution
{
private:
    unordered_map<char, string> map = {
        {'2', "abc"},
        {'3', "def"},
        {'4', "ghi"},
        {'5', "jkl"},
        {'6', "mno"},
        {'7', "pqrs"},
        {'8', "tuv"},
        {'9', "wxyz"},
    };

public:
    void findCombinations(string &digits,
                          vector<string> &res,
                          string &tmp,
                          int idx, int len)
    {
        if (tmp.length() == len)
        {
            res.push_back(tmp);
        }
        else
        {
            for (size_t i = 0; i < map[digits[idx]].length(); i++)
            {
                tmp.push_back(map[digits[idx]][i]);
                findCombinations(digits, res, tmp, idx + 1, len);
                tmp.pop_back();
            }
        }
    }

    vector<string> letterCombinations(string digits)
    {
        if (digits.empty())
        {
            return {};
        }
        vector<string> res;
        string tmp;
        findCombinations(digits, res, tmp, 0, digits.length());
        return res;
    }
};

39、组合总数——回溯

findCombination 函数中，传入参数 candidates 表示候选数字的集合，target 表示目标和，idx 表示当前考虑的候选数字的索引，len 表示候选数字的总数，tmp 表示当前的组合，result 表示最终结果。

如果 sum 等于 target，说明当前组合满足要求，将其加入到 result 中，并返回。

如果 sum 大于 target，说明当前组合已经超过了目标和，直接返回。

使用一个循环，从索引 idx 开始遍历候选数字。将当前候选数字加入到 tmp 中，然后递归调用 findCombination 函数，传入更新后的参数。在递归调用结束后，需要将最后一个加入到 tmp 中的候选数字移除，以便尝试其他组合。

class Solution
{
public:
    void findCombination(vector<int> &candidates,
                         int target,
                         int idx,
                         int len,
                         vector<int> &tmp,
                         vector<vector<int>> &result)
    {
        int sum = 0;
        for (auto &num : tmp)
        {
            sum += num;
        }
        if (sum == target)
        {
            result.push_back(tmp);
            return;
        }
        else if (sum > target)
        {
            return;
        }
        for (size_t i = idx; i < len; i++)
        {
            tmp.push_back(candidates[i]);
            findCombination(candidates, target, i, len, tmp, result);
            tmp.pop_back();
        }
    }
    vector<vector<int>> combinationSum(vector<int> &candidates,
                                       int target)
    {
        vector<vector<int>> result;
        vector<int> tmp;
        findCombination(candidates, target, 0, candidates.size(), tmp, result);
        return result;
    }
};

22、括号生成——回溯

函数backtrack，传入结果向量res、当前括号组合tmp、括号对数n、剩余左括号数量n和剩余右括号数量n作为参数。

如果左括号数量大于0，说明还可以继续放置左括号。将左括号添加到tmp字符串末尾，然后递归调用backtrack方法，左括号数量减1，右括号数量不变。

如果右括号数量大于左括号数量，说明可以放置右括号。将右括号添加到tmp字符串末尾，然后递归调用backtrack方法，左括号数量不变，右括号数量减1。

class Solution
{
public:
    void backtrack(vector<string> &res,
                   string &tmp, int n,
                   int left, int right)
    {
        if (tmp.length() == n * 2)
        {
            res.push_back(tmp);
            return;
        }
        if (left > 0)
        {
            tmp.push_back('(');
            backtrack(res, tmp, n, left - 1, right);
            tmp.pop_back();
        }
        // 只有已经放入的左括号数量大于右括号时，才能是一个有效的括号串
        if (right > left)
        {
            tmp.push_back(')');
            backtrack(res, tmp, n, left, right - 1);
            tmp.pop_back();
        }
    }

    vector<string> generateParenthesis(int n)
    {
        vector<string> res;
        string tmp;
        backtrack(res, tmp, n, n, n);
        return res;
    }
};

79、单词搜索——回溯

在dfs函数中，通过递归实现深度优先搜索。首先检查当前位置的字符是否与目标单词的当前字符匹配，并且当前位置没有被访问过。如果不匹配或已经被访问过，则返回false。如果当前字符是目标单词的最后一个字符，说明找到了完整的单词，返回true。使用循环遍历四个方向上的相邻位置。如果相邻位置合法（不越界），则递归调用dfs函数进行下一步搜索。如果在某个方向上找到了匹配的单词，则设置ret为true，并立即返回。每次进入递归前将当前位置标记为已访问，递归结束后将其重新标记为未访问，以便进行下一次搜索。

在exist函数中，遍历整个字符矩阵。如果当前位置的字符与目标单词的第一个字符匹配，则调用dfs函数进行搜索。如果找到了匹配的单词，则直接返回true。

class Solution
{
private:
    vector<pair<int, int>> dirs =
        {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public:
    bool dfs(vector<vector<char>> &board, string &word,
             vector<vector<bool>> &visted,
             int n, int i, int j, int h, int w)
    {
        if (word[n] != board[i][j] || visted[i][j])
        {
            return false;
        }
        else if (n == word.length() - 1)
        {
            return true;
        }
        int ret = false;
        visted[i][j] = true;
        for (int k = 0; k < 4; k++)
        {
            if (i + dirs[k].first >= 0 && i + dirs[k].first < h &&
                j + dirs[k].second >= 0 && j + dirs[k].second < w)
            {
                ret = ret || dfs(board, word, visted, n + 1, i + dirs[k].first, j + dirs[k].second, h, w);
            }
            if (ret)
            {
                break;
            }
        }
        visted[i][j] = false;
        return ret;
    }

    bool exist(vector<vector<char>> &board,
               string word)
    {
        int m = board.size();
        int n = board[0].size();
        vector<vector<bool>> visted(m, vector<bool>(n, false));
        bool ret = false;
        for (size_t i = 0; i < m; i++)
        {
            for (size_t j = 0; j < n; j++)
            {
                if (word[0] == board[i][j])
                {
                    ret = ret || dfs(board, word, visted, 0, i, j, m, n);
                    if (ret)
                    {
                        return true;
                    }
                }
            }
        }
        return ret;
    }
};

42、接雨水——双指针

按层计算

在每一次循环中，根据指针所指的位置，判断当前柱子的高度与另一侧柱子的高度哪个更小。如果height[pre] <= height[nx]，则说明左侧柱子更低，可以确定左侧柱子的高度作为当前水平面的高度，并计算从pre到nx之间可以存储的雨水量。如果height[pre] > height[nx]，则说明右侧柱子更低，可以确定右侧柱子的高度作为当前水平面的高度，并计算从pre到nx之间可以存储的雨水量。

不过这种方法超时了。

class Solution
{
public:
    int volume(vector<int> &height, int start, int end, int h)
    {
        int ret = 0;
        for (size_t i = start + 1; i < end; i++)
        {
            int diff = h - height[i];
            ret += (diff > 0) ? diff : 0;
            height[i] = (diff > 0) ? h : height[i];
        }
        return ret;
    }

    int trap(vector<int> &height)
    {
        int pre = 0, nx = height.size() - 1, res = 0;
        unordered_set<int> layers;
        layers.insert(0);
        while (pre < nx)
        {
            if (height[pre] <= height[nx])
            {
                if (layers.find(height[pre]) == layers.end())
                {
                    res += volume(height, pre, nx, height[pre]);
                    layers.insert(height[pre]);
                }
                pre++;
            }
            else
            {
                if (layers.find(height[nx]) == layers.end())
                {
                    res += volume(height, pre, nx, height[nx]);
                    layers.insert(height[nx]);
                }
                nx--;
            }
        }
        return res;
    }
};

优化——按列计算

首先定义两个指针 left 和 right，分别指向数组的最左边和最右边。同时定义两个变量 leftMax 和 rightMax，分别表示左边和右边的最大高度。

接下来使用一个循环来遍历数组，当 left 小于 right 时，进行以下操作：

如果 height[left] 小于等于 height[right]，说明左边的柱子高度较低或者相等，此时可以确定左边的柱子是当前能够接水的最高柱子。如果 height[left] 大于 leftMax，则更新 leftMax 为 height[left]，否则将 leftMax - height[left] 加到 water 中。然后将 left 向右移动一位。
如果 height[left] 大于 height[right]，说明右边的柱子高度较低，此时可以确定右边的柱子是当前能够接水的最高柱子。如果 height[right] 大于 rightMax，则更新 rightMax 为 height[right]，否则将 rightMax - height[right] 加到 water 中。然后将 right 向左移动一位。

class Solution
{
public:
    int trap(vector<int> &height)
    {
        int n = height.size();
        if (n == 0)
        {
            return 0;
        }

        int left = 0, right = n - 1;
        int leftMax = 0, rightMax = 0;
        int water = 0;

        while (left < right)
        {
            if (height[left] <= height[right])
            {
                if (height[left] > leftMax)
                {
                    leftMax = height[left];
                }
                else
                {
                    water += leftMax - height[left];
                }
                left++;
            }
            else
            {
                if (height[right] > rightMax)
                {
                    rightMax = height[right];
                }
                else
                {
                    water += rightMax - height[right];
                }
                right--;
            }
        }

        return water;
    }
};

239、滑动窗口最大值——双指针、单调队列

首先处理前 k 个元素，构建初始的滑动窗口：

遍历前 k 个元素的索引 i。
在保持队列单调递减的前提下，移除队列中比当前元素 nums[i] 小的元素，以保证队列中的元素是按照从大到小的顺序排列的。
将当前元素的索引 i 添加到队尾。
继续下一轮循环。

处理剩余的元素：

从索引 k 开始遍历剩余的元素，即滑动窗口向右移动。
在每次处理一个新的元素前，将队首元素 dq.front() 添加到结果向量 ret，它是当前窗口的最大值。
检查队首元素的索引是否已经不在当前窗口内（即超过了窗口的右边界 i - k），如果是，则将队首元素从队列中移除。
在保持队列单调递减的前提下，移除队列中比当前元素 nums[i] 小的元素。
将当前元素的索引 i 添加到队尾。
继续下一轮循环。

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        vector<int> ret;
        deque<int> dq;
        for (size_t i = 0; i < k; i++)
        {
            while (!dq.empty() && nums[i] >= nums[dq.back()])
            {
                dq.pop_back();
            }
            dq.push_back(i);
        }
        for (size_t i = k; i < nums.size(); i++)
        {
            ret.push_back(nums[dq.front()]);
            if (dq.front() <= i - k)
            {
                dq.pop_back();
            }
            while (!dq.empty() && nums[i] >= nums[dq.back()])
            {
                dq.pop_back();
            }
            dq.push_back(i);
        }
        // 处理最后一个窗口的最大值
        if (!dq.empty())
        {
            ret.push_back(nums[dq.front()]);
        }

        return ret;
    }
};

优先队列

使用一个优先队列来维护滑动窗口内的元素，并按照元素值的降序进行排序。

处理前 k 个元素，构建初始的滑动窗口：
- 遍历前 k 个元素的索引 i。
- 将元素 nums[i] 和索引 i 组成一个 pair 对，并将其插入优先队列 pq。
- 继续下一轮循环。
处理剩余的元素：
- 从索引 k 开始遍历剩余的元素，即滑动窗口向右移动。
- 在每次处理一个新的元素前，将优先队列的头部元素 pq.top() 的值（最大值）添加到结果向量 ret。
- 检查头部元素的索引是否已经不在当前窗口内（即超过了窗口的右边界 i - k），如果是，则将头部元素从优先队列中移除。
- 将元素 nums[i] 和索引 i 组成一个 pair 对，并将其插入优先队列 pq。
- 继续下一轮循环。
处理最后一个窗口的最大值：
- 如果优先队列 pq 不为空，将头部元素 pq.top() 的值（最大值）添加到结果向量 ret。

class Solution
{
public:
    vector<int> maxSlidingWindow(vector<int> &nums, int k)
    {
        vector<int> ret;
        priority_queue<pair<int, int>> pq;
        for (size_t i = 0; i < k; i++)
        {
            pq.emplace(nums[i], i);
        }
        for (size_t i = k; i < nums.size(); i++)
        {
            ret.push_back(pq.top().first);
            while (!pq.empty() && pq.top().second <= i - k)
            {
                pq.pop();
            }
            pq.emplace(nums[i], i);
        }
        if (!pq.empty())
        {
            ret.push_back(pq.top().first);
        }

        return ret;
    }
};

76、最小覆盖子串——哈希表、滑动窗口

hasAll 函数用于判断哈希表 has 是否包含了哈希表 need 中所有的字符及其对应的出现次数。

两个指针，一个用于「延伸」现有窗口的 rrr 指针，和一个用于「收缩」窗口的 lll 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 sss 上滑动窗口，通过移动 rrr 指针不断扩张窗口。当窗口包含 ttt 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

class Solution
{
public:
    bool hasAll(unordered_map<char, int> &has,
                unordered_map<char, int> &need)
    {
        for (auto &n : need)
        {
            if (has.find(n.first) == has.end())
            {
                return false;
            }
            else if (has[n.first] < n.second)
            {
                return false;
            }
        }
        return true;
    }

    string minWindow(string s, string t)
    {
        int left = 0, right = 0;
        string ret;
        unordered_map<char, int> has;
        unordered_map<char, int> need;
        vector<int> index;
        index.push_back(0);
        index.push_back(s.length() + 1);
        for (auto c : t)
        {
            need[c] = need.find(c) == need.end() ? 1 : need[c] + 1;
        }
        while (right <= s.length() && left <= right)
        {
            if (!hasAll(has, need))
            {
                has[s[right]] = has.find(s[right]) == has.end() ? 1 : has[s[right]] + 1;
                right++;
            }
            else
            {
                if (right - left < index[1] - index[0])
                {
                    index[0] = left;
                    index[1] = right;
                }
                left++;
                has[s[left - 1]]--;
            }
        }
        return index[1] - index[0] == s.length() + 1 ? ret : s.substr(index[0], index[1] - index[0]);
    }
};

41、缺失的第一个正数——排序

这是困难题？

class Solution
{
public:
    int firstMissingPositive(vector<int> &nums)
    {
        sort(nums.begin(), nums.end());
        bool first = true;
        for (size_t i = 0; i < nums.size(); i++)
        {
            if (nums[i] > 0 && first)
            {
                first = false;
                if (nums[i] != 1)
                {
                    return 1;
                }
                continue;
            }
            if (!first && nums[i] - nums[i - 1] > 1)
            {
                return nums[i - 1] + 1;
            }
        }
        return nums[nums.size() - 1] + 1 > 0 ? nums[nums.size() - 1] + 1 : 1;
    }
};

25、K个一组翻转链表

myReverse(ListNode *head, ListNode *tail)：以迭代的方式翻转从head到tail之间的子链表，并返回新的头和尾节点。

reverseKGroup(ListNode *head, int k)：

首先创建一个hair节点，将其指向链表头部。然后创建一个pre节点，初始指向hair节点。
进入循环，循环条件是head不为空。
在循环中，首先确定子链表的尾节点tail。通过循环遍历k个节点，如果遍历到尾部为空，则直接返回链表头部。
获取子链表的下一个节点nex。
调用myReverse函数翻转子链表，得到翻转后的头节点head和尾节点tail。
将翻转后的子链表重新接回原链表，即将pre->next指向head，tail->next指向nex。
更新pre为当前子链表的尾节点tail，更新head为tail->next，继续下一轮循环。
循环结束后，返回hair->next，即翻转后的链表头节点。

class Solution
{
public:
    // 翻转一个子链表，并且返回新的头与尾
    pair<ListNode *, ListNode *> myReverse(ListNode *head, ListNode *tail)
    {
        ListNode *prev = nullptr;
        ListNode *p = head;
        while (prev != tail)
        {
            ListNode *nx = p->next;
            p->next = prev;
            prev = p;
            p = nx;
        }
        return {tail, head};
    }

    ListNode *reverseKGroup(ListNode *head, int k)
    {
        ListNode *hair = new ListNode(0);
        hair->next = head;
        ListNode *pre = hair;

        while (head)
        {
            ListNode *tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i)
            {
                tail = tail->next;
                if (!tail)
                {
                    return hair->next;
                }
            }
            ListNode *nex = tail->next;
            pair<ListNode *, ListNode *> result = myReverse(head, tail);
            head = result.first;
            tail = result.second;
            // 把子链表重新接回原链表
            pre->next = head;
            tail->next = nex;
            // 下一要交换子链表的前一节点
            pre = tail;
            // 下一要交换子链表头节点
            head = tail->next;
        }

        return hair->next;
    }
};

23、合并K个升序链表

这是困难题？

/**
 * 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 *mergeKLists(vector<ListNode *> &lists)
    {
        vector<int> vec;
        for (size_t i = 0; i < lists.size(); i++)
        {
            ListNode *p = lists[i];
            while (p != nullptr)
            {
                vec.push_back(p->val);
                p = p->next;
            }
        }
        ListNode *head = new ListNode();
        ListNode *cur = head;
        sort(vec.begin(), vec.end());
        for (size_t i = 0; i < vec.size(); i++)
        {
            ListNode *tmp = new ListNode(vec[i]);
            cur->next = tmp;
            cur = cur->next;
        }

        return head->next;
    }
};

124、二叉树中的最大路径和——动态规划

拆解问题（null节点为0），以叶子节上一层的节点为根节点寻找最大路径，假设树为[a,b,c]，则最大路径和有六种情况，a、b、c、abc、ab、bc，在寻找时更新max即可。然后返回当前节点为路径起点的最大路径和，有三种情况a，ab和ac，用于在后序遍历的过程中寻找当前节点的父节点的最大路径和。

/**
 * 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) {}
 * };
 */
#define MAX(a, b) (a > b ? a : b)
class Solution
{
private:
    int max;

public:
    int travel(TreeNode *root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int left = travel(root->left);
        int right = travel(root->right);
        int ans = MAX(root->val, root->val + left);
        ans = MAX(ans, root->val + right);
        ans = MAX(ans, root->val + left + right);
        max = MAX(ans, max);
        return MAX(root->val, root->val + MAX(left, right));
    }
    int maxPathSum(TreeNode *root)
    {
        max = INT_MIN;
        travel(root);
        return max;
    }
};

131、分割回文串——回溯

ret用于存储所有的分割结果，cur用于存储当前的分割结果，s是待分割的字符串，idx表示当前处理的位置。

当idx等于字符串长度时，说明已经处理完所有字符，将当前的分割结果cur添加到ret中。
否则，从idx开始遍历字符串，如果从idx到当前位置的子串是回文串，就将它添加到cur中，然后递归调用backtrack函数，继续处理下一个位置，最后将添加的子串从cur中移除，以便尝试其他分割方式。

class Solution
{
public:
    bool isPalindrome(string str)
    {
        int n = str.length();
        for (int i = 0; i < n / 2; i++)
        {
            if (str[i] != str[n - i - 1])
            {
                return false;
            }
        }
        return true;
    }

    void backtrack(vector<vector<string>> &ret,
                   vector<string> &cur,
                   string &s,
                   int idx)
    {
        if (idx == s.length())
        {
            ret.push_back(cur);
        }
        for (int i = idx; i < s.length(); ++i)
        {
            if (isPalindrome(s.substr(idx, i - idx + 1)))
            {
                cur.push_back(s.substr(idx, i - idx + 1));
                backtrack(ret, cur, s, i + 1);
                cur.pop_back();
            }
        }
    }

    vector<vector<string>> partition(string s)
    {
        vector<vector<string>> ret;
        vector<string> cur;
        backtrack(ret, cur, s, 0);
        return ret;
    }
};

51、N皇后——回溯

isValid 函数用于判断当前位置是否合法。它首先检查当前位置所在的列是否已经存在皇后，如果存在则返回 false。然后，它分别检查当前位置所在的两条斜线上是否存在皇后，如果存在则返回 false。如果当前位置在所有方向上都没有冲突，则返回 true。

backtrack 函数首先判断当前行是否已经越界，如果越界则表示找到了一个解，将当前解保存到结果集中。否则，它遍历当前行的每一个位置，判断该位置是否合法。如果合法，则将当前位置标记为皇后，并递归调用 backtrack 函数处理下一行。递归调用结束后，需要将当前位置恢复为空白，以便尝试其他可能性。

class Solution
{
public:
    bool isValid(vector<string> &cur,
                 int i, int j, int n)
    {
        // 判断当前位置是否合法 列
        for (size_t m = 0; m < i; m++)
        {
            if (cur[m][j] == 'Q')
            {
                return false;
            }
        }
        // 判断当前位置是否合法 斜线
        int row = i, col = j;
        while (--row >= 0 && --col >= 0)
        {
            if (cur[row][col] == 'Q')
            {
                return false;
            }
        }
        row = i, col = j;
        while (--row >= 0 && ++col < n)
        {
            if (cur[row][col] == 'Q')
            {
                return false;
            }
        }
        return true;
    }

    void backtrack(vector<vector<string>> &ret,
                   vector<string> &cur,
                   int n,
                   int row)
    {
        if (row == n)
        {
            ret.push_back(cur);
            return;
        }
        else
        {
            for (size_t i = 0; i < n; i++)
            {
                if (isValid(cur, row, i, n))
                {
                    cur[row][i] = 'Q';
                    backtrack(ret, cur, n, row + 1);
                }
                cur[row][i] = '.';
            }
        }
    }

    vector<vector<string>> solveNQueens(int n)
    {
        vector<vector<string>> ret;
        vector<string> cur(n, string(n, '.'));
        backtrack(ret, cur, n, 0);
        return ret;
    }
};

74、搜索二维矩阵——二分查找

当成一维查找就可以了，转换一下坐标即可。

class Solution
{
public:
    bool searchMatrix(vector<vector<int>> &matrix,
                      int target)
    {
        int row = matrix.size(), col = matrix[0].size();
        int st = 0, ed = row * col - 1;
        int mid, x, y;
        while (st <= ed)
        {
            mid = st + (ed - st) / 2;
            x = mid / col;
            y = mid - col * x;
            if (matrix[x][y] == target)
            {
                return true;
            }
            else if (matrix[x][y] > target)
            {
                ed = mid - 1;
            }
            else
            {
                st = mid + 1;
            }
        }
        return false;
    }
};

34、在排序数组中查找元素的区间——二分查找

还是很常规的二分查找，在nums[mid] == target条件下略施小计即可，这样函数寻找的就是满足条件的最小下标。

class Solution
{
public:
    int lower(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        int mid;
        int ret = -1;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            if (nums[mid] == target)
            {
                ret = mid;
                right = mid - 1;
            }
            else if (nums[mid] < target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
        return ret;
    }

    vector<int> searchRange(vector<int> &nums,
                            int target)
    {
        vector<int> ret(2, -1);
        ret[0] = lower(nums, target);
        if (ret[0] == -1)
        {
            return ret;
        }
        ret[1] = ret[0];
        int cnt = ret[0];
        while (++cnt < nums.size() && nums[cnt] == target)
        {
            ret[1] = cnt;
        }
        return ret;
    }
};

33、搜索旋转排序数组——二分查找

数组是经过旋转的，但仍然有一部分是有序的。关键是判断哪一部分是有序的。通过比较 nums[left] 和 nums[mid]，以及 nums[mid] 和 nums[right] 可以确定哪一部分是有序的，确定有序之后就判断目标是否可能在这个有序区间，如果是则更新寻找区间（之后就是常规的二分查找），如果不是则在另一个部分有序区间重复上述步骤。

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        int left = 0, right = nums.size() - 1;
        int mid;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            // 找到
            if (nums[mid] == target)
            {
                return mid;
            }
            // 如果mid的左边是有序的
            if (nums[left] <= nums[mid])
            {
                // 如果target在mid的左边
                if (nums[left] <= target && nums[mid] > target)
                {
                    right = mid - 1;
                }
                else
                {
                    left = mid + 1;
                }
            }
            // 如果mid的右边是有序的
            else
            {
                // 如果target在mid的右边
                if (nums[mid] < target && nums[right] >= target)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
};

153、寻找旋转排序数组中的最小值——二分查找

如果nums[left] <= nums[right]，表示整个区间是有序的，直接返回nums[left]，即为最小值。
如果nums[left] <= nums[mid] && nums[mid] > nums[right]，表示中间位置mid的左边是有序的（不包括mid），而右边是无序的（包括mid），最小值在右边，将左指针left移动到mid + 1的位置。
其他情况下，表示中间位置mid的右边是有序的，而左边是无序的，最小值在左边，将右指针right移动到mid的位置。

class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        int left = 0, right = nums.size() - 1;
        int mid = 0;
        while (left <= right)
        {
            mid = left + (right - left) / 2;
            // 如果整体有序
            if (nums[left] <= nums[right])
            {
                return nums[left];
            }
            // 如果mid的左边是有序的且右边无序，则最小值在右边
            else if (nums[left] <= nums[mid] && nums[mid] > nums[right])
            {
                left = mid + 1;
            }
            // 如果mid的右边是有序的且左边无序，则最小值在左边
            else
            {
                right = mid;
            }
        }
        return -1;
    }
};

4、寻找两个正序数组的中位数——二分查找

这里的中位数，本质上就是排在中间的数，可以把问题简化成找第K大的值的问题。

先找两个数组中的第K/2（如果大于数组长度则为数组长度）个数，将两数进行比较，由于数组是有序的，所以较小的第K/2个数一定不是符合要求的数，我们可以排除出去，然后再在剩下的数中找第K-K/2个数。

class Solution
{
public:
    int getKthElement(const vector<int> &nums1, const vector<int> &nums2, int k)
    {
        int m = nums1.size();
        int n = nums2.size();
        int index1 = 0, index2 = 0;

        while (true)
        {
            // 边界情况
            if (index1 == m)
            {
                return nums2[index2 + k - 1];
            }
            if (index2 == n)
            {
                return nums1[index1 + k - 1];
            }
            if (k == 1)
            {
                return min(nums1[index1], nums2[index2]);
            }

            // 正常情况
            int newIndex1 = min(index1 + k / 2 - 1, m - 1);
            int newIndex2 = min(index2 + k / 2 - 1, n - 1);
            int pivot1 = nums1[newIndex1];
            int pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2)
            {
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            }
            else
            {
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }
    }

    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        int totalLength = nums1.size() + nums2.size();
        if (totalLength % 2 == 1)
        {
            return getKthElement(nums1, nums2, (totalLength + 1) / 2);
        }
        else
        {
            return (getKthElement(nums1, nums2, totalLength / 2) +
                    getKthElement(nums1, nums2, totalLength / 2 + 1)) /
                   2.0;
        }
    }
};

155、最小栈——设计

不使用辅助栈

使用vector模拟栈，vector中每个元素，first存储如果弹出该元素栈的最小值下标，second存储值。然后同时用index存储最小值下标，在每次pop和push时进行更新即可。

在 push(val) 操作中，将 val 入栈，并将push前的最小值下标和值作为 pair 放入 stack 中。同时更新 index 的值，如果 index 为 -1，则将其设置为 0；否则，将其与当前栈顶元素进行比较，如果当前栈顶元素较小，则不改变 index，否则将其设置为 nums – 1。

在 pop() 操作中，首先判断栈中是否有元素（nums > 0），然后判断是否需要更新 index 的值。如果 nums 等于 index + 1，说明当前栈顶元素是最小元素，需要更新 index 的值为push该元素前的最小值下标 stack[index].first。然后将 nums 减 1，同时从 stack 中删除最后一个元素。

class MinStack
{
private:
    int index;
    int nums;
    vector<pair<int, int>> stack;

public:
    MinStack()
    {
        nums = 0;
        index = -1;
    }

    void push(int val)
    {
        nums++;
        stack.push_back(make_pair(index, val));
        index = index == -1 ? 0 : (stack[index].second < val ? index : nums - 1);
    }

    void pop()
    {
        if (nums > 0)
        {
            if (nums == index + 1)
            {
                index = stack[index].first;
            }
            nums--;
            stack.pop_back();
        }
    }

    int top()
    {
        if (nums > 0)
            return stack[nums - 1].second;
        else
            return INT_MAX;
    }

    int getMin()
    {
        if (nums > 0)
            return stack[index].second;
        else
            return INT_MAX;
    }
};

394、字符串解码——栈

遍历输入字符串 s 的每个字符，根据不同的情况进行处理：

如果当前字符不是 ] 且不是数字，则将其作为一个单独的字符压入栈中。
如果当前字符是 ]，则需要从栈中不断弹出字符，直到遇到对应的 [。弹出的字符构成一个子字符串 tmp。对应的 [之后一定是数字num，然后将num个tmp压入栈。
接下来，从栈中弹出一个数字，表示 tmp 需要重复的次数。然后将 tmp 重复相应次数，并将结果压入栈中。
如果当前字符是数字，则需要将连续的数字字符组合成一个完整的数字，并将其作为字符串压入栈中。

最后，将栈中剩余的字符串依次弹出，并拼接成最终的解码结果。

class Solution
{
public:
    string decodeString(string s)
    {
        string ret;
        stack<string> stk;
        for (size_t i = 0; i < s.length(); i++)
        {
            if (s[i] != ']' && (s[i] < '0' || s[i] > '9'))
            {
                stk.push(string(1, s[i]));
            }
            else if (s[i] == ']')
            {
                string tmp;
                while (stk.top() != "[")
                {
                    tmp = stk.top() + tmp;
                    stk.pop();
                }
                stk.pop();
                int num = stoi(stk.top());
                stk.pop();
                while (num--)
                {
                    stk.push(tmp);
                }
            }
            else
            {
                string strnum = string(1, s[i]);
                while (s[++i] >= '0' && s[i] <= '9')
                {
                    strnum = strnum + s[i];
                }
                stk.push(strnum);
                i--;
            }
        }
        while (!stk.empty())
        {
            ret = stk.top() + ret;
            stk.pop();
        }

        return ret;
    }
};

739、每日温度——单调栈

遍历数组，对于每个元素，如果栈为空，或者当前元素的温度小于等于栈顶元素的温度，将当前元素的索引入栈。如果当前元素的温度大于栈顶元素的温度，则将栈顶元素出栈，并计算它与当前元素索引的距离，将该距离存储在 ret 数组中对应位置。重复这个过程，直到栈为空或者栈顶元素的温度大于等于当前元素的温度。

class Solution
{
public:
    vector<int> dailyTemperatures(vector<int> &temperatures)
    {
        stack<int> stk;
        vector<int> ret(temperatures.size(), 0);
        for (int i = 0; i < temperatures.size(); i++)
        {
            if (stk.empty())
            {
                stk.push(i);
            }
            else
            {
                if (temperatures[i] <= temperatures[stk.top()])
                {
                    stk.push(i);
                }
                else
                {
                    while (!stk.empty() && temperatures[stk.top()] < temperatures[i])
                    {
                        ret[stk.top()] = i - stk.top();
                        stk.pop();
                    }
                    stk.push(i);
                }
            }
        }
        return ret;
    }
};

84、柱状图中最大的矩形——单调栈

这题的基础模型其实就是：在一维数组中对每一个数找到第一个比自己小的元素，找到之后对每一个数计算面积，然后得到其中的最大值。在heights向量的开头插入一个值为0的元素，表示柱子的左边界。在heights向量的末尾插入一个值为0的元素，表示柱子的右边界。

循环中，首先判断栈st是否为空，并且当前柱子的高度heights[i]小于栈顶柱子的高度heights[st.back()]，条件满足，表示当前栈顶柱子的高度构成了一个矩形的右边界。弹出所有大于当前边界的栈顶元素，计算矩形的左边界和右边界。左边界为栈顶元素的前一个元素索引加1，右边界为当前柱子的索引减1。计算当前矩形的面积，即(right - left + 1) * heights[cur]，并将结果与ans进行比较，更新ans为较大的值。然后将当前柱子的索引i压入栈st中。

class Solution
{
public:
    int largestRectangleArea(vector<int> &heights)
    {
        int ans = 0;
        vector<int> st;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        for (int i = 0; i < heights.size(); i++)
        {
            while (!st.empty() && heights[st.back()] > heights[i])
            {
                int cur = st.back();
                st.pop_back();
                int left = st.back() + 1;
                int right = i - 1;
                ans = max(ans, (right - left + 1) * heights[cur]);
            }
            st.push_back(i);
        }
        return ans;
    }
};

215、数组中的第K个最大元素——堆

STL

STL有优先队列或者堆的的容器可以直接使用，不说了。

class Solution
{
public:
    int findKthLargest(vector<int> &nums,
                       int k)
    {
        priority_queue<int, vector<int>, greater<int>> minHeap;

        for (int num : nums)
        {
            minHeap.push(num);
            if (minHeap.size() > k)
            {
                minHeap.pop();
            }
        }

        return minHeap.top();
    }
};

自己实现堆排序

heapify 函数用于执行下沉操作，将元素下沉到合适的位置，使得以该元素为根的子树满足堆的性质。
- size 表示堆的大小。
- index 表示当前节点的索引。
- 首先，将当前节点设为最大值。
- 然后，比较左子节点和当前节点的值，如果左子节点的值更大，则将最大值更新为左子节点的索引。
- 接着，比较右子节点和当前节点的值，如果右子节点的值更大，则将最大值更新为右子节点的索引。
- 如果最大值不是当前节点的索引，说明需要交换当前节点和最大值对应的元素，并继续向下调整刚刚交换过的子节点。
heapSort 函数用于执行堆排序算法。
- 首先，获取数组的大小。
- 然后，从最后一个非叶子节点开始，依次调用 heapify 函数进行下沉操作，构建初始堆。
- 接下来，重复执行以下操作，直到堆中只剩下一个元素：
  - 将堆顶元素（最大值）与堆中的最后一个元素交换位置。
  - 对剩余元素进行堆调整，使其满足堆的性质。这里调用 heapify 函数，将堆的大小设置为当前元素的索引，并将当前元素的索引设为0。

通过以上步骤，最终得到的数组就是按照从小到大排序的结果。

class Solution
{
public:
    // 下沉操作，将元素下沉到合适的位置，使得以该元素为根的子树满足堆的性质
    void heapify(std::vector<int> &nums, int size, int index)
    {
        int largest = index;       // 当前节点为最大值
        int left = 2 * index + 1;  // 左子节点的索引
        int right = 2 * index + 2; // 右子节点的索引
        // 比较左子节点和当前节点的值
        if (left < size && nums[left] > nums[largest])
        {
            largest = left;
        }
        // 比较右子节点和当前节点的值
        if (right < size && nums[right] > nums[largest])
        {
            largest = right;
        }
        // 如果最大值不是当前节点，则交换它们，并继续向下调整
        if (largest != index)
        {
            std::swap(nums[index], nums[largest]);
            heapify(nums, size, largest);
        }
    }

    // 堆排序算法
    void heapSort(std::vector<int> &nums)
    {
        int size = nums.size();
        // 构建初始堆，从最后一个非叶子节点开始，依次进行下沉操作
        for (int i = size / 2 - 1; i >= 0; i--)
        {
            heapify(nums, size, i);
        }
        // 重复执行以下操作，直到堆中只剩下一个元素
        for (int i = size - 1; i > 0; i--)
        {
            // 将堆顶元素（最大值）与堆中的最后一个元素交换位置
            std::swap(nums[0], nums[i]);
            // 对剩余元素进行堆调整，使其满足堆的性质
            heapify(nums, i, 0);
        }
    }

    int findKthLargest(vector<int> &nums, int k)
    {
        heapSort(nums);
        return nums[nums.size() - k];
    }
};

347、前K个高频元素——堆、排序

排序

暴力排序法，没什么说的

class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {

        unordered_map<int, int> frequent;
        for (auto &num : nums)
        {
            frequent[num]++;
        }
        vector<pair<int, int>> v;
        for (auto &it : frequent)
        {
            v.push_back(make_pair(it.first, it.second));
        }
        sort(v.begin(), v.end(), [](const pair<int, int> &a, const pair<int, int> &b)
             { return a.second > b.second; });
        vector<int> ret;
        for (size_t i = 0; i < k; i++)
        {
            ret.push_back(v[i].first);
        }
        return ret;
    }
};

最小堆

第二个循环用来找出前k个高频元素。代码首先判断ret（存储前k个高频元素）的大小是否已经达到k。如果是，则比较当前元素it和ret中的最小频率元素（ret[0]）的频率大小。如果当前元素的频率大于最小频率元素的频率，则将最小频率元素从ret中移除，并将当前元素加入ret中，然后重新维护ret的堆结构。这里使用了push_heap和pop_heap来维护堆。如果当前元素的频率小于等于最小频率元素的频率，则不做任何操作。

如果ret的大小还没达到k，则直接将当前元素加入ret，并维护堆结构。

最后，返回ret作为结果。

class Solution
{
public:
    vector<int> topKFrequent(vector<int> &nums, int k)
    {

        unordered_map<int, int> frequent;
        for (auto &num : nums)
        {
            frequent[num]++;
        }
        for (auto &it : frequent)
        {
            cout << it.first << "=" << it.second<< " ";
        }
        cout<<endl;
        vector<int> ret;
        for (auto &it : frequent)
        {
            if (ret.size() == k)
            {
                if (it.second > frequent[ret[0]])
                {
                    pop_heap(ret.begin(), ret.end(), [&frequent](auto &a, auto &b)
                             { return frequent[a] > frequent[b]; });
                    ret.pop_back();
                    ret.push_back(it.first);
                    push_heap(ret.begin(), ret.end(), [&frequent](auto &a, auto &b)
                              { return frequent[a] > frequent[b]; });
                }
            }
            else
            {
                ret.push_back(it.first);
                push_heap(ret.begin(), ret.end(), [&frequent](auto &a, auto &b)
                          { return frequent[a] > frequent[b]; });
            }
        }
        return ret;
    }
};

295、数据流的中位数——优先队列

该类使用两个优先队列 Min 和 Max 来存储数字。Min 是一个最大堆，用于存储较小的一半数字；Max 是一个最小堆，用于存储较大的一半数字。

在 addNum 方法中，首先判断 Min 是否为空或者插入的数字是否小于等于当前中位数（通过调用 findMedian 方法获取）。如果是，则将数字插入 Min 中，并检查 Min 的大小是否比 Max 多 1。如果是，则将 Min 的顶部元素（最大值）插入 Max 中，并从 Min 中移除该元素，以保持两个堆的平衡。

如果插入的数字大于当前中位数，则将数字插入 Max 中，并检查 Max 的大小是否比 Min 多 1。如果是，则将 Max 的顶部元素（最小值）插入 Min 中，并从 Max 中移除该元素。

在 findMedian 方法中，首先检查 Max 和 Min 的大小。如果两个堆的大小相等，则说明元素总数为偶数，返回 Max 的顶部元素和 Min 的顶部元素的平均值作为中位数。如果 Max 的大小大于 Min 的大小，则返回 Max 的顶部元素作为中位数。否则，返回 Min 的顶部元素作为中位数。

添加数字时，最多需要对一个堆进行插入和调整操作，时间复杂度为 O(log n)。获取中位数时，只需要获取堆顶元素，时间复杂度为 O(1)。

class MedianFinder
{
private:
    priority_queue<int, vector<int>, less<int>> Min;
    priority_queue<int, vector<int>, greater<int>> Max;

public:
    MedianFinder()
    {
    }

    void addNum(int num)
    {
        if (Min.empty() || num <= findMedian())
        {
            Min.push(num);
            if (Max.size() + 1 < Min.size())
            {
                Max.push(Min.top());
                Min.pop();
            }
        }
        else
        {
            Max.push(num);
            if (Max.size() > Min.size() + 1)
            {
                Min.push(Max.top());
                Max.pop();
            }
        }
    }

    double findMedian()
    {
        if (Max.size() == Min.size())
        {
            return (Max.top() + Min.top()) / 2.0;
        }
        else if (Max.size() > Min.size())
        {
            return Max.top();
        }
        else
        {
            return Min.top();
        }
    }
};

763、划分字母区间——贪心、哈希表、双指针

遍历字符串s，将每个字符及其最后一次出现的位置存储在映射表map中。

start表示当前子串的起始索引。在每次循环中，让right等于left索引的字符出现的最后位置（当最后位置大于当前right时），然后判断left到right的范围内的字符是否有在哈希表中最后位置大于right的，如果存在，说明当前字符 s[left] 在当前片段之后还出现过，当前子串不符合要求，让left++，即以下一个当前子串的元素作为右边界（必须大于当前右边界），然后继续循环；如果不存在，可以将当前子串长度（right – start + 1）存入结果。

class Solution
{
public:
    vector<int> partitionLabels(string s)
    {
        vector<int> ret;
        int left = 0, right = 0;
        int start = 0;
        unordered_map<char, int> map;
        for (size_t i = 0; i < s.length(); i++)
        {
            map[s[i]] = i;
        }
        while (left <= right)
        {
            while (map[s[left]] < right)
            {
                left++;
            }
            right = map[s[left]];
            if (right == s.length() - 1)
            {
                ret.push_back(right - start + 1);
                break;
            }
            bool flag = true;
            for (size_t j = start; j < right; j++)
            {
                if (map[s[j]] > right)
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                ret.push_back(right - start + 1);
                left = right + 1;
                right = left;
                start = left;
            }
            else
            {
                left++;
            }
        }
        return ret;
    }
};

279、完全平方数——动态规划

遍历1到n，对于每一个元素i，遍历1到sqrt(i)，每次遍历j更新minn为min(minn, f[i – j * j])，最后更新dp数组。

时间复杂度为O(n*sqrt(n))，其中sqrt(n)是内层循环的遍历次数。空间复杂度为O(n)，需要一个大小为n+1的数组来保存最少完全平方数的个数。

class Solution
{
public:
    int numSquares(int n)
    {
        vector<int> f(n + 1);
        for (int i = 1; i <= n; i++)
        {
            int minn = INT_MAX;
            for (int j = 1; j * j <= i; j++)
            {
                minn = min(minn, f[i - j * j]);
            }
            f[i] = minn + 1;
        }
        return f[n];
    }
};

322、零钱兑换——动态规划

外层循环从1遍历到amount，表示需要凑出的目标金额。内层循环遍历硬币数组coins中的每个硬币。

对于每个目标金额i，遍历硬币数组，如果i - coin大于等于0，表示当前硬币可以被使用，进行状态转移。在状态转移中，先判断dp[i - coin]是否等于INT_MAX，如果是，则表示无法使用当前硬币凑出金额i - coin，因此temp被赋值为INT_MAX。否则，temp被赋值为dp[i - coin] + 1，表示使用当前硬币后凑出金额i所需的硬币数量。

更新dp[i]，将其与temp进行比较，取较小的值作为凑出金额i所需的最少硬币数量。

class Solution
{
public:
    int coinChange(vector<int> &coins, int amount)
    {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i < amount + 1; i++)
        {
            for (int &coin : coins)
            {
                if (i - coin >= 0)
                {
                    int temp = dp[i - coin] == INT_MAX ? INT_MAX : dp[i - coin] + 1;
                    dp[i] = min(dp[i], temp);
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};

139、单词划分——动态规划

无序集合dict，用于存储wordDict中的单词。布尔类型的向量dp，其中dp[i]表示从字符串s的位置0到位置i的子字符串是否可以通过拆分成wordDict中的单词来组成。将dp[0]设置为true，表示空字符串可以被拆分。

使用两层循环遍历字符串s的每个字符。在内层循环中，从当前位置i向前遍历，提取从位置j到位置i的子字符串tmp（使用substr函数）。如果tmp在dict中存在，并且dp[j]为true，则将dp[i+1]设置为true，表示从位置0到位置i的子字符串可以被拆分。

最后，返回dp[s.length()]作为结果，表示整个字符串s是否可以通过拆分成wordDict中的单词来组成。

class Solution
{
public:
    bool wordBreak(string s,
                   vector<string> &wordDict)
    {
        unordered_set<string> dict;
        vector<bool> dp(s.length() + 1, false);
        dp[0] = true;
        for (string &word : wordDict)
        {
            dict.insert(word);
        }
        for (int i = 0; i < s.length(); i++)
        {
            string tmp;
            for (int j = i; j >= 0; j--)
            {
                tmp = s.substr(j, i - j + 1);
                if (dict.find(tmp) != dict.end() &&
                    dp[j])
                {
                    dp[i + 1] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
};

300、最长递增子序列——动态规划

创建一个长度为n的整数向量dp，并将所有元素初始化为1，表示任意单个元素都可以作为递增子序列。

使用两层循环遍历向量nums。外层循环遍历每个元素nums[i]，内层循环遍历i之前的每个元素nums[j]。如果nums[j] < nums[i]，说明可以将nums[i]加入到以nums[j]结尾的递增子序列中，从而形成以nums[i]结尾的更长的递增子序列。因此，更新dp[i] = max(dp[i], dp[j] + 1)，表示取当前最长递增子序列长度和加入nums[i]后的长度的最大值。

最后，使用max_element函数找到dp中的最大值，并返回作为结果，即最长递增子序列的长度。

class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        int n = (int)nums.size();
        if (n == 0)
        {
            return 0;
        }
        vector<int> dp(n, 1);
        for (size_t i = 0; i < n; i++)
        {
            for (size_t j = 0; j < i; j++)
            {
                if (nums[j] < nums[i])
                {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
};

152、乘积最大子数组——动态规划

需要注意的是，负数乘以负数，会变成正数，因此我们除了保存当前元素的最大乘积，还要保存最小乘积，万一后面来了个负数当前最小值就变成最大值了。

dp[i][0]表示以nums[i]结尾的子数组的最大乘积，dp[i][1]表示以nums[i]结尾的子数组的最小乘积，dp[i][2]表示截止到nums[i]的子数组的最大乘积。从1开始遍历nums的元素，依次计算dp[i][0]、dp[i][1]和dp[i][2]的值。

最后返回dp[nums.size() - 1][2]，即截止到最后一个元素的子数组的最大乘积。

class Solution
{
public:
    int maxProduct(vector<int> &nums)
    {
        vector<vector<int>> dp(nums.size(), vector<int>(3, 0));
        dp[0][0] = nums[0];
        dp[0][1] = nums[0];
        dp[0][2] = nums[0];
        for (size_t i = 1; i < nums.size(); i++)
        {
            dp[i][0] = max(dp[i - 1][0] * nums[i], nums[i]);
            dp[i][0] = max(dp[i][0], dp[i - 1][1] * nums[i]);
            dp[i][1] = min(dp[i - 1][1] * nums[i], nums[i]);
            dp[i][1] = min(dp[i][1], dp[i - 1][0] * nums[i]);
            dp[i][2] = max(dp[i][0], dp[i - 1][2]);
        }
        return dp[nums.size() - 1][2];
    }
};

416、分割等和子集——动态规划

简单回溯

判断是否总和为偶数，如果不是则返回false，否则回溯寻找数组是否有何为总和一半的子集。

超时了

class Solution
{
public:
    bool backtrack(vector<int> &nums,
                   int target,
                   int tmp,
                   int idx)
    {
        if (tmp == target)
        {
            return true;
        }
        bool ret = false;
        for (size_t i = idx; i < nums.size(); i++)
        {
            tmp += nums[i];
            ret |= backtrack(nums, target, tmp, i + 1);
            tmp -= nums[i];
        }
        return ret;
    }

    bool canPartition(vector<int> &nums)
    {
        int sum = 0;
        for (int &num : nums)
        {
            sum += num;
        }
        if (sum % 2 != 0)
        {
            return false;
        }
        int half = sum / 2;
        return backtrack(nums, half, 0, 0);
    }
};

动态规划

首先计算数组nums的所有元素的总和，如果总和是奇数，那么无法等分，直接返回false。

创建一个二维布尔数组dp，其中dp[i][j]表示在前i个元素中是否存在一个子集的和等于j。将dp数组的第一列初始化为true，表示可以选择不取任何元素得到和为0。

遍历数组nums的每个元素，对于第i个元素，遍历和的范围从0到half（总和的一半），其中half是总和的一半，因为如果有一个子集的和等于half，那么另一个子集的和也必然等于half。

对于每个子问题dp[i][j]，可以根据上一个子问题dp[i-1][j]的结果进行填表。如果dp[i-1][j]为true，则dp[i][j]也为true，表示不选择第i个元素。同时，如果j + nums[i] <= half，则可以选择第i个元素，将dp[i-1][j]的true传递到dp[i][j+nums[i]]，表示选择第i个元素。在填表的过程中，如果出现dp[i][j]等于true且j等于half，表示存在一个子集的和等于half，直接返回true。

最后返回dp[nums.size()-1][half]，即最后一个元素对应的子问题的解，表示是否存在一个子集的和等于half。

class Solution
{
public:
    bool canPartition(vector<int> &nums)
    {
        int sum = 0;
        for (int &num : nums)
        {
            sum += num;
        }
        if (sum % 2 != 0 || nums.empty())
        {
            return false;
        }
        int half = sum / 2;
        vector<vector<bool>> dp(nums.size(), vector<bool>(half + 1, false));
        for (size_t i = 0; i < nums.size(); i++)
        {
            dp[i][0] = true;
        }
        if (nums[0] <= half)
        {
            if (nums[0] == half)
            {
                return true;
            }
            dp[0][nums[0]] = true;
        }
        for (size_t i = 1; i < nums.size(); i++)
        {
            for (size_t j = 0; j < half + 1; j++)
            {
                dp[i][j] = dp[i - 1][j] == true ? true : dp[i][j];
                if (dp[i - 1][j] && j + nums[i] <= half)
                {
                    if (j + nums[i] == half)
                    {
                        return true;
                    }
                    dp[i][j + nums[i]] = true;
                }
            }
        }
        return dp[nums.size() - 1][half];
    }
};

32、最长有效括号——栈

使用一个栈（stack<int> stk）来存储括号的索引位置。初始化栈，将-1压入栈中，表示起始位置。保持栈顶元素为最后一个没有被匹配元素的索引。

遍历字符串s：

如果当前字符是右括号’)’，则判断栈顶元素是否为左括号'(‘。
- 如果栈顶元素为左括号，则表示找到了一个有效的括号子串。
  - 弹出栈顶元素。
  - 计算当前有效括号子串的长度cur，即当前位置i减去新的栈顶元素（最后一个没有被匹配元素的索引）。
  - 更新最长有效括号子串的长度ret，取ret和cur的较大值。
- 如果栈顶元素不为左括号，则将当前右括号的索引位置i压入栈中（更新最后一个没有被匹配元素的索引）。

最后返回ret

class Solution
{
public:
    int longestValidParentheses(string s)
    {
        int cur = 0;
        int ret = 0;
        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.length(); i++)
        {
            if (s[i] == ')')
            {
                if (stk.top() != -1 && s[stk.top()] == '(')
                {
                    stk.pop();
                    cur = i - stk.top();
                    ret = max(ret, cur);
                }
                else
                {
                    stk.push(i);
                }
            }
            else
            {
                stk.push(i);
            }
        }
        return ret;
    }
};

169、多数元素——位运算

遍历数组中最大元素的位数0-cnt，在内层遍历所有num的第i位，记录下是0多还是1多，由于结果的出现次数一定大于n/2，故结果该位一定是0、1中更多的那一个。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int ret = 0;
        int max = 0;
        for(int num:nums){
            if(num > max){
                max = num;
            }
        }
        bitset<sizeof(max) * 8> binary(max);
        int cnt;
        cnt = binary.size();
        for(int i = 0;i<cnt;i++){
            int zero = 0;
            int one = 0;
            for(int num:nums){
                if(num & (1 << i)){
                    one++;
                }else{
                    zero++;
                }
            }
            if(one > zero){
                ret |= (1 << i);
            }
        }
        return ret;
    }
};

5、最长回文子串——动态规划

创建一个二维布尔型向量 dp，大小为 len × len，其中 dp[i][j] 表示从下标 i 到下标 j 的子串是否为回文串。初始化对角线上的元素，即 dp[i][i]，它们都是单个字符，因此都是回文串。

使用两层循环遍历子串的长度 i，从 2 开始，直到字符串的长度 len。外层循环控制子串的长度，内层循环控制子串的起始位置。判断子串的起始位置 j 和结束位置 j + i - 1 处的字符是否相等。

如果相等，说明子串的首尾字符相同，需要进一步判断去掉首尾字符后的子串是否为回文串。
- 如果子串长度 i 为 2，即只有两个字符，那么去掉首尾字符后为空串，因此子串一定为回文串。
- 如果子串长度 i 大于 2，那么去掉首尾字符后的子串就是下标范围从 j+1 到 j+i-2 的子串，需要查看 dp[j+1][j+i-2] 的值。
如果子串是回文串，将 dp[j][j+i-1] 设置为 true。
如果 dp[j][j+i-1] 为 true，更新 ret 的值为当前子串的起始位置和结束位置。

最后返回字符串 s 中 ret 范围内的子串，即最长回文子串。

class Solution
{
public:
    string longestPalindrome(string s)
    {
        int len = s.length();
        pair<int, int> ret = {0, 0};
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        for (size_t i = 0; i < len; i++)
        {
            dp[i][i] = true;
        }
        // 子串长度
        for (size_t i = 2; i <= len; i++)
        {
            // 从0开始遍历长度为i的子串
            for (size_t j = 0; j <= len - i; j++)
            {
                if (s[j] == s[j + i - 1])
                {
                    if (i == 2)
                    {
                        dp[j][j + i - 1] = true;
                    }
                    else
                    {
                        dp[j][j + i - 1] = dp[j + 1][j + i - 2];
                    }
                    if (dp[j][j + i - 1])
                    {
                        ret = {j, j + i - 1};
                    }
                }
            }
        }

        return s.substr(ret.first, ret.second - ret.first + 1);
    }
};

1143、最长公共子序列——动态规划

二维向量dp，大小为(len1 + 1) × (len2 + 1)，并初始化所有元素为0。

使用两个嵌套的循环遍历dp的所有位置，其中i的范围是从1到len1，j的范围是从1到len2。每个位置(i, j)，判断text1[i-1]和text2[j-1]是否相等，如果相等，则将dp[i][j]更新为dp[i-1][j-1] + 1，表示在当前位置上的最长公共子序列的长度比前一个位置上的长度多1。如果text1[i-1]和text2[j-1]不相等，则将dp[i][j]更新为dp[i-1][j]和dp[i][j-1]中的较大值，表示在当前位置上的最长公共子序列的长度与左边位置和上边位置的最长公共子序列长度的较大值相同。

class Solution
{
public:
    int longestCommonSubsequence(string text1,
                                 string text2)
    {
        int len1 = text1.length();
        int len2 = text2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (size_t i = 1; i < len1 + 1; i++)
        {
            for (size_t j = 1; j < len2 + 1; j++)
            {
                if (text1[i - 1] == text2[j - 1])
                {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else
                {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }
};

72、编辑距离——动态规划

二维数组 dp，其中 dp[i][j] 表示将 word1 的前 i 个字符转换为 word2 的前 j 个字符所需的最小编辑距离。初始化边界条件，即当一个字符串为空时，将另一个字符串的长度作为编辑距离。因此，对于 dp[0][i] 和 dp[i][0]，它们的值都等于 i。

使用两个嵌套的循环遍历 dp 数组的每个元素。对于每个位置 (i, j)，考虑当前字符 word1[i-1] 和 word2[j-1]。首先考虑这两个字符不相等，通过插入、删除或替换操作来使它们相等，所以 dp[i][j] 可以通过 dp[i-1][j-1]（替换操作）、dp[i-1][j]（删除操作）和 dp[i][j-1]（插入操作）中的最小值加 1 得到。如果这两个字符相等，因此 dp[i][j] 可以由 dp[i-1][j-1] 直接得到，故 dp[i][j] 为 dp[i][j] 和 dp[i-1][j-1] 二者的最小值。

返回 dp[len1][len2]

class Solution
{
public:
    int minDistance(string word1, string word2)
    {
        int len1 = word1.length();
        int len2 = word2.length();
        vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
        for (size_t i = 0; i < len2 + 1; i++)
        {
            dp[0][i] = i;
        }

        for (size_t i = 0; i < len1 + 1; i++)
        {
            dp[i][0] = i;
        }

        for (size_t i = 1; i < len1 + 1; i++)
        {
            for (size_t j = 1; j < len2 + 1; j++)
            {
                dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1;
                if (word1[i - 1] == word2[j - 1])
                {
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);
                }
            }
        }
        return dp[len1][len2];
    }
};

75、颜色分类——排序

冒泡排序

class Solution
{
public:
    void sortColors(vector<int> &nums)
    {
        for (size_t i = 0; i < nums.size() - 1; i++)
        {
            for (size_t j = 0; j < nums.size() - i - 1; j++)
            {
                if (nums[j] > nums[j + 1])
                {
                    swap(nums[j], nums[j+1]);
                }
            }
        }
    }
};

31、下一个排列

如果一个序列是递减的，那么他就是最大的序列，否则是最小的序列。

所以将本题的问题简化，就是从右边开始向左遍历，找到从右边开始的第一个递减的数 n 下标为 i，此时 i 右边的子序列已经是当前子序列的最大排列，所以要让当前排列变大同时保证变大的幅度尽可能小，就将 n 与右边大于 n 的最小数交换，这样新的序列不论下标 i 之后的数字排序如何，都大于原来的序列。但是修改后，i 右边的子序列本来已经是最大排列了，但是 i 位比原来的大已经足够了，所以转置 i 右边的子序列即可。

class Solution
{
public:
    /**
     * 最大-递减序列
     * 最小-递增序列
     *
     * 所以本题的实质就是从右边开始向左遍历
     * 找到从右边开始的第一个递减的数n 下标为 i
     * 然后将n与右边大于n的最小数交换，
     * 这样新的序列不论下标 i 之后的数字排序如何，都大于原来的序列
     * 所以要让新序列是下一个序列，只需要让下标 i 之后的数字是从左往右递增的即可（最小）
     **/
    void nextPermutation(vector<int> &nums)
    {
        int find = -1;
        for (int i = nums.size() - 2; i >= 0; i--)
        {
            if (nums[i + 1] > nums[i])
            {
                find = i;
                cout<<find<<endl;
                while (i + 1 < nums.size() && nums[i + 1] > nums[find])
                {
                    i++;
                }
                cout<<i<<endl;
                swap(nums[find], nums[i]);
                for (int j = find + 1; j < find + 1 + (nums.size() - find - 1) / 2; j++)
                {
                    swap(nums[j], nums[nums.size()+ find + 1 - j - 1]);
                }
                return;
            }
        }
        if (find == -1)
        {
            for (int i = 0; i < nums.size() / 2; i++)
            {
                swap(nums[i], nums[nums.size() - i - 1]);
            }
        }
    }
};

------本页内容已结束，喜欢请分享------

文章作者

能不能吃完饭再说

隐私政策

PrivacyPolicy

用户协议

UseGenerator

许可协议

NC-SA 4.0

文章版权归作者所有，未经允许请勿转载。

THE END