LeetCode刷题总结

本文最后更新于 2025年9月20日 凌晨

简介

本文是在求职过程中，跟随代码随想录练习LeetCode题目（C++）所形成的笔记，记录下来以备后续使用。本文大体结构与代码随想录一致，并辅以C++基础教程的相关知识。

灰色引用是LeetCode题号，部分带链接。

数组

数组理论基础

数组是存放在连续内存空间上的相同类型数据的集合。在删除或者增添元素的时候，就难免要移动其他元素的地址。在C++中二维数组在地址空间上是连续的。
复习时记得回看C++数组以及vector的相关函数。

二分法

在有序数组中查找元素，并且没有重复元素。使用left、right两个指针。需要清楚区间的定义，是左闭右闭还是左闭右开（建议左闭右闭）。要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。时间复杂度为O(logn)

704.二分查找

双指针法

（快慢指针法）：通过两个指针在一个for循环下完成两个for循环的工作，来降低时间复杂度。要搞清楚每个指针在什么条件下移动，什么条件下不移动。

27.移除元素，977.有序数组的平方，844.有序数组的平方

滑动窗口法

也属于双指针法，所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。首先想起始位置和终止位置移动会分别带来什么影响，然后要确定窗口内是什么，窗口的起始位置的移动规则，窗口的结束位置的移动规则。

209.长度最小的子数组，904.水果成篮，76.最小覆盖子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int minSubArrayLen(int s, vector<int>& nums) {
    int result = INT32_MAX;
    int sum = 0; // 滑动窗口数值之和
    int i = 0; // 滑动窗口起始位置
    int subLength = 0; // 滑动窗口的长度
    for (int j = 0; j < nums.size(); j++) {
        sum += nums[j];
        // 注意这里使用while，每次更新 i（起始位置），并不断比较子序列是否符合条件
        while (sum >= s) {
            subLength = (j - i + 1); // 取子序列的长度
            result = result < subLength ? result : subLength;
            sum -= nums[i];
            i++;
            // 起始位置的移动规则：sum>=s，需要缩小滑动窗口之和，寻找是否存在j结尾的长度更小的子数组
        }
        // 结束位置的移动规则：sum<s，需要增大滑动窗口之和，j后移  (while循环结束后sum就会小于s)
    }
    // 如果result没有被赋值的话，就返回0，说明没有符合条件的子序列
    return result == INT32_MAX ? 0 : result;
}

模拟行为

循环不变量原则，是写程序中的重要原则。确定模拟过程中遵循的规则。

59.螺旋矩阵II，54.螺旋矩阵

链表

链表理论基础

链表的节点在内存中是分散存储的，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null。双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。循环链表，顾名思义，就是链表首尾相连。
链表的操作：

  • 删除节点：定位到删除节点的前一个节点，保存->next为tmp，将->next域设为->next->next，delete tmp。
  • 添加节点：定位到添加位置的前一个位置p，new一个新节点，next域设为p->next，p->next设为新节点地址。

技巧：多画图模拟过程，考虑极端情况，包括：链表长为0，长为1，头结点位置，尾结点位置等

虚节点/哨兵节点

使用一个头结点之前虚节点（dummyNode）可以有效简化删除/添加节点时需要考虑头部位置的情况。

203.移除链表元素，707.设计链表

双指针法

常见的方式有prev与cur两个相差一步的指针（206、24）、slow与fast两个相差若干步的指针（19、面试02.07）、slow每次走一步fast每次走两步（142）

206.反转链表、24.两两交换链表中的节点

19.删除链表的倒数第N个节点、面试题 02.07.链表相交

142.环形链表II

哈希表

理论基础

一般来说哈希表都是用来快速判断一个元素是否出现集合里。对于哈希表，要知道哈希函数和哈希碰撞在哈希表中的作用。哈希函数是把传入的key映射到哈希表的索引上。哈希碰撞处理有多个key映射到相同索引上时的情景，处理碰撞的普遍方式是拉链法和线性探测法。

接下来是常见的三种哈希结构：

  • 数组
  • set（集合）
  • map（映射）

集合set是一组同类型数据的集合，unordered_set类似于python中的set。映射map是一组（key，value）键值对（pair类型）的集合，unordered_map类似于python的dict、java的hashmap。在C++中，set 和 map 分别提供以下三种数据结构：

集合 底层实现 是否有序 数值能否重复 能否更改数值 查询效率 增删效率
set 红黑树 有序 否 否 O(logn) O(logn)
multiset 红黑树 有序 是 否 O(logn) O(logn)
unordered_set 哈希表 无序 否 否 O(1) O(1)
映射 底层实现 是否有序 键值能否重复 能否更改数值 查询效率 增删效率
map 红黑树 key有序 key不可重复 key不可修改 O(logn) O(logn)
multimap 红黑树 key有序 key可重复 key不可修改 O(logn) O(logn)
unordered_map 哈希表 key无序 key不可重复 key不可修改 O(1) O(1)

以上六种常用的是unordered_set，unordered_map。具体接口可查询：unordered_set、unordered_map

数组作为哈希表

数组本身也是一种哈希表或者说map。在一些涉及到字母等的题目中，哈希表元素个数有限（如26个字母），就可以用数组作为简便的哈希表，使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算，所以数组更加简单直接有效。

242.有效的字母异位词、383.赎金信

set作为哈希表

在一些需要以较低的时间复杂度判断元素是否在一个集合中，或者是否重复出现过，就可以用unordered_set做容器。

349.两个数组的交集、202.快乐数

map作为哈希表

map是一种<key, value>的结构，在一些合适的题中很有用，如两数之和（1）、四数相加（454）。但一些题中哈希法太过复杂，反而适合用双指针法，如三数之和（15）、四数之和（18），这两题值得重点关注。

1.两数之和、454.四数相加II

字符串

C++字符串：库函数

双指针法

一快一慢两个指针或者一头一尾。
很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。

344.反转字符串、剑指Offer 05.替换空格、151.翻转字符串里的单词

反转系列

基本的字符串反转使用一前一后两个指针，时间复杂度是O(n)。一些题目用到了先整体反转再局部反转（151）和先局部反转再整体反转（剑指Offer58-II.左旋转字符串）的技巧。

151.翻转字符串里的单词、剑指Offer58-II.左旋转字符串

KMP

KMP算法用于在O(n+m)的时间复杂度内在文本串中匹配模式串。核心思想是当字符串不匹配时，利用已经匹配过的失败信息，跳过一些不可能的字符串匹配。需要掌握的要点是：

  • 前缀表/next数组：作用是记录了模式串与文本串不匹配的时候，模式串应该从哪里开始重新匹配。next[i]的含义是在模式串中，下标 i 之前（包括i）的子串中，最长的相同前缀、后缀的长度
  • KMP有两种实现方法，包括next数组与前缀表相同、前缀表统一每位减一，两者等价，下面介绍相同的情况
  • 参考辅助理解KMP：理解KMP
  • KMP可以解决两种经典问题：模式串匹配问题（28.实现 strStr()）、重复子串问题（459.重复的子字符串）
  • KMP包含两部分：快速建立前缀表和利用前缀表进行匹配。

快速建立前缀表：

思路：采用递推的方式求next数组。假设next[ 0~ i-1 ]已知的情况下，求next[ i ]的值。

  1. 初始化：j指向前缀末尾位置，i指向后缀末尾位置，j=0；
  2. 处理前后缀不相同的情况，j不断根据next[j-1]回退，直至s[i]=s[j]或者j=0；
  3. 处理前后缀相同的情况，s[i]=s[j]，前后缀就可以扩展一位，j++，再赋给next[i]；
  4. j 赋值给next[i]

利用前缀表进行匹配：

  1. 定义两个下标j 指向模式串起始位置，i指向文本串起始位置
  2. for循环中i从0开始遍历文本串，如果在j位置匹配失败，j根据前缀表next[j-1]不断回溯，直至匹配成功
  3. 如果匹配成功，i、j后移一位（j+1，i在for循环中+1）
  4. j移动到超出模式串的末尾，表示模式串匹配成功，返回i-模式串长度+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    void getNext(int* next, const string& s){  //next数组与前缀表相同，不减一的做法
        int j=0;  // 1、初始化：j指向前缀末尾位置，i指向后缀末尾位置
        next[0]=j;  // next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）
        for (int i=1; i<s.size(); i++){
            // 每次循环开始时，j的值就是next[i-1]
            while (j>0 && s[i]!=s[j]){  // 2、处理前后缀不相同的情况，j不断根据next[j-1]回退，直至s[i]=s[j]或者j=0
                j=next[j-1];
            }
            if (s[i]==s[j]){  // 3、处理前后缀相同的情况，s[i]=s[j]，前后缀就可以扩展一位，j++（即next[i-1]+1），再赋给next[i]
                j++;
            }
            next[i]=j;  // 4、更新next[i]
        }
    }
    int strStr(string haystack, string needle) {
        if (needle.size()==0){  // 处理特殊情况：模式串长度为0
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);  // 获得next数组，next[i]含义是下标i之前（包括i）的子串中，最长的相同前缀后缀的长度
        int j=0;
        for (int i=0; i<haystack.size(); i++){
            while (j>0 && haystack[i]!=needle[j]){
                j=next[j-1];  // 如果在j位置匹配失败，j根据前缀表next[j-1]不断回溯，直至匹配成功
            }
            if (haystack[i]==needle[j]){
                j++;  // 匹配成功，j前移一位
            }
            if (j==needle.size()){
                return i-needle.size()+1;  // j移动到超出模式串的末尾，表示模式串匹配成功，返回i-模式串长度+1
            }
        }
        return -1;
    }
};

双指针法

双指针法广泛应用于数组、链表、字符串的题目中。

fast & slow

定义一快一慢两个指针，有以下几种思路：

  • fast和slow两个指针根据一些条件移动，复制元素，来模拟数组元素的移动

    27.移除元素、剑指Offer 05.替换空格、151.翻转字符串里的单词

  • 扩充数组至所需大小后，fast&slow指针从后向前移动

    剑指Offer 05.替换空格

  • fast指针先走几步，fast与slow相差n步，然后两个指针再同步移动

    19.删除链表的倒数第N个节点、面试题 02.07.链表相交

  • fast每次走两步，slow每次走一步，两者在环中相遇

    142.环形链表II

left & right

定义一头一尾两个指针，向中间移动

344.反转字符串、15.三数之和、18.四数之和

pre & cur链表类

在链表中常定义pre & cur两个指针，来进行链表next的修改

206.反转链表、24.两两交换链表中的节点

反转类

字符串的反转，不仅可能用到fast & slow，也可能用到先整体反转再局部反转，或先局部反转再整体反转的方法。

344.反转字符串、151.翻转字符串里的单词、剑指Offer58-II.左旋转字符串

N数之和

先将数组排序，遍历前N-2个数，最后两个数设置left & right两个指针向中间移动，若和小了left向右，和大了right向左。

15.三数之和、18.四数之和

栈与队列

基础知识

栈是先进后出的数据结构，队列是先进先出的数据结构。

stack、queue、priority_queue在STL中属于容器适配器，包装了STL中的基础容器类，本质上还是容器。stack、queue使用的默认基础容器是deque，priority_queue使用的默认基础容器是vector。可以自定义底层容器。

栈和队列不允许有遍历行为，不提供迭代器。

优先级队列与队列相似，只能一端进一端出，但只能访问队头的元素。当元素进入队列后，会进行排序，保证队列按照预定义的优先级排列，默认使用std::less进行从大到小排列。底层采用vector形式的大顶堆/小顶堆。

stack

1
2
3
4
5
6
7
8
9
10
11
12
#include <stack>
using namespace std;
// 不包含任何元素的 stack 适配器，并采用默认的 deque 基础容器
stack<int> values;
// 使用list为基础容器的stack
stack<int, list<int>> values;
// 用一个基础容器来初始化 stack 适配器，只要该容器的类型和 stack 底层使用的基础容器类型相同即可
list<int> values{1, 2, 3};
stack<int, list<int>> my_stack(values);
// 用一个 stack 适配器来初始化另一个 stack 适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可
stack<int, list<int>> my_stack=my_stack1;
//stack<int, list<int>> my_stack(my_stack1);
成员函数 功能
empty() 当 stack 栈中没有元素时，该成员函数返回 true；反之，返回 false。
size() 返回 stack 栈中存储元素的个数。
top() 返回一个栈顶元素的引用，类型为 T&。如果栈为空，程序会报错。
push(const T& val) 先复制 val，再将 val 副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
pop() 弹出栈顶元素。

queue

1
2
3
4
5
6
7
8
9
10
11
12
#include <queue>
using namespace std;
// 不包含任何元素的 queue 适配器，并采用默认的 deque 基础容器
queue<int> values;
// 使用list为基础容器的queue
queue<int, list<int>> values;
// 用一个基础容器来初始化 queue 适配器，只要该容器的类型和 queue 底层使用的基础容器类型相同即可
list<int> values{1, 2, 3};
queue<int, list<int>> my_queue(values);
// 用一个 queue 适配器来初始化另一个 queue 适配器，只要它们存储的元素类型以及底层采用的基础容器类型相同即可
queue<int, list<int>> my_queue=my_queue1;
//queue<int, list<int>> my_queue(my_queue1);
成员函数 功能
empty() 如果 queue 中没有元素的话，返回 true。
size() 返回 queue 中元素的个数。
front() 返回 queue 中第一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
back() 返回 queue 中最后一个元素的引用。如果 queue 是常量，就返回一个常引用；如果 queue 为空，返回值是未定义的。
push(const T& obj) 在 queue 的尾部添加一个元素的副本。这是通过调用底层容器的成员函数 push_back() 来完成的。
pop() 删除 queue 中的第一个元素。

priority_queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <queue>
using namespace std;
// 空的 priority_queue 容器，底层默认 vector 容器，排序方式默认 std::less<T> 方法，即大顶堆
priority_queue<int> values;
//使用普通数组初始化
int values[]{4,1,3,2};
priority_queue<int> copy_values(values,values+4); //{4,2,3,1}
//使用序列式容器初始化
array<int, 4>values{ 4,1,3,2 };
priority_queue<int> copy_values(values.begin(),values.end());//{4,2,3,1}
// 手动指定 priority_queue 使用的底层容器以及排序规则
int values[]{ 4,1,2,3 };
priority_queue<int, deque<int>, greater<int> > copy_values(values, values+4); // 小顶堆
// 用函数对象类自定义排序规则
class Cmp {  // 函数对象类
public:
    bool operator()(const pair<int, int>& left, const pair<int, int>& right){
        return left.second > right.second;  // 小顶堆，从小到大排序
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, Cmp> pri_que;
成员函数 功能
empty() 如果 priority_queue 为空的话，返回 true；反之，返回 false。
size() 返回 priority_queue 中存储元素的个数。
top() 返回 priority_queue 中第一个元素的引用形式。
push(const T& obj) 根据既定的排序规则，将元素 obj 的副本存储到 priority_queue 中适当的位置。
pop() 移除 priority_queue 容器适配器中第一个元素。

栈经典题目

栈在计算机系统、编译器中应用广泛，如：

20.有效的括号、71.简化路径、1047.删除字符串中的所有相邻重复项、150.逆波兰表达式求值

队列经典题目

  • 单调队列

    在 239.滑动窗口最大值 中，需要这样一种队列：队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队里里的元素数值是由大到小的。这就是单调队列，即单调递减或单调递增的队列。设计单调队列的时候，pop和push操作要保持如下规则：

    pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
    push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止。

    239.滑动窗口最大值

  • 优先级队列

    优先级队列就是一个披着队列外衣的堆，因为优先级队列对外接口只是从队头取元素，从队尾添加元素，再无其他取元素的方式，看起来就是一个队列。是大顶堆/小顶堆的现成的实现。

    347.前 K 个高频元素

二叉树

理论基础

  • 满二叉树：一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，深度为k，有2^k-1个节点

  • 完全二叉树：除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置

  • 二叉搜索树是一个有序树，

    • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    • 它的左、右子树也分别为二叉排序树

  • 平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

    红黑树也是一种平衡二叉树，性能优于平衡二叉树。C++中map、set、multimap，multiset的底层实现都是红黑树。

  • 存储方式：二叉树可以链式存储，也可以顺序存储。顺序存储就是用数组来存储二叉树，如果父节点的数组下标是 i，那么它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。链式存储则是通过指针把分布在散落在各个地址的节点串联一起。

  • 遍历方式：

    • 深度优先遍历（DFS）
      • 前序遍历（递归法，迭代法）
      • 中序遍历（递归法，迭代法）
      • 后序遍历（递归法，迭代法）
    • 广度优先遍历（BFS）
      • 层次遍历（迭代法）

其中深度优先的迭代法是用栈的数据结构实现，层次遍历的迭代法是用队列的数据结构实现。

递归遍历（DFS）

写递归算法的三要素：

  • 确定递归函数的参数和返回值： 确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  • 确定终止条件： 写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  • 确定单层递归的逻辑： 确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 前序遍历
class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右   // 前序遍历，中序和后序修改三句话顺序即可
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

迭代遍历（DFS）

使用栈的结构来模拟递归的过程，时间复杂度与递归相同，但空间更小。有两种实现方式，第一种实现三种遍历不一致，不好记；第二种实现加入空指针作为待处理的标记，三种遍历写法统一，更好记。记住一种即可。

注意由于栈的“先进后出”，编写代码时顺序要与前序的“中左右”相反，中/后序同理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 前序遍历
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        stack<TreeNode*> st;
        if (root!=nullptr) st.push(root);
        while (!st.empty()){
            TreeNode* node=st.top();
            if (node!=nullptr){  // 非空指针，表示该节点需要访问但不处理
                st.pop();  // 弹出该节点，接下来访问子节点，但不处理（将该节点加入result）该节点
                if (node->right!=nullptr) st.push(node->right);  // 右
                if (node->left!=nullptr) st.push(node->left);  // 左，注意这里是用栈的结构，顺序与前序遍历的“中左右”相反，应为“右左中”
                st.push(node);  // 中，  再次将该节点压入栈中
                st.push(nullptr);  // 并加上一个空指针表示待处理
                // 中序和后序修改上面四句话的顺序
            }
            else {  // 遇到空指针，表示栈中的下一个节点是待处理的
                st.pop();  // 先弹出空指针
                node=st.top();
                st.pop();
                result.push_back(node->val);  // 处理该节点，加入result
            }
        }
        return result;
    }
};

层序遍历（BFS）

从左到右一层一层的去遍历二叉树，借助“先进先出”的队列的数据结构实现迭代式的写法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> que;
        if (root != NULL) que.push(root);
        vector<vector<int>> result;
        while (!que.empty()) {
            int size = que.size();
            vector<int> vec;
            // 这里一定要使用固定大小size，不要使用que.size()，因为que.size()是不断变化的
            for (int i = 0; i < size; i++) {  // 当不需要输出二维的vector时可以省去size变量和for循环
                TreeNode* node = que.front();
                que.pop();
                vec.push_back(node->val);
                if (node->left) que.push(node->left);
                if (node->right) que.push(node->right);
            }
            result.push_back(vec);
        }
        return result;
    }
};

解题步骤

二叉树类的题目通常有两种思路：递归法和迭代法。

  • 对于递归法，首先要搞清楚递归函数所要实现的功能是什么，然后按照递归算法的三要素来思考。这类做法通常是使用前/中/后序遍历三者之一
  • 对于迭代法，通常是采用队列的数据结构，并采用层序遍历的方式（也有例外，如101.对称二叉树使用迭代法，但不是层序遍历），要记住层序遍历的模板

226.翻转二叉树、101.对称二叉树、104.二叉树的最大深度、111.二叉树的最小深度、222.完全二叉树的节点个数、110.平衡二叉树

二叉树的题目可分为以下几种类型：

  • 求普通二叉树的属性：一般用后序，因为需要用到左右子树的属性来计算本节点的属性，但有例外
  • 二叉树的修改与构造：使用前序，因为需要先构造中节点
  • 求二叉搜索树的属性：使用中序

题目归类：二叉树总结篇

未看的文章：23~33

回溯

理论基础

回溯是递归的副产品，只要有递归就会有回溯，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯法解决的问题都可以抽象为树形结构。因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

回溯法的模板：

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

回溯算法能解决如下问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 棋盘问题：N皇后，解数独等等

组合问题

剪枝技巧：

  • for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了，就没有必要搜索了（77.组合）
  • 已选元素总和如果已经大于n（题中要求的和）了，那么往后遍历就没有意义了，直接剪掉（216.组合总和III）
  • 其他剪枝技巧需要具体问题具体分析

组合问题通常需要startIndex来控制for循环的起始位置，如果是一个集合来求组合的话，就需要startIndex；如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，如：17.电话号码的字母组合。

去重问题：集合元素会有重复，但要求解集不能包含重复的组合。需要理解“同一树枝上重复”与“同一树层上重复”，具体看：40.组合总和II。

77.组合、216.组合总和III、17.电话号码的字母组合、39.组合总和、40.组合总和II、332.重新安排行程

切割问题

类似于组合问题，需要了解string的基本操作。

131.分割回文串、93.复原IP地址

子集问题

在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

78.子集

排列问题

每层都是从0开始搜索而不是startIndex；需要used数组记录path里都放了哪些元素了。

46.全排列

棋盘问题

一些只需要找到一个解的问题（如：37. 解数独、332.重新安排行程），可以将回溯函数的返回值设为bool，当找到解直接用true返回所有递归，代码见链接

51.N皇后、37.解数独

时间/空间复杂度分析

链接

未看的文章：13、14、16、19

贪心算法

理论基础

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。贪心的问题通常是求一个最值，贪心问题没有一个固定套路，只能靠自己手动模拟，如果模拟中用了局部最优推出全局最优的思想，且找不出反例，就可以试一试贪心策略，如果不可行，可能需要动态规划。不需要精确的数学推导。

技巧

  • 有些题目数组是无序的，混乱中并不能产生最值，且题目与元素之间的相对位置无关，此时通常需要先对数组进行排序。需要看一下sort函数自定义排序规则的方式（见452. 用最少数量的箭引爆气球）。

    但一些题目关乎相邻元素的关系、求连续子数组，就不能改变元素位置（如376. 摆动序列、 53. 最大子序和）。

    455.分发饼干、1005.K次取反后最大化的数组和、406.根据身高重建队列、452.用最少数量的箭引爆气球

动态规划

理论基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

对于动态规划问题，拆解为如下五步曲：

  1. 确定dp数组（dp table）以及下标的含义
  2. 确定递推公式（由以往的状态推导出当前的状态，即dp[i-1]或dp[i-2]等推出dp[i]。一般要分情况讨论）
  3. dp数组如何初始化（结合递推公式确定初始化。有时初始化没有实际含义，仅仅是为了保证递推公式）
  4. 确定遍历顺序（for循环顺序，根据递推公式确定，看dp[i]依赖什么）
  5. 举例推导dp数组

做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。写出代码后，如果出问题，把dp数组打印出来，看看究竟是不是按照自己思路推导的。

509.斐波那契数、70. 爬楼梯、746. 使用最小花费爬楼梯、62.不同路径、63. 不同路径 II、343. 整数拆分、96.不同的二叉搜索树

背包问题

01背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解物品价值总和最大是多少。

  • 二维dp数组：

dp数组的定义：dp[i] [j]表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少。

递推公式：dp[i] [j] = max(dp[i - 1] [j], dp[i - 1] [j - weight[i]] + value[i]) 分别对应不取物品i和取物品i的两种情况

初始化：背包容量j为0，即dp[i] [0]，初始化为0；存放编号0的物品，当 j < weight[0]时dp[0] [j] 初始化为0，当j >= weight[0]时dp[0] [j] 初始化为 value[0]。

遍历顺序：先遍历物品再遍历背包容量，或者反过来都可以

1
2
3
4
5
6
for(int i = 1; i < weight.size(); i++) { // 遍历物品
    for(int j = 0; j <= bagweight; j++) { // 遍历背包容量
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}
  • 一维dp数组：

利用滚动数组压缩空间复杂度，每完整刷新一轮数组就是增加了一件物品。

dp数组的定义：容量为j的背包，所背的物品价值可以最大为dp[j]

递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

初始化：背包容量j为0，即dp[0]，初始化为0；其他dp[j]的值随意，但一般也初始化为0。

遍历顺序：先遍历物品并且内层倒序遍历背包容量，不能反过来。倒序是为了保证递推式中用的dp[j - weight[i]]是上一轮的值，即dp[ i - 1 ] [j - weight[i]]。否则每个物品就会多次抽取，就变成了完全背包。

1
2
3
4
5
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

416.分割等和子集、1049. 最后一块石头的重量 II

以上两道道题类似，都是把一组数分成两组，使得两组和的差值最小。做法是对和较小的那一组做DP，转化为容积为sum/2的背包，每个物品的体积和价值都是相同的。dp[sum/2]表示从原数组中选择一部分数，在和不超过sum/2的情况下，所能达到的最大和。由于已经限制了DP部分的和不超过sum/2，所以没有被DP选中的数之和（sum - dp[sum/2]）一定是比DP部分的和大的，那么两组和的最小差值就是sum - dp[sum/2] - dp[sum/2]，不需要加绝对值。

494.目标和、 474.一和零

目标和也是一组数分为两组，但将问题转化为恰好装满背包容积，有多少种装法，初始化有所不同。一和零也是01背包，但背包的容积有两个维度，做法一样。

1
2
3
4
5
6
7
// 目标和
dp[0]=1;  // 初始化：加和为0的取法只有一种，即什么数也不取
for (int i=0; i<nums.size(); i++){
    for (int j=x; j>=nums[i]; j--){
        dp[j] += dp[j-nums[i]];  // 递推公式
    }
}

完全背包

由01背包问题延伸而来，物品数量是无限的。

题目总结：

  • 纯完全背包，求解物品价值的总和最大是多少：

    与01背包问题的解法区别仅在于遍历顺序，需要将一维dp数组的遍历顺序改为 外层遍历物品并且内层正序遍历背包容量。也可以先遍历背包容量再遍历物品。链接

    1
    2
    3
    4
    5
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    内层正序遍历背包容量的话，每次递推公式里的 dp[ j - weight[i]] 就已经是被覆盖的值了，即本轮的值 dp[ i ] [ j - weight[i]] ，就可以做到多次选取物品。

    322.零钱兑换

  • 组合数，每个物品数量无限，求恰好凑成给定价值的组合数有多少：必须外层for循环遍历物品，内层for遍历背包。

    1
    2
    3
    4
    5
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
            dp[j] += dp[j - coins[i]];
        }
    }

    518.零钱兑换 II

  • 排列数，每个物品数量无限，求恰好凑成给定价值的排列数有多少：必须外层for遍历背包，内层for循环遍历物品。理解看这里

    1
    2
    3
    4
    5
    for (int j = 0; j <= amount; j++) { // 遍历背包容量
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
        }
    }

    377.组合总和 Ⅳ、139.单词拆分

打家劫舍系列

198.打家劫舍

简单的动规题，dp[i] 由 dp[i-1] 和 dp[i-2] 推出

213.打家劫舍II

考虑头尾两间房子，分两种情况，分别调用一次198.打家劫舍

337.打家劫舍 III

树形DP，结合了动态规划与二叉树的后序遍历。递归函数的返回值是偷与不偷的两个状态所得到的金钱构成的dp数组，必须要后序遍历，因为通过递归函数的返回值来计算父节点的dp数组。代码见

股票问题

121.买卖股票的最佳时机

122.买卖股票的最佳时机II

123.买卖股票的最佳时机III

188.买卖股票的最佳时机IV

309.最佳买卖股票时机含冷冻期

714.买卖股票的最佳时机含手续费

做法类似，将状态分为持有和不持有（限制买卖次数时多分几个状态），定义一个二维的dp数组，第一维表示天数，第二维表示状态，dp[i] [0] 表示第i天结束时持有股票剩余金额，dp[i] [1] 表示第i天结束时不持有股票剩余金额，递推公式由dp[i-1]推出。

子序列问题

不连续（子序列）：

300.最长递增子序列

1143.最长公共子序列

1035.不相交的线

连续（子数组）：

674.最长连续递增序列

718.最长重复子数组

53.最大子序和

编辑距离：

392.判断子序列

115.不同的子序列

583.两个字符串的删除操作

72.编辑距离

回文串：

647.回文子串

516.最长回文子序列

对于dp数组定义，一般是dp[i]表示以s[i]结尾的字符串或者在s[i]之前的。。。递推公式则要分类讨论，循环顺序根据递推公式决定。

单调栈

单调栈的应用场景：通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时我们就要想到可以用单调栈了。时间复杂度为O(n)。

单调栈的原理：当寻找右边第一个比自己大的元素时，栈中元素从栈底到栈顶应该是从大到小，遍历时遇到比栈顶元素小的元素，直接入栈；遇到比栈顶元素大的元素，就需要将栈顶元素出栈，再入栈（类似于汉诺塔，小盘子只能垒在大盘子上方），此时栈顶元素就已经找到了右边第一个比自己大的元素，即当前遍历的元素。

使用单调栈主要有三个判断条件，可以视情况合并为两个（取决于寻找的是右边严格大于自己的元素，还是大于等于）：

  • 当前遍历的元素T[i]小于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]等于栈顶元素T[st.top()]的情况
  • 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
stack<int> st;
vector<int> result(temperatures.size(), 0);  // 这里的初始值0取决于问题的需求，表示没有右边比自己大的元素时的结果
st.push(0);
for (int i=1; i<temperatures.size(); i++){
    if (temperatures[i] <= temperatures[st.top()]){  // 当前遍历的元素T[i]小于等于栈顶元素T[st.top()]的情况，直接入栈
        st.push(i);
    }
    else {  // 当前遍历的元素T[i]大于栈顶元素T[st.top()]的情况，取出栈顶元素再入栈
        while (!st.empty() && temperatures[i] > temperatures[st.top()]){
            result[st.top()] = i-st.top();
            st.pop();
        }
        st.push(i);
    }
}
return result;

当寻找右边比自己小的元素、左边比自己大/小的元素时，可以进行类比，单调栈的顺序会有不同。

739.每日温度、496.下一个更大元素 I、503.下一个更大元素II、42.接雨水、84.柱状图中最大的矩形