这是 labuladong 的算法小抄 的刷题记录。每一节选一道代表题目，方便快速复习。

LeetCode上的 Debug 小技巧

补充一个在LeetCode网页上刷题的时候的 Debug 技巧。因为非会员在 LeetCode 上没有调试功能，所以我们只能 print 打印一些关键变量的值。

但是如果遇到递归算法的时候，直接打印变量会十分混乱。 这里提供一个十分好用的方法。

首先我们需要定义一个函数 debug 和一个全局变量 _count，然后在递归函数开始时执行debug(_count++) 在递归函数结束前执行debug(--_count)。然后在中间我们就可以正常打印我们需要的关键变量。debug函数如下：

// 调试
int _count = 0;
void debug(int count){
    // 打印 count 个缩进
    for(int i = 0; i < count; i++){
        printf("    ");
    }
    // 这句可以不写
    printf("[%d] ", count);
}

我们以一个较为复杂的题目 236. 二叉树的最近公共祖先 为例，递归版本的算法如下：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return dfs(root, p, q);
    }
private:
    TreeNode* dfs(TreeNode *root, TreeNode *p, TreeNode *q){
        if(root == nullptr){
            return nullptr;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode *left = dfs(root->left, p, q);
        TreeNode *right = dfs(root->right, p, q);

        if(left != nullptr && right != nullptr){
            return root;
        } 
        return left == nullptr ? right : left;
    }
};

我们进行 debug 打印关键变量的信息：

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        return dfs(root, p, q);
    }
private:
    // 调试
    int _count = 0;
    void debug(int count){
        // 打印 count 个缩进
        for(int i = 0; i < count; i++){
            printf("    ");
        }
        // 这句可以不写
        printf("[%d] ", count);
    }

    TreeNode* dfs(TreeNode *root, TreeNode *p, TreeNode *q){
        // 函数开始时调用debug，并打印当前节点的信息
        debug(_count++);
        cout<<"node: ";
        root == nullptr ? cout<<"nullptr"<<endl : cout<<root->val<<endl;

        if(root == nullptr){
            // 函数结束时调用debug，并打印返回值的信息
            debug(--_count);
            cout<<"retrun nullptr"<<endl;

            return nullptr;
        }
        if(root == p || root == q){
            // 函数结束时调用debug，并打印返回值的信息
            debug(--_count);
            cout<<"return "<<root->val<<endl;

            return root;
        }
        TreeNode *left = dfs(root->left, p, q);
        TreeNode *right = dfs(root->right, p, q);

        if(left != nullptr && right != nullptr){
            // 函数结束时调用debug，并打印返回值的信息
            debug(--_count);
            cout<<"return ";
            root == nullptr ? cout<<"nullptr"<<endl : cout<<root->val<<endl;

            return root;
        } 

        // 函数结束时调用debug，并打印返回值的信息
        debug(--_count);
        cout<<"return ";
        TreeNode *node =  left == nullptr ? right : left;
        node == nullptr ? cout<<"nullptr"<<endl : cout<<node->val<<endl;

        return left == nullptr ? right : left;
    }
};

打印结果如下：

/**
* 输入：
* [3,5,1,6,2,0,8,null,null,7,4]
* 5
* 8
*/
[0] node: 3
    [1] node: 5
    [1] return 5
    [1] node: 1
        [2] node: 0
            [3] node: nullptr
            [3] retrun nullptr
            [3] node: nullptr
            [3] retrun nullptr
        [2] return nullptr
        [2] node: 8
        [2] return 8
    [1] return 8
[0] return 3

可以看到这种方法可以很直观地看出递归的过程，我们很容易就能分析出这个算法的执行流程。

第零章、核心框架汇总

第一章、手把手刷数据结构

1. 手把手刷链表算法

🎁合并链表：23. 合并K个升序链表

剑指 Offer II 078. 合并排序链表

自己写的题解：合并K个升序链表：优先队列

🎁环形链表：142. 环形链表 II

剑指 Offer II 022. 链表中环的入口节点

自己写的题解：环形链表：双指针

🎁相交链表：160. 相交链表

剑指 Offer II 023. 两个链表的第一个重合节点

自己写的题解：相交链表：双指针

🎁反转链表：92. 反转链表 II

自己写的题解：反转链表：递归 - 反转链表 II

🎁K个一组反转链表：25. K 个一组翻转链表

自己写的题解：K个一组反转链表

🎁回文链表：234. 回文链表

自己写的题解：回文链表：反转链表 + 链表中间结点

2. 手把手刷数组算法

🎁前缀和：304. 二维区域和检索 - 矩阵不可变

难度简单

class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        arr.resize(matrix.size() + 1, vector<int>(matrix[0].size()+1, 0)); 
        for(int i = 1; i < arr.size(); i++){
            for(int j = 1; j < arr[0].size(); j++){
                arr[i][j] = matrix[i-1][j-1] + arr[i-1][j] + arr[i][j-1] - arr[i-1][j-1];
            }
        }
    }
    
    int sumRegion(int row1, int col1, int row2, int col2) {
        return arr[row2+1][col2+1] - arr[row2+1][col1] - arr[row1][col2+1] + arr[row1][col1];
    }
private:
    vector<vector<int>> arr;
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

🎁差分数组：1094. 拼车

难度==中等==

class Difference{
private:
    vector<int> diff;
public:
    Difference(int n){
        diff.resize(n, 0);
    }

    void increment(int i, int j, int val){
        diff[i] += val;
        if(j + 1 < diff.size()){
            diff[j + 1] -= val;
        }
    }

    vector<int> result(){
        vector<int> res(diff.size(), 0);
        res[0] = diff[0];
        for(int i = 1; i < res.size(); i++){
            res[i] = res[i-1] + diff[i];
        }
        return res;
    }

};

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        Difference diff(1001);
        for(int i = 0; i < trips.size(); i++){
            int val = trips[i][0];
            int start = trips[i][1];
            int end = trips[i][2]-1;

            diff.increment(start, end, val);
        }
        vector<int> res = diff.result();
        for(int i = 0; i < res.size(); i++){
            if(res[i] > capacity){
                return false;
            }
        }
        return true;
    }
};

🎁双指针-重复元素：26. 删除有序数组中的重复项

难度简单

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow = 0, fast = 0;
        while(fast < nums.size()){
            if(/* fast指针找到满足条件的元素 */){
                // 将元素放在slow指针处
                slow++;
            }
            fast++;
        }
        return slow+1;
    }
}

🎁二维数组的花式遍历：54. 螺旋矩阵

难度==中等==

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        int upper = 0, lower = m - 1, left = 0, right = n - 1;
        vector<int> res;
        while(res.size() < m*n){
            if(upper <= lower){
                for(int j = left; j <= right; j++){
                    res.push_back(matrix[upper][j]);
                }
                upper++;
            }

            if(left <= right){
                for(int i = upper; i <= lower ; i++){
                    res.push_back(matrix[i][right]);
                }
                right--;
            }

            if(upper <= lower){
                for(int j = right; j >= left; j--){
                    res.push_back(matrix[lower][j]);
                }
                lower--;
            }

            if(left <= right){
                for(int i = lower; i >= upper; i--){
                    res.push_back(matrix[i][left]);
                }
                left++;
            }
        }
        return res;
    }
};

🎁滑动窗口：76. 最小覆盖子串

难度==困难==

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;

        for(char c : t){
            need[c]++;
        }
        
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = INT_MAX;
        while(right < s.size()){
            char c = s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]){
                    valid++;
                }
            }

            while(valid == need.size()){
                if(right - left < len){
                    start = left;
                    len = right - left;
                }

                char d = s[left];
                left++;

                if(need.count(d)){
                    if(window[d] == need[d]){
                        valid--;
                    }
                    window[d]--;
                }
            }
        } 

        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

🎁二分查找：704. 二分查找

自己写的题解：二分查找模版总结

🎁带权重的随机选择算法：528. 按权重随机选择

难度==中等==

class Solution {
public:
    Solution(vector<int>& w) {
        presum.resize(w.size() + 1, 0);
        for(int i = 1; i < presum.size(); i++){
            presum[i] = presum[i - 1] + w[i - 1];
        }
    }
    
    int pickIndex() {
        int n = presum.size();
        int target = rand() % presum[n - 1] + 1; 
        return left_bound(presum, target) - 1;    
    }
private:
    vector<int> presum;
    int left_bound(vector<int> &presum, int target){
        int left = 0, right = presum.size() - 1;
        while(left <= right){
            int mid = (right - left)/2 + left;
            if(presum[mid] < target){
                left = mid + 1;
            } else if(presum[mid] > target){
                right = mid - 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

🎁二分搜索应用：875. 爱吃香蕉的珂珂

难度==中等==

class Solution {
public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1, right = *max_element(piles.begin(), piles.end());
        while(left <= right){
            int mid = (right - left)/2 + left;
            if(finishtime(piles, mid) > h){
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

private:
    int finishtime(vector<int> &piles, int speed){
        int sum = 0;
        for(int i = 0; i < piles.size(); i++){
            sum += (piles[i] + speed - 1) / speed;
        }
        return sum;
    }
};

🎁田忌赛马：870. 优势洗牌

难度==中等==

class Solution {
public:
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;

        for(int i = 0; i < nums2.size(); i++){
            q.push(make_pair(nums2[i], i));
        }
        
        int n = nums1.size();
        int left = 0, right = n - 1; 
        vector<int> res(n, 0);
        while(!q.empty()){
            int maxval = q.top().first;
            int index = q.top().second;
            q.pop();
            if(maxval < nums1[right]){
                res[index] = nums1[right];
                right--;
            } else {
                res[index] = nums1[left];
                left++;
            }
        }
        return res;
    }
private:
    struct cmp{
        bool operator()(pair<int, int> p1, pair<int, int> p2){
            return p1.first < p2.first;
        }
    };
};

🎁常数时间删除/查找数组中的任意元素：380. O(1) 时间插入、删除和获取随机元素 + 710. 黑名单中的随机数

自己写的题解：O(1) 时间插入、删除和获取随机元素：变长数组+哈希表 + 黑名单中的随机数：哈希表 - 黑名单中的随机数 - 力扣（LeetCode）

🎁单调栈：316. 去除重复字母

由浅入深，单调栈思路去除重复字符 - 去除重复字母 - 力扣（LeetCode）

改进：可以直接将 res 做为单调栈，不用另开辟空间

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<bool> inStack(256, false);
        vector<int> count(256, 0);
        string res;
        
        for(char c : s){
            count[c]++;
        }

        for(char c : s){
            count[c]--;
            if(inStack[c]){
                continue;
            }            
            while(!res.empty() && res[res.size() - 1] > c){
                if(count[res[res.size() - 1]] == 0){
                    break;
                }
                inStack[res[res.size() - 1]] = false;
                res.pop_back();
            }
            res += c;
            inStack[c] = true;
        }

        return res;
    }
};

3. 手把手刷二叉树算法

🎁后序遍历解决二叉树深度问题：543. 二叉树的直径

自己写的题解：二叉树的直径：后序遍历解决二叉树深度问题

🎁后序遍历应用：114. 二叉树展开为链表

自己写的题解：二叉树展开为链表：后序遍历

🎁前序遍历应用：116. 填充每个节点的下一个右侧节点指针

自己写的题解：填充每个节点的下一个右侧节点指针：DFS

🎁构造二叉树：105. 从前序与中序遍历序列构造二叉树

自己写的题解：二叉树的构造问题解题方法

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

自己写的题解：二叉树的序列化与反序列化：DFS+BFS - 二叉树的序列化与反序列化 - 力扣（LeetCode）

🎁后序遍历+序列化：652. 寻找重复的子树

自己写的题解：寻找重复的子树：后序遍历+序列化二叉树 - 寻找重复的子树 - 力扣（LeetCode）

🎁排序算法：912. 排序数组

自己写的题解：排序算法

🎁归并排序解决逆序对问题：剑指 Offer 51. 数组中的逆序对

自己写的题解：数组中的逆序对：归并排序

🎁二叉搜索树的性质：538. 把二叉搜索树转换为累加树

自己写的题解：把二叉搜索树转换为累加树：中序遍历

🎁二叉搜索树的增删改查操作：700. 二叉搜索树中的搜索

自己写的题解：二叉搜索树的增删改查操作

🎁构造二叉搜索树：96. 不同的二叉搜索树

自己写的题解：不同的二叉搜索树：暴力搜索 + 优化 = 动态规划

🎁快速选择算法：215. 数组中的第K个最大元素

自己写的题解：数组中的第k个最大元素：优先队列 + 快速选择算法

🎁二叉树的最近公共节点：236. 二叉树的最近公共祖先

自己写的题解：二叉树的最近公共祖先大集合：后序遍历

🎁完全二叉树的节点个数：222. 完全二叉树的节点个数

自己写的题解：完全二叉树的节点个数：普通二叉树 + 满二叉树

4. 手把手刷图算法

🎁图论基础：797. 所有可能的路径

自己写的题解：797. 所有可能的路径：图的回溯

🎁二分图：785. 判断二分图

自己写的题解：判断二分图：DFS

🎁判断图是否有环：207. 课程表

自己写的题解：判断图是否有环：图的回溯

🎁拓扑排序：210. 课程表 II

自己写的题解：图的拓扑排序：判断图是否有环+图的后序遍历

🎁岛屿问题：130. 被围绕的区域

自己写的题解：被围绕的区域：DFS + 并查集

🎁并查集：130. 被围绕的区域

自己写的题解：被围绕的区域：DFS + 并查集

🎁最小生成树：1584. 连接所有点的最小费用

自己写的题解：最小生成树：Kruskal + Prim - 连接所有点的最小费用 - 力扣（LeetCode）

🎁最短路径：

5. 手把手设计数据结构

🎁单调栈： 496. 下一个更大元素 I

自己写的题解：496. 下一个更大元素 I：单调栈

🎁LRU 算法：146. LRU 缓存

自己写的题解：LRU缓存：哈希表+双向链表

🎁单调队列结构解决滑动窗口问题：239. 滑动窗口最大值

自己写的题解：滑动窗口最大值：堆（优先队列）、单调队列 - 滑动窗口最大值

🎁设计朋友圈时间线功能：355. 设计推特

自己写的题解：设计推特：哈希表+链表+优先队列

第二章、手把手刷动态规划

1. 动态规划基本技巧

🎁动态规划核心原理：322. 零钱兑换

自己写的题解：零钱兑换：动态规划

🎁动态规划设计方法：300. 最长递增子序列

自己写的题解：最长递增子序列：动态规划+二分查找

🎁base case 的初始值如何设置：931. 下降路径最小和

自己写的题解：下降路径最小和：动态规划 - 下降路径最小和 - 力扣（LeetCode）

2. 子序列类型问题

🎁编辑距离：72. 编辑距离

自己写的题解：编辑距离：动态规划

3. 背包问题

🎁0-1背包问题：

问题描述： 给你一个可装载重量为 W 的背包和 N 个物品，每个物品有重量和价值两个属性。其中第 i 个物品的重量为 wt[i]，价值为 val[i]，现在让你用这个背包装物品，最多能装的价值是多少？

int knapsack(int w, int n, vector<int> &wt, vector<int> &val) {
    vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
//         for(int i = 0; i < dp.size(); i++){
//             dp[i][0] = 0;
//         }
    for(int i = 1; i < dp.size(); i++){
        for(int j = 1; j < dp[0].size(); j++){
            if(j - wt[i-1][0] < 0){
                dp[i][j] = dp[i - 1][j];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt[i-1][0]] + val[i-1][1]);
            }
        }
    }
    return dp[n][w];
}

🎁子集背包问题：416. 分割等和子集

自己写的题解：分割等和的子集：0-1 背包问题

🎁完全背包问题：518. 零钱兑换 II

🎁动态规划与回溯：494. 目标和

4. 用动态规划玩游戏

🎁最小路径和：64. 最小路径和

自己写的题解：最小路径和：从记忆化递归到动态规划

🎁魔塔游戏：174. 地下城游戏

自己写的题解：地下城游戏：DFS＋后序遍历+动态规划思想

🎁正则表达式匹配：10. 正则表达式匹配

自己写的题解：正则表达式匹配：递归 + 记忆化 = 动态规划

🎁打家劫舍问题：198. 打家劫舍

自己写的题解：打家劫舍：经典动态规划问题

🎁股票问题：121. 买卖股票的最佳时机

自己写的题解：状态机解决所有股票问题！！！ - 买卖股票的最佳时机 - 力扣（LeetCode）

🎁KMP 字符匹配算法：28. 实现 strStr()

自己写的题解：实现 strStr()：KMP 算法

5. 贪心类型问题

🎁区间调度问题：435. 无重叠区间

自己写的题解：无重叠区间：贪心算法

第三章、必知必会算法技巧

1. 暴力搜索算法

🎁回溯算法：51. N 皇后

自己写的题解：N皇后：回溯

🎁回溯算法解决排列组合和子集问题：46. 全排列

自己写的题解：回溯问题大合集：子集、组合、排列

🎁回溯算法解决集合划分问题：698. 划分为k个相等的子集 - 力扣（LeetCode）

自己写的题解：集合划分问题：回溯 - 划分为k个相等的子集

🎁BFS 算法：752. 打开转盘锁

自己写的题解：最短路径：广度优先搜索 - 打开转盘锁

2. 经典面试题

🎁分治算法：为运算符表达式设计优先级

自己写的题解：为运算符表达式设计优先级：分治算法 - 为运算表达式设计优先级

🎁接雨水：42. 接雨水

自己写的题解：接雨水：动态规划+双指针+单调栈