Detailed Explanation of Java Stream
Details Explanation of Java Stream
注意
wsl和本地上用IDEA运行java代码，最新修改的结果往往都无法被正常运行出来，我推测是缓存没有及时刷新之类的。有两个解决办法：
- 每次运行前按下快捷键：ctrl + shift + f9，达到rebuild project的目的
- 手动点击上边栏，选择build-rebuild project，选择build project没有作用
根据这个帖子，要彻底解决这个问题，恐怕要更新到2024.1以后的版本，我暂时不要更新自己的IDEA，因为当前的IDEA还能够正常使用，而我使用的是破解版的密钥，贸然更新可能会导致反而无法正常使用的情况出现。
不可变集合详解
创建不可变集合
不可变集合：不可以被修改的集合。其长度和内容都不可以被修改。
创建不可变集合的应用场景：
- 如果某个数据不能被修改，把它防御性地拷贝到不可变集合中是个很好的实践。
- 当集合对象被不可信的库调用时，不可变形式是安全的。
- 某些确定的规则。
- 电脑中的硬件信息。
简单理解：不想让别人修改集合中的内容，就可以给他提供一个不可变的集合。拿到不可变集合的人只能做查询操作，不能删除、修改、添加。
创建不可变集合的书写格式：
在List, Set, Map接口中，都存在静态的of方法，可以获取一个不可变的集合。
| 方法名称 | 说明 |
| :————————————————————: | :————————————————: |
| static <E> List<E> of(E...elements) | 创建一个具有指定元素的List集合对象 |
| static <E> Set<E> of(E...elements) | 创建一个具有指定元素的Set集合对象 |
| static <K, V> Map<K, V> of(E...elements) | 创建一个具有指定元素的Map集合对象 |
List of:
1 | package com.cyf.a01immutable; |
Set of:
1 | package com.cyf.a01immutable; |
Map.of:
1 | package com.cyf.a01immutable; |
Map.ofEntries:
1 | package com.cyf.a01immutable; |
上面的代码非常麻烦，可以简化。
Stream流
方法引用
初爽Stream流
Stream流的思想和获取Stream流
Day 31 Leetcode Basics of Greedy Algorithms, 455, 376, 53
链接
知识
理论基础
什么是贪心
贪心算法的本质是找到每个阶段的局部最优，从而去推导全局最优。
例如：
- 10张面值不同的钞票，如何取能取到总数最多的钱？每次取面额最大的钞票即可，这就是局部最优。取10次后拿到最多的钱，就是全局最优。这是贪心的思路。
- 背包最大承重是n。有一系列物品，其重量和价值各不相同，问这个背包能装的最大价值是多少？这需要用动态规划的思路来解决。
贪心的两个极端
贪心的题目要么太简短，要么太难。
贪心的套路
不像二叉树或者回溯算法的套路，贪心是没有套路的。部分较难的贪心题目，做过了才知道怎么做，否则完全想不到。非要说有套路，就是要想清楚每个阶段的局部最优，能否由局部最优推出全局最优。怎么由局部最优推出全局最优，也没有固定的思考方式。不需要做数学证明（数学证明的常用方法是数学归纳法和反证法），浪费时间。面试时，只要想到局部最优，可以推出全局最优，没有明显的反例，就已经可以试试，面试官不会要求严谨的数学证明。文字版讲解中有解决贪心算法的四个步骤，但实际做题时无法严格遵循四个步骤，实操性不强。
455.分发饼干
376.摆动序列
53.最大子序和
初次尝试
455.分发饼干
本题我的思路是，找出s数组的最大值，然后看g数组中有几个数小于等于s数组中的最大值，即为结果。我写了如下的代码，但只通过了23/25个测试样例：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
if (s.size() == 0) return 0;
sort(s.begin(), s.end());
int max = s[s.size() - 1];
int res = 0;
for (int i = 0; i < g.size(); i ++ )
if (g[i] <= max)
res ++ ;
if (s.size() <= res) return s.size();
return res;
}
};
直接看代码随想录的讲解吧。
376.摆动序列
53.最大子序和
实现
455.分发饼干
例子：
胃g: 1, 2, 7, 10
饼s: 1, 3, 5, 9
输出：3
策略：尽量用大饼干去喂胃口大的孩子，这样就可以充分利用饼干。
代码实现：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// 对两个数组进行排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int res = 0;
int index = s.size() - 1; // 饼干的index
// 优先用大饼干喂胃口大的小孩，因此倒序遍历
for (int i = g.size() - 1; i >= 0; i -- ) {
// 饼干成功投喂后，再向前遍历小孩数组，否则不能向前
if (index >= 0 && s[index] >= g[i]) {
res ++ ;
index -- ;
}
}
return res;
一定要外层循环遍历胃口，内层循环遍历饼干。如果外层循环遍历饼干，内层循环遍历胃口，拿上面的例子模拟就知道不可行。拿外层循环遍历饼干，内层循环遍历胃口，代码为：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// 对两个数组进行排序
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int res = 0;
int index = g.size() - 1;
for (int i = s.size() - 1; i >= 0; i -- ) {
if (index >= 0 && s[i] >= g[index]) {
res ++ ;
index -- ;
}
}
return res;
对于上面的例子，上述写法返回值为0。核心在于，要尝试去喂饱胃口大的孩子，而我们无法确保最大的饼干一定能喂饱胃口最大的孩子，如果最大的饼干无法喂饱胃口最大的孩子，那么上述写法的返回值恒为0。
另一种思路：尽量用小饼干去满足胃口小的孩子，这样可以充分利用小饼干。
376.摆动序列
53.最大子序和
心得与备忘录
455.分发饼干
- 一定要外层循环遍历胃口，内层循环遍历饼干。
- 内存循环用if判断而不用while循环，因为要一个小孩一个小孩地喂过去。
- 两种思路：先去满足大胃口的孩子，先去使用小饼干。两种思路遍历的顺序不同。
376.摆动序列
53.最大子序和
Dublin Restaurant Recommendations
简介
都柏林，素有美食荒漠、欧洲宁古塔之称。然而，经过本人和好友长期约饭探店的实地考察之后，发现都柏林的中餐馆门类齐全、品种多样，除去价格稍贵外相比于国内并无显著的短板和缺憾。因此，本人维护本帖用于记录都柏林吃喝之旅，并为读者提供一份尽可能详细的都柏林美食推荐清单。
本人向来赞同孔夫子“食不厌精，脍不厌细”的名言，因此，性价比是这份排行榜中相对次要的因素，食物的调味、口感、精细和新颖程度是更重要的。本帖中的五星代表着这个饭店的食物有独道之处，甚至超过了国内同种食物之最。四星代表着这个饭店的食物在味道或性价比方面至少有一个非常出众，而另一个也至少在平均水平之上。三星代表着值得一试，但并不惊艳。果腹则代表着仅供日常果腹之用，胜在量大管饱。心愿清单则是我早有耳闻，但还未成行的餐馆。本帖中推荐的餐馆会附带有谷歌地图的位置信息和一句简短的点评。本帖中也会提到一些国内的餐馆，主要分布在南昌、西安和合肥，都是本人曾经久居过的城市。本帖中评分点评随性，主观色彩浓重，愿博看官一笑。
五星
- 四川
- 川九香
四星
三星
果腹
国内
心愿清单
- 日料Omakase
- 西餐Shanahan’s on the Green
recipe
Day 30 Leetcode 332, 51, 37
链接
知识
51. N皇后
初始化一个vector<string>，其中的元素全是字符.（共有n行，每行是一个字符串，每个字符串由n个.构成）：
1 | vector<string> chessboard(n, string(n, '.')); |
实现
今天这三道题都非常难，那么这么难的题，为啥一天做三道？
因为一刷也不求能把这么难的问题解决，所以一刷的时候，就了解一下题目的要求，了解一下解题思路，不求能直接写出代码，先大概熟悉一下这些题，二刷的时候，随着对回溯算法的深入理解，再去解决如下三题。
332.重新安排行程
本题的思路不难，但选择的数据结构和初始化、遍历等操作非常复杂，是一道难题。
本题需要一个特殊的数据结构来存储一个机场映射多个机场，机场之间要靠字母序排列的这种复杂关系，选择的数据结构是unordered_map<string, map<string, int>> targets。其具体的含义为unordered_map<出发机场, map<到达机场, 航班次数>> targets。在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了。如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。有如下代码：1
2
3
4// unordered_map<出发机场, map<到达机场, 航班次数>> targets
// 使用map的原因是为了让其key有序（字典序）
// 第一个unordered_map是为了存储出发机场和到达机场间的映射关系，第二个map是为了对到达机场按照字典序排序，且记录到达机场在输入数据中出现的次数
unordered_map<string, map<string, int>> targets;
本题的树形结构如下所示，以输入：[["JFK", "KUL"], ["JFK", "NRT"], ["NRT", "JFK"]为例：
对上述树形结构的解释：始终从JFK出发，输入中JFK可以到KUL或者NRT，因此可以有这两个选择。输入中没有以KUL作为出发点的航班，因此飞向KUL的那一枝结束。飞向NRT的一枝，输入中以NRT为出发点的航班的终点是JFK，因此有行程：JFK->NRT->JFK。输入中以JFK为出发点的航班的终点可以是KUL或者NRT，因此分为两枝。JKF已经飞过NRT，因此剪枝；JKF飞KUL构成了行程：JFK->NRT->JFK->KUL，三趟航班，形成中有四个机场，说明找到了结果。
通过上述分析，我们可以得出代码的终止条件：n张机票，即有n个航班，则行程中有n + 1个机场（机场可重复）时，收集结果。原因是行程是由若干个向量组成的，每个向量都是一个航班，行程是单向的，不会形成环。因此，若有n个向量（即n个航班），那么就会有n + 1个节点（即单个向量的首尾），即n + 1个机场。有如下代码：1
2
3
4
5
6vector<string> res; // 存放结果，即由n个航班拼接成的行程，其中有n + 1个机场
// ticketNum为票数，即航班数
if (result.size() == ticketNum + 1) {
return true;
}
在写单层递归逻辑前，需要先对res数组和targets数组进行初始化，代码如下所示：1
2
3
4for (const vector<string>& vec : tickets) {
targets[vec[0]][vec[1]]++; // 记录映射关系
}
result.push_back("JFK"); // 起始机场
tickets数组是输入，其类型是vector<vector<string>>。由于输入不可更改，且其中的每个元素的类型都是vector<string>，因此用类型为const vector<string>的变量对其进行遍历，这里的引用就不加都可以，不会影响运行结果。vec[0]为出发机场，vec[1]为到达机场。targets中存储的是出发机场与到达机场的映射关系。对一个出发机场，若输入中存在其的到达机场，则在targets中记录这个映射关系，且map<string, int>中的string存储到达机场（vec[1]），int存储次数（有出发机场和其对应的到达机场，则该int存1）。这实现了对每一个航线（从某个出发机场到某个目的地机场）的航班次数进行计数。
根据树形结构，可以写出单层递归的逻辑：
1 | for (pair<const string, int>& target : targets[result[result.size() - 1]]) { |
这里特别需要注意的是：1
for (pair<const string, int>& target : targets[result[result.size() - 1]])
其含义为：result[result.size() - 1] 获取 result 向量的最后一个元素，即当前路径中最新的机场。然后，使用这个机场名称作为键，从 targets 映射中检索对应的内层 map，这个内层 map 包含所有从该机场出发的航班及其次数。for 循环遍历这个内层 map，即遍历从当前结果集中的最新机场可以直接到达的所有机场及对应的航班次数。一定要加上引用即 & target，因为后面有对 target.second 做减减操作，如果没有引用，单纯复制，这个结果就没记录下来，那最后的结果就不对了。加上引用之后，就必须在string前面加上const，因为map中的key是不可修改了，这就是语法规定了。
还需要注意本题的递归函数的返回值和参数：1
bool backtracking(int ticketNum, vector<string>& result)
注意函数返回值用的是bool！因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线。所以找到了这个叶子节点了直接返回。
拆分地写好了各部分的代码之后，整合起来就是本题的完整代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43class Solution {
public:
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketSum, vector<string>& res)
{
// 终止条件
if (ticketSum + 1 == res.size()) return true;
// 单层递归逻辑
// 以res中最新机场为出发点，遍历targets寻找可能的目的地
for (pair<const string, int>& target: targets[res[res.size() - 1]])
{
// target.second > 0说明目的地可用
if (target.second > 0)
{
// 处理节点
res.push_back(target.first);
target.second -- ;
// 递归
if (backtracking(ticketSum, res)) return true;
// 回溯
res.pop_back();
target.second ++ ;
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
// 初始化res
vector<string> res;
res.push_back("JFK");
// 初始化targets
for (auto vec: tickets)
targets[vec[0]][vec[1]] ++ ;
// 调用递归函数并返回结果
backtracking(tickets.size(), res);
return res;
}
};
使用auto来简化上述代码，避免需要手写复杂的变量类型：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
35class Solution {
public:
// 提取输入数据中的信息：构造出发机场和到达机场间的映射，到达机场按照字典序排序并记录到达机场出现的次数
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketSum, vector<string>& res)
{
// 终止条件
if (ticketSum + 1 == res.size()) return true;
// 单层递归逻辑
for (auto& target: targets[res[res.size() - 1]])
{
if (target.second > 0)
{
target.second -- ;
res.push_back(target.first);
if (backtracking(ticketSum, res)) return true;
target.second ++ ;
res.pop_back();
}
}
return false;
}
vector<string> findItinerary(vector<vector<string>>& tickets) {
// 初始化res
vector<string> res;
res.push_back("JFK");
// 初始化targets
for (auto ticket: tickets) targets[ticket[0]][ticket[1]] ++ ;
backtracking(tickets.size(), res);
return res;
}
};
51. N皇后
本题是回溯中较难的题目。题意：给一个n*n的棋盘，在其中放n个皇后，要求同一行、同一列、同意斜线上不能有两个皇后，将放置皇后的结果返回。难点：之前讲的组合问题、分割问题、子集问题和排列问题，都是一个一维的集合按照条件输出若个子集，本题则是一个二维的集合（数组）。
首先想如何暴力枚举，以4*4的棋盘为例，需要4个for循环，每一行每个位置尝试放皇后，根据规则判断能否放皇后。回溯算法的本质和暴力枚举没有区别，但回溯算法用递归的方式控制嵌套for循环的层数。
本题的树形结构如下所示，以3*3的棋盘为例：
第n层递归对应着尝试在第n行中放置皇后。3*3的N皇后问题是无解的，画其只是为了展现其树形结构。树的深度为棋盘的行数，树的宽度为棋盘的列数。接下来写本题的代码：
1 | // 每个棋盘是一个二维数组，放置若干棋盘，因此需要三维数组 |
总结：回溯法解决二维数组问题，第n层递归处理第n行，每层递归中遍历每一行中的每个元素。
在理解了本题的主题思路后，独立写出代码依然有难度，因为本题返回的变量类型是vector<vector<string>，chessboard的变量类型应该为vector<string>，对其进行初始化有一定难度。另外，isValid函数的实现我第一次写也有一定的困难，直接看文字版讲解。
我独立写出的本题的代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54class Solution {
public:
// 结果集
vector<vector<string>> res;
bool isValid(vector<string>& chessboard, int n, int row, int col)
{
// 同一列中不能有两个皇后
for (int i = 0; i < row; i ++ )
if (chessboard[i][col] == 'Q') return false;
// 主对角线不能有两个皇后
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i -- , j -- )
if (chessboard[i][j] == 'Q') return false;
// 副对角线不能有两个皇后
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i -- , j ++ )
if (chessboard[i][j] == 'Q') return false;
return true;
}
// 传入棋盘，棋盘大小，行数（即递归层数）
void backtracking(vector<string>& chessboard, int n, int row)
{
// 终止条件
if (row == n)
{
res.push_back(chessboard);
return;
}
// 单层递归逻辑
for (int i = 0; i < n; i ++ )
{
// 合法性判断
if (isValid(chessboard, n, row, i))
{
// 放皇后
chessboard[row][i] = 'Q';
// 递归
backtracking(chessboard, n, row + 1);
// 回溯
chessboard[row][i] = '.';
}
}
}
vector<vector<string>> solveNQueens(int n) {
vector<string> chessboard(n, string(n, '.'));
backtracking(chessboard, n, 0);
return res;
}
};
需要特别注意的是，在放皇后时，每次只在一行中的某个位置放一个皇后，且放完后会回溯，因此同一行中不会出现两个皇后，因此不需要在isValid函数中对同一行中出现两个皇后的情况进行判断。另外，放皇后的顺序是从行数小放到行数大，从列数小放到列数大。在不同行中，行数小的位置会被优先尝试放置皇后。在同一行的不同列中，列数小的位置会被优先尝试放置皇后。因此，isValid函数中对同一列判断，只需要判断从0-row列；对主对角线判断，只需要判断i从row-1到0，j从col-1到0；对副对角线判断，只需要判断i从row - 1到0，j从col + 1到n（由于优先放小的行，所以i < row, j > col的位置可能已经放置了皇后）。
37. 解数独
给一个99的棋盘，用1-9填满这个棋盘，规则为：同一行中不能有重复的数字，同一列中不能有重复的数字，九宫格中不能有重复的数字。本题求出一个填满的方案即可。本题是回溯章节的难题，和上一题N皇后类似。但用N皇后的思路做本题做不出来。*本题比N皇后多一个维度。N皇后用for循环遍历行，递归遍历列。本题不仅行要放满数字，列也要放满数字，整个棋盘都要放满数字。
本题解法被称为二维递归，即两个for循环，下面是一个递归函数。一个for循环来遍历行，一个for循环来遍历列，这样才能确定一个空格。递归用来确定空格中应该放的数字。本题的树形结构如下所示：
现在开始写本题的代码，本题的代码其实并不复杂。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// 确定递归函数的返回值和参数
// 返回值为bool类型，原因是本题求数独的一个解即可，一旦棋盘被填满，立即返回
// 若一题有多个结果，多个结果散落在树形结构里，需要将树形结构全都搜索一遍，然后将结果放入结果集中，因此返回值为void类型
bool backtracking(vector<vector<char>>& board) // board要引用，这样才会修改board
{
// 本题不需要写终止条件，棋盘被填满后会直接return true，若无法满足填充规则，则会return false
// 两个for循环，一个遍历行，另一个遍历列
for (int i = 0; i < board.size(); i ++ )
for (int j = 0; j < board[0].size(); j ++ )
{
// 处理节点
// 棋盘中的点表示空格
if (board[i][j] == '.')
{
for (char k = '1'; k <= '9'; k ++ )
{
// 检查在board的(i, j)处放置数字k是否合法
if (isValid(i, j, k, board))
{
board[i][j] = k;
// 进入下一层递归
bool res = backtracking(board);
// 找到一个结果就立即停止搜索，返回
if (res == true) return true;
// 回溯
board[i][j] = '.';
}
}
return false; // 在空格处将9个数字都尝试了，无法填入，则说明该棋盘没有结果，返回false
}
}
// 若没有走到return false，则return true（若棋盘一直被填充直到被填满，则不会走if (board[i][j] == '.')）
return true;
}
根据上面的核心代码，我自己实现了isValid函数，写出了本题的完整代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57class Solution {
public:
bool isValid(int i, int j, char k, vector<vector<char>>& board)
{
// 检查第i行能否放入k
for (int j = 0; j < board[0].size(); j ++ )
if (board[i][j] == k)
return false;
// 检查第j列能否放入k
for (int i = 0; i < board.size(); i ++ )
if (board[i][j] == k)
return false;
// 检查九宫格能否放入k
int starti = i / 3 * 3;
int startj = j / 3 * 3;
int endi = starti + 2;
int endj = startj + 2;
for (int i = starti; i <= endi; i ++ )
for (int j = startj; j <= endj; j ++ )
if (board[i][j] == k)
return false;
return true;
}
bool backtracking(vector<vector<char>>& board)
{
for (int i = 0; i < board.size(); i ++ )
for (int j = 0; j < board[0].size(); j ++ )
{
if (board[i][j] == '.')
{
// 处理节点
for (char k = '1'; k <= '9'; k ++ )
{
if (isValid(i, j, k, board))
{
board[i][j] = k;
// 递归
bool res = backtracking(board);
if (res == true) return true;
// 回溯
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};
心得与备忘录
332.重新安排行程
- 本题的解题思路其实不难，画出树形结构后，是一道经典的回溯问题。本题的难点在于选用怎样的数据结构来有效地存放和处理输入的数据。
- 因为本题是hard题，且由于使用了较为复杂的数据结构，因此我觉得在hard中都算是难题，显著比N皇后困难。因此，第一遍学习本题，了解本题的思路和核心代码即可，不要求能够将本题完整地写出来。
本题的实现部分对代码进行了细致的拆分讲解，大致可以分为以下几个要点：
- 用怎样的数据结构存储输入数据中出发机场和到达机场间的映射关系，且要求同一个出发机场的到达机场按照字典序排列，同时记录到达机场的使用次数
- 如何对结果集和上面的数据结构进行初始化
- 根据树形结构写出终止条件和单层搜索逻辑，并确定递归函数的返回值和传入的参数。本题递归函数的返回值是罕见的bool类型，而非void类型
明确上述三个问题，即可理解本题的思路和实现细节，进而顺畅地写出本题的代码。
在初始化targets时，范围遍历可以直接采用
auto类型的变量，避免需要手写复杂的变量类型。但在单层递归逻辑中遍历targets时，不能直接采用auto，因为for循环中涉及到了对遍历的值的修改操作，因此一定要使用引用，可以使用auto&。
51. N皇后
本题的新奇之处在于：之前用回溯法解决过组合、切割、子集、排列问题，处理的对象都是一维数组，N皇后问题处理的对象却是二维数组。
本题的原理实际上非常简单，理解本题的树形结构即可：
由上述树形结构可知，树的宽度是棋盘的列数，树的深度是棋盘的行数。据此，可以轻松地写出
backtracking函数的终止条件和单层递归逻辑。对棋盘合法性的判断其实是比较容易写错的。按照以下标准验证棋盘是否合法，两皇后：
不能同行
不能同列
不能同斜线 （主对角线和副对角线）
在
isValid函数中，不能同行的判断不需要写。因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，且后序还会回溯释放掉这个元素。因此只需要写不能同列、不能同主对角线、不能同副对角线的判断。这三个判断的书写依据如下图所示。
当我们尝试在
(row, col)处放置皇后时，只有绿色部分可能在之前被放置过皇后。原因是：递归到当前层，只有行数<row的格点上可能被放置过皇后。根据三条黄线，可以方便地写出三个判断。本题的时间复杂度O(n!)，空间复杂度O(n)。
- 时间复杂度：由于回溯法的本质依然是暴搜，因此，在棋盘的第一行，有n种放置皇后的方式；第二行最多有n - 1种，依次类推，得到时间复杂度为O(n!)。
- 空间复杂度即为树的深度，即为棋盘的行数，故空间复杂度为O(n)。
37. 解数独
- 和之前的递归题目不同，本题的递归是二维递归。一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性。
- 本题递归函数的函数返回值类型为
bool类型。原因是本题只需要找到一个解，就立即返回。如果需要搜索整棵二叉树，找到所有的解，然后将结果记录在结果集中，那么递归函数的返回值类型为void。 - 本题不需要写终止条件。因为在递归逻辑中，如果找到了满足条件的解，就会直接
return true。如果某个空格中无论填入哪个数字都无法满足条件，就会直接return false。 - 注意
return true和return false的位置。前者放在递归函数末尾，意思是若棋盘一直被填充直到被填满，则不会走if (board[i][j] == '.')，就return true。后者放在for (char k = '1'; k <= '9'; k ++ )的结束之处，意思是在空格处将9个数字都尝试了，无法填入，则说明该棋盘没有结果，return false。 - 时间复杂度：O(9^m) , m是’.’的数目。空间复杂度：$O(n^2)$，原因是递归的深度是n^2（原因是第一层
for循环代表树的宽度，后面两层for循环代表了树的深度。由于本题中数独的长宽固定为9，因此本题中的n = 9）。 - 回溯的题目到此结束，总体来说比较简单，有统一的模板，但每个题目又有一些需要注意的小细节。
Day 29 Leetcode 491, 46, 47
链接
知识
491.递增子序列
46.全排列
47.全排列 II
初次尝试
491.递增子序列
本题的关键：递增、至少两个元素、去重。但本题存在一个很大的问题，就是去重的时候不能对原数组进行排序，否则会打乱原数组的顺序，以以下测试样例为例：1
2Input: nums = [4,4,3,2,1]
Output: [[4,4]]
一旦顺序被打乱，实际输出和理论输出就会不同，会多出很多递增的子序列。
本题和90.子集II非常像，但又很不一样，很容易掉坑里。直接看卡尔的讲解吧。
46.全排列
本题是排列问题，不需要startIndex，但我写不出代码，直接看卡尔的讲解。经过卡尔的提示用used数组避免重复取元素后，我独立写出了以下的代码：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
34class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, vector<int>& used)
{
// 终止条件
if (path.size() == nums.size())
{
res.push_back(path);
return;
}
// 单层递归逻辑
for (int i = 0; i < nums.size(); i ++ )
{
if (used[i] == 1) continue;
// 处理节点
path.push_back(nums[i]);
used[i] = 1;
// 递归
backtracking(nums, used);
// 回溯
path.pop_back();
used[i] = 0;
}
}
vector<vector<int>> permute(vector<int>& nums) {
vector<int> used(nums.size(), 0);
backtracking(nums, used);
return res;
}
};
47.全排列 II
本题中的数组中会有重复元素，因此本题需要去重逻辑。本题相当于40.组合总和II去重逻辑和46.全排列的结合。我先尝试用set去重。我独立写出了以下的代码：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
36class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, vector<int>& used)
{
// 终止条件
if (path.size() == nums.size())
{
res.push_back(path);
return;
}
unordered_set<int> uset;
for (int i = 0; i < nums.size(); i ++ )
{
if (uset.find(nums[i]) != uset.end() || used[i] == 1) continue;
// 处理节点
uset.insert(nums[i]);
used[i] = 1;
path.push_back(nums[i]);
// 递归
backtracking(nums, used);
// 回溯
used[i] = 0;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> used(nums.size(), 0);
backtracking(nums, used);
return res;
}
};
再接着尝试写出used数组去重的代码。我独立写出了如下的代码：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
35class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, vector<int>& used)
{
// 终止条件
if (path.size() == nums.size())
{
res.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i ++ )
{
if (used[i] == 1 || i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
// 处理节点
used[i] = 1;
path.push_back(nums[i]);
// 递归
backtracking(nums, used);
// 回溯
used[i] = 0;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> used(nums.size(), 0);
sort(nums.begin(), nums.end());
backtracking(nums, used);
return res;
}
};
由于本题中nums[i]的数据范围在-10-10之间，所以可以不用set去重，而是用数组去重（将数据范围-10-10映射到数组下标范围0-20），这样效率更高，代码如下所示：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
38class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, vector<int>& used)
{
// 终止条件
if (path.size() == nums.size())
{
res.push_back(path);
return;
}
// 数组去重
int hash[21] = {0};
for (int i = 0; i < nums.size(); i ++ )
{
if (used[i] == 1 || hash[nums[i] + 10]) continue;
// 处理节点
hash[nums[i] + 10] = 1;
used[i] = 1;
path.push_back(nums[i]);
// 递归
backtracking(nums, used);
// 回溯
used[i] = 0;
path.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<int> used(nums.size(), 0);
backtracking(nums, used);
return res;
}
};
实现
491.递增子序列
列出递增子序列，子序列元素数量大于等于2。有以下测试样例：1
2Input: [4, 7, 6, 7]
Output: [4, 7, 7], [4, 7], [4, 6], [4, 6, 7], [6, 7], [7, 7]
要求不能有重复的子序列，因此需要去重。本题和90.子集II，只不过要求元素有顺序，且元素个数大于等于2。实际上，本题的细节和90有很大区别。本题的去重思路不可以沿用先排序再去重的做法，因为会改变原数组中元素的顺序，导致递增子序列的改变。例如对上述测试样例排序后，递增子序列会包括[4, 6, 7, 7]，实际上原本的输出不包含[4, 6, 7, 7]。
所有的回溯算法都是深搜，所有的深搜都可以说是递归。画本题的树形结构：
去重为树层去重。现在开始写代码：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
27vector<int> path; // 单个结果
vector<vector<int>> res; // 结果集
void backtracking(vector<int>& nums, int startIndex)
{
// 子集类问题可以不写终止条件，具体原因参见78/90
if (path.size() >= 2) res.push_back(path); // 子集中元素数量大于等于2
unordered_set<int> uset; // set去重
// 单层递归逻辑
for (int i = startIndex; i < nums.size(); i ++ )
{
// 剪枝条件1：所取元素小于子序列最后一个元素，此时要求子序列非空，否则path.back()会报错
// 剪枝条件2：用set做树层去重
if (!path.empty() && nums[i] < path.back() || uset.find(nums[i]) != uset.end()) continue;
// 处理节点
// 记录每一层取的数(for循环中除去递归部分外都是横向遍历的)，每一层不能重复取相同的数
uset.insert(nums[i]);
path.push_back(nums[i]);
// 递归
backtracking(nums, i + 1);
// 回溯
path.pop_back();
}
}
为什么没有对uset做回溯操作？
原因：上述代码中，每进入一层递归，都会重新定义一个uset。因此uset就是确保同一层中没有取到相同的元素，在进入下一层递归时，uset会被刷新。因此uset并不会对树枝去重，只会对树层去重。而used数组需要做回溯，因为used数组记录的是元素是否在path中被使用过，因此path中加减元素都需要对used数组进行修改。
本题的去重方式也可以应用于40.组合总和II和90.子集II。本题也可以用数组取代set进行去重，用数组的效率会更高些。
本题的完整代码如下所示：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
32class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int startIndex)
{
// 收集结果
if (path.size() >= 2) res.push_back(path);
unordered_set<int> uset;
// 单层递归逻辑
for (int i = startIndex; i < nums.size(); i ++ )
{
// 剪枝条件1：所取元素小于子序列最后一个元素，此时要求子序列非空，否则path.back()会报错
// 剪枝条件2：用set做树层去重
// cpp中&&的优先级高于||，因此是先与后或，不需要给剪枝条件1加括号
if (!path.empty() && nums[i] < path.back() || uset.find(nums[i]) != uset.end()) continue;
// 处理节点
uset.insert(nums[i]);
path.push_back(nums[i]);
// 递归
backtracking(nums, i + 1);
// 回溯
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return res;
}
};
由于本题nums[i]的数据范围很小，因此可以用数组做去重，运行效率也更高。只需要将set替换为普通数组，然后做一个偏移（数值-100-100映射到数组下标0-200上）即可。代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int startIndex)
{
if (path.size() > 1) res.push_back(path);
int cnt[201] = {0};
for (int i = startIndex; i < nums.size(); i ++ )
{
if (!path.empty() && nums[i] < path.back() || cnt[nums[i] + 100] == 1) continue;
cnt[nums[i] + 100] = 1;
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
}
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return res;
}
};
46.全排列
题目中明确说了给定的集合中没有重复元素，因此不用去重。
排列相对于组合的区别：[2, 1], [1, 2]是同一个组合，但是两个排列。排列是强调元素顺序的，组合不强调元素顺序。接下来画本题的树形结构。
排列问题中也需要用到used数组，用于标记哪些元素被使用过，因为在排列问题中同一个元素不能重复使用。组合问题中是用startIndex来避免取同一个元素和避免产生相同组合的情况。树的深度由nums的长度来控制。
used数组用来标记哪些元素被取过，取过的元素不能重复取，但所有没取过的元素都可以重复取，而不需要像组合问题那样用startIndex来控制只能取当前元素的下一个元素。具体的代码如下所示：
1 | vector<int> path; // 放单个结果 |
47.全排列 II
上一题给定的集合中没有重复元素，本题给定的集合中有重复元素。以[1, 1, 2]为例，如果依然用上一题的办法求解本题，结果集中会出现两个[1, 1, 2]，因此本题需要做去重。如果对去重的思路不够了解，可以看40.组合总和II。回溯的所有题目中，去重的逻辑都是相同的。本题等于排列+去重。但排列问题中的去重会有些与之前不同的地方。
画出本题的树形结构：
用used数组做树层去重前，记得对nums数组进行排序。本题中的used数组有两个作用：
- 避免同一个元素被重复使用
- 做树层去重
接下来写具体的代码：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
30vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, vector<int>& used)
{
// 终止条件
if (path.size() == nums.size())
{
res.push_back(path);
return;
}
// 单层递归逻辑
for (int i = 0; i < nums.size(); i ++ )
{
// 树层去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
// 同一个元素不能被重复取，因此取过的数直接跳过
if (used[i] == 1) continue;
// 处理节点
used[i] = 1;
path.push_back(nums[i]);
// 递归
backtracking(nums, used);
// 回溯
used[i] = 0;
path.pop_back();
}
}
细节：1
2// 树层去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
可以通过
1 | // 树枝去重 |
也可以通过。这意味着树层去重和树枝去重都可以解决本题。但树层去重的效率更高，树层去重会剪掉更多分支，而树枝去重要一直到最后一个树枝才会列出所有的结果。因此还是推荐树层去重的写法。以[1, 1, 1]为例，画出树层去重和树枝去重的树形结构：
很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。
时间复杂度和空间复杂度分析：
- 时间复杂度: 最差情况所有元素都是唯一的，时间复杂度为$O(n!\times n)$。 对于n个元素一共有n!中排列方案。而对于每一个答案，我们需要$O(n)$去复制最终放到
res数组。 - 空间复杂度: $O(n)$。空间复杂度即为回溯树的深度，其取决于
nums数组中有多少个元素。
心得与备忘录
491.递增子序列
关键点：set去重->剪枝->数组去重取代set去重
本题和90.子集II乍一看非常相似，但细节上有很大不同，解决本题时不能有惯性思维。
之前去重的方法都是利用
used数组，这意味着需要对nums数组进行排序。在本题中，如果对nums数组进行排序，就会打乱原数组中元素的顺序，导致递增子序列发生改变。因此，本题不能用used数组去重，而需要用set去重。因为用set去重不需要对原数组排序。本题有两个剪枝条件：
剪枝条件1：若所取元素小于子序列最后一个元素，则需要剪枝。此时要求子序列非空，否则
path.back()会报错。剪枝条件1的原因是本题要求子序列是递增的。剪枝条件2：用set做树层去重
两个剪枝条件用||相连。
为什么不需要对
set进行回溯？每进入一层递归，都会重新定义一个
set。因此set就是确保同一层中没有取到相同的元素。在进入下一层递归时，set会被刷新（重新定义）。因此set并不会对树枝去重，只会对树层去重。而used数组需要做回溯，因为used数组记录的是元素是否在path中被使用过，因此path中加减元素都需要对used数组进行相应的修改。本题的去重方法也可以应用于40.组合总和II和90.子集II。
由于本题
nums[i]的数据范围很小，因此可以用数组做去重，运行效率也更高。只需要将set替换为普通数组，然后做一个偏移（数值-100-100映射到数组下标0-200上）即可。本题的时间和空间复杂度分别为$O(n\times2^n)$和$O(n)$。同90和78。
46.全排列
- 排列问题和组合问题的两大区别：
- 每层都是从0开始搜索而不是
startIndex - 需要used数组记录
path里都放了哪些元素了
- 每层都是从0开始搜索而不是
- 不需要
startIndex的原因：[1, 2]和[2, 1]是同一个组合，但却是不同的排列，因此排列问题不能像组合问题那样从当前元素的下一个元素开始取，而是要取nums数组中所有当前没有取过的元素。 - 需要
used数组的原因：used数组记录了此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。 - 终止条件为
path.size() == nums.size()，nums数组的大小限制了树的深度。 - 本题的时间复杂度为$O(n!)$，空间复杂度为$O(n)$。时间复杂度的原因是有$n$个元素的
nums数组共有$n!$种排列。空间复杂度的原因是递归的深度（即树的深度）为$n$。
47.全排列 II
- 本题相当于40.组合总和II（树层去重）和46.全排列的结合。
- 本题的去重有三种写法：
set去重、数组去重、used数组去重。三种写法我都在初次尝试中给出了。 - 用
used数组去重前，一定要记得对nums数组进行排序。另外两种去重写法则不需要对nums数组进行排序。 - 由于本题是在叶子节点处收集结果，因此需要终止条件。
- 本题的时间复杂度为$O(n!\times n)$，空间复杂度为$O(n)$。具体原因参见实现部分。
- 本题用树层去重和树枝去重都可以，具体原因参见实现部分。但树层去重的效率远高于树枝去重，因此采用一贯以来的
used数组树层去重写法即可，不要纠结树枝去重的原理和合理性。
LeetCode problems prepared for a TikTok interview
34. 在排序数组中查找元素的第一个和最后一个位置
本题是整数二分的加强版。本题的要点为：
写两个函数，分别寻找target的左边界和右边界。本题的区间定义为左闭右闭。
寻找左边界，说明target在[left, mid]之间，因此在[left, mid]中更新左边界。寻找右边界，说明target在[mid, right]之间，因此在[mid, right]中更新右边界。
寻找左边界，就要在
nums[mid] == target的时候更新right，然后将right赋给左边界。寻找右边界，就要在nums[mid] == target的时候更新left，然后将left赋给右边界。实际上的左右边界是
mid，而非right和left，因此在主函数中需要将左边界+1，恢复为mid；将右边界-1，也恢复为mid。也可以直接让左右边界是mid，这样就不需要加1减1，参见我的第二种写法。target的三种情况：
- target在数组范围的右边或者左边
- target 在数组范围中，且数组中存在target
- target 在数组范围中，且数组中不存在target
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57// 左闭右闭写法
class Solution {
public:
// 寻找左边界
// 说明target在[left, mid]之间
int findLeftBorder(vector<int>& nums, int target)
{
int leftBorder = -2;
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
// 在[left, mid]中更新左边界
if (nums[mid] >= target)
{
right = mid - 1;
leftBorder = right;
}
else left = mid + 1;
}
return leftBorder;
}
// 寻找右边界
// 说明target在[mid, right]之间
int findRightBorder(vector<int>& nums, int target)
{
int rightBorder = -2;
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > target) right = mid - 1;
// 在[mid, right]中更新右边界
else
{
left = mid + 1;
rightBorder = left;
}
}
return rightBorder;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = findLeftBorder(nums, target);
int rightBorder = findRightBorder(nums, target);
// target在数组范围的右边或者左边
if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
// target 在数组范围中，且数组中存在target
if (rightBorder - leftBorder > 1) return {leftBorder + 1, rightBorder - 1};
// target 在数组范围中，且数组中不存在target
return {-1, -1};
}
};
我写出了以下的变式代码。在这个代码里，通过mid来更新左右边界。这样若找到了左右边界，则直接返回左右边界即可，不需要做加1减1的操作。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57// 左闭右闭写法
class Solution {
public:
// 寻找左边界
// 说明target在[left, mid]之间
int findLeftBorder(vector<int>& nums, int target)
{
int leftBorder = -2;
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
// 在[left, mid]中更新左边界
if (nums[mid] >= target)
{
right = mid - 1;
leftBorder = mid;
}
else left = mid + 1;
}
return leftBorder;
}
// 寻找右边界
// 说明target在[mid, right]之间
int findRightBorder(vector<int>& nums, int target)
{
int rightBorder = -2;
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > target) right = mid - 1;
// 在[mid, right]中更新右边界
else
{
left = mid + 1;
rightBorder = mid;
}
}
return rightBorder;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftBorder = findLeftBorder(nums, target);
int rightBorder = findRightBorder(nums, target);
// target在数组范围的右边或者左边
if (leftBorder == -2 || rightBorder == -2) return {-1, -1};
// target 在数组范围中，且数组中存在target
if (rightBorder - leftBorder >= 0) return {leftBorder, rightBorder};
// target 在数组范围中，且数组中不存在target
return {-1, -1};
}
};
278.第一个坏版本
我独立写出了以下代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17// The API isBadVersion is defined for you.
// bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
int left = 1, right = n;
while (left < right)
{
int mid = left + (right - left) / 2;
if (isBadVersion(mid) == 0) left = mid + 1;
else right = mid;
}
return left;
}
};
在本题中，尽管是左闭右闭的写法，但循环的条件应该为left < right，因为当left = right时，实际上就锁定了第一个坏版本，循环就应当结束。这种题目当出现超时，要着重检查是不是循环的条件不对。
和本题同样的题目：输入一个数组，比如[0, 0, 0, 1, 1, 1, 1]，找到第一个为1的数的下标，代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int firstBadVersion(vector<int> arr)
{
int left = 0, right = arr.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == 1) right = mid;
else left = mid + 1;
}
return left;
}
int main()
{
vector<int> arr = {0, 0, 0, 1, 1, 1, 1, 1};
cout << firstBadVersion(arr) << endl;
return 0;
}
27. 移除元素
本题直接采用（快慢）双指针解法即可。一遍过，但需要注意不要在for循环中重复定义指针j。本题的暴力做法甚至比双指针做法更复杂，也更容易写错。相向双指针做法暂时不用管。
977.有序数组的平方
暴力解法非常简单，也能通过测试。我先在纸上模拟了双指针的过程，然后独立写出了如下的双指针代码，时间和空间复杂度都是$O(n)$。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26// 双指针经典题
class Solution {
public:
vector<int> sortedSquares(vector<int>& nums) {
int size = nums.size() - 1;
vector<int> res(nums.size(), 0);
for (int i = 0, j = size; i <= j; )
{
if (nums[i] * nums[i] <= nums[j] * nums[j])
{
res[size] = nums[j] * nums[j];
j -- ;
size -- ;
}
else
{
res[size] = nums[i] * nums[i];
i ++ ;
size -- ;
}
}
return res;
}
};
不要追求把代码写得过度简洁，而导致可能的问题，宁可把代码写长一些，也要让代码清楚地表达算法思想。
209.长度最小的子数组
一时想不起来具体怎么写了，只记得遍历整个数组的同时，有数划入窗口，该数被累加到和中，有数划出窗口，则该数被从和中减去。看了我自己的笔记后，我独立写出了以下的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int len = INT_MAX;
int s = 0; // 滑动窗口的和
int i = 0; // 起始位置
// j为终止位置
for (int j = 0; j < nums.size(); j ++ )
{
s += nums[j]; // 终止位置划入
while (s >= target)
{
int sub = j - i + 1;
if (sub < len) len = sub;
s -= nums[i]; // 起始位置从和中滑出
i ++ ; // 起始位置从滑动窗口中滑出
}
}
if (len == INT_MAX) return 0;
else return len;
}
};
需要注意：
i为起始位置，j为终止位置
循环中，终止位置先划入。若和大于等于目标值，则先更新最小长度，再将起始位置划出。
起始位置的值需要先从和中滑出，起始位置再从滑动窗口中滑出。顺序不可颠倒。
for循环中是while循环，而非if判断
数组中的每个元素至多被滑入一次再滑出一次，因此时间复杂度是$O(2n)$，即$O(n)$。
59.螺旋矩阵II
我记得本题是个模拟题。但实在记不得怎么做了，看以前的笔记。复习完后，我写出了本题的代码：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
28class Solution {
public:
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> res(n, vector<int>(n, 0));
int i, j;
int startx = 0, starty = 0;
int offset = 1, cnt = 1;
int loop = n / 2;
while (loop -- )
{
for (j = starty; j < n - offset; j ++ )
res[startx][j] = cnt ++ ;
for (i = startx; i < n - offset; i ++ )
res[i][j] = cnt ++ ;
for (j = n - offset; j > starty; j -- )
res[i][j] = cnt ++ ;
for (i = n - offset; i > startx; i -- )
res[i][j] = cnt ++ ;
offset ++ ;
startx ++ ;
starty ++ ;
}
if (n % 2) res[n / 2][n / 2] = cnt;
return res;
}
};
需要注意：
画图理解（记住本图，就可以写出这道题的代码）：
顺时针转圈，转多少圈可以填满整个二维数组？从(0, 0)的位置开始转圈，终止的位置为中心(n/2, n/2)。每转一圈横纵坐标均加1，因此一共转了n/2圈。
切记遵守循环不变量原则，所有边都是左闭右开的。所以是
j < n - offset，且offset的初始值为1，因为右边界是开的。startx,starty,offset每转一圈都要加1。定义二维数组的方式是将一位数组复制行数遍。
若n为奇数，则最后记得向二维数组的中心填入最后一个数。
189.旋转数组
首先我写出了可以正常运行但会超时的代码：1
2
3
4
5
6
7
8
9
10class Solution {
public:
void rotate(vector<int>& nums, int k) {
while (k -- )
{
reverse(nums.begin(), nums.end());
reverse(nums.begin() + 1, nums.end());
}
}
};
不超时的代码我写不出来，看卡尔的讲解。
本题的代码如下所示：1
2
3
4
5
6
7
8
9class Solution {
public:
void rotate(vector<int>& nums, int k) {
k = k % nums.size();
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
本题其实原理不难，类似于旋转字符串的题目，总结如下：
- 首先反转整个数组，这样在不考虑顺序的情况下，就将两段数字放在了正确的位置上。
- 然后反转前k个数，将前k个数的顺序调整正确。
- 最后反转剩下的数，将剩下的数的顺序调整正确。
- 需要注意的是，若
k > nums.size()，则右移k % nums.size()即可，因为右移nums.size()次相当于没有改变原数组。 - 不要对nums.end()进行加减操作，nums.end()不指向一个特定的元素（不要下意识地以为其指向最后一个元素后面的紧邻的位置），对其进行加减操作会导致未定义的随机行为。对nums.begin()进行操作就没有这个问题。因此反转的第三步不要写成
reverse(nums.end() - k - 1, nums.end())。
153.寻找旋转数组中的最小值
应该是先要将其恢复为有序的数组，然后返回有序数组的第一个元素即可。本题应该结合了二分法和旋转数组。我直接看题解吧。
虽然但是，本题用暴力做法也可以通过：1
2
3
4
5
6
7class Solution {
public:
int findMin(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[0];
}
};
上述算法的时间复杂度是O(nlogn)。用二分法应该可以将时间复杂度优化为O(logn)。
本题的二分做法如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22// 左闭右闭写法
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
// 循环的终止条件：left = right。此时必然已经找到了数组中的最小值
while (left < right)
{
int mid = left + (right - left) / 2;
// 中间数字大于右边数字，比如[3,4,5,1,2]，则左侧是有序上升的，最小值在右侧
if (nums[mid] > nums[right]) left = mid + 1;
// 中间数字小于右边数字，比如[6,7,1,2,3,4,5]，则右侧是有序上升的，最小值在左侧
// 以[6, 7, 1, 2, 3, 4]为例，mid = 2, right = 2，即恰好在[left, mid]中取到最小值1
// 若right = mid - 1，则[left, right]会错过最小值
else if (nums[mid] < nums[right]) right = mid;
// 中间数字等于右边数字，则说明数组中只有一个元素，返回该元素即可
// 也可以直接写作else right = mid;
}
return nums[left];
}
};
本题延续了二分法的思路和代码形式，但细节和二分法略有不同，需要注意复习。
本题的思路：
本题是左闭右闭写法，区间为
[left, right]数组中的最小值要么在数组的右侧，要么在数组的左侧
- 数组的最小值在数组右侧的情况：[3, 4, 5, 1, 2]。数组的最小值在数组左侧的情况：[6, 7, 1, 2, 3, 4, 5]
- 若数组的最小值在数组的右侧，由于
nums[mid] > nums[right]，因此nums[mid]必然不可能是数组的最小值，因此left = mid + 1 - 对于剩下的情况，即
nums[mid] <= nums[right]，数组的最小值在数组的左侧。由于可能存在nums[mid] = nums[right]的情况，因此nums[mid]可能是最小值，因此有right = mid - 记住始终是
nums[mid]和nums[right]比较。始终是中间和右边比！
本题的另一种思路（更推荐这种，因为这种思路可以推广到33）：
nums[mid]和nums[right]的关系可以分为大于，等于，小于三种情况nums[mid] == nums[right]时，中间的数字等于最右边的数字，说明数组中只有一个元素，此时返回nums[left]即可，这种情况不需要考虑nums[mid] > nums[right]时，例如[3, 4, 5, 1, 2]。数组的最小值在数组的右侧，nums[mid]必定不为最小值，因此有left = mid + 1nums[mid] < nums[right]时，数组的最小值在数组的左侧。例如[6, 7, 1, 2, 3, 4, 5]，也有可能是[6, 7, 1, 2, 3, 4]，此时mid = 2, right = 2，即恰好在[left, mid]中取到最小值1。若right = mid - 1，则[left, right]会错过最小值，因此right = mid
154.寻找旋转数组中的最小值II
本题的思路：
- 延续上题的思路，
nums[mid]和nums[right]的关系可以分为大于，等于，小于三种情况 nums[mid] > nums[right]和nums[mid] < nums[right]的情况同上- 由于数组中可以有重复的元素，因此需要考虑
nums[mid] == mums[right]的情况，例如[2,3,1,1,1]或者[4,1,2,3,3,3,3]。此时，重复值nums[right]可能是最小值，也可能最小值在重复值的左侧，因此right左移一位：right -= 1
本题的代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
// [5, 6, 7, 1, 2]
if (nums[mid] > nums[right]) left = mid + 1;
// [7, 1, 2, 3, 4]
else if (nums[mid] < nums[right]) right = mid;
else right -= 1;
}
return nums[left];
}
};
33.搜索旋转排序数组
我对本题的初步思路：先找到最小的那个点，然后分别对两段单调递增的区间用二分法进行搜索。根据这个原理，我独立写出了以下的代码：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
37class Solution {
public:
// 二分查找有序数组中的数
// 左闭右闭写法
int searchTarget(vector<int>& nums, int left, int right, int target)
{
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > target) right = mid - 1;
else if (nums[mid] < target) left = mid + 1;
else return mid;
}
return -1;
}
int search(vector<int>& nums, int target) {
// 先找到最小的数字, 下标为left
int left = 0, right = nums.size() - 1;
while (left < right)
{
int mid = left + (right - left) / 2;
// nums[mid] nums[right], [4, 5, 6, 7, 0, 1, 2]
if (nums[mid] > nums[right]) left = mid + 1;
else right = mid;
}
int leftIndex = searchTarget(nums, 0, left - 1, target);
int rightIndex = searchTarget(nums, left, nums.size() - 1, target);
if (leftIndex == -1 && rightIndex == -1) return -1;
else if (leftIndex == -1) return rightIndex;
else if (rightIndex == -1) return leftIndex;
return -1;
}
};
时间复杂度也是$O(logn)$。
更简单的写法如下：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// 左闭右闭写法
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
// 本质是查找target，因此是小于等于。若是查找最小值，则是小于
while (left <= right)
{
int mid = left + (right - left) / 2;
// 第一种情况，直接找到
if (nums[mid] == target) return mid;
// 由于第一种情况已经讨论过nums[mid] == target，因此第二三种情况不用再讨论
// 第二种情况，数组最小值在右侧, [left, mid]为有序
if (nums[mid] > nums[right])
{
// target在[left, mid](有序)内
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
// target在无序区间内
else left = mid + 1;
}
// 第三种情况，数组最小值在左侧，[mid, right]为有序
else
{
// target在[mid, right]区间内
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
// target在无序区间内
else right = mid - 1;
}
}
return -1;
}
};
分三种情况讨论：
- 直接在mid处找到target
- 数组最小值在右侧, [left, mid]为有序
- target在[left, mid]有序区间内
- target在剩余的无序区间内
- 数组最小值在左侧，[mid, right]为有序
- target在[mid, right]有序区间内
- target在剩余的无序区间内
81.搜索旋转排序数组II
本题依然可以用老思路：找到最小值点，将区间划分为两个单调区间，然后分别在两个单调区间中进行搜索。本题实际上不可以这样做，因为本题中数组的元素可以重复，可能存在不止一个最小值点。
看了答案后，发现本题有两种写法，第一种：在循环内部跳过数组左侧和右侧的重复元素：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
33class Solution {
public:
bool search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
// 跳过数组左侧的重复元素
while (left < right && nums[left] == nums[left + 1]) left++;
// 跳过数组右侧的重复元素
while (left < right && nums[right] == nums[right - 1]) right--;
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
// 判断有序部分
if (nums[mid] >= nums[left]) { // 左侧有序
if (target >= nums[left] && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else { // 右侧有序
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return false;
}
};
第二种，在循环外部直接删去数组尾部与数组头部重复的元素：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
36class Solution {
public:
bool search(vector<int>& nums, int target) {
// 移除重复的末尾元素以减少干扰
// 可以处理如下情况：[1, 0, 1, 1, 1], [1, 2, 2, 2, 2, 0, 1]
// nums.front() == nums.back()时，可能数组右边有序，也可能左边有序
// 也可写作nums[0] == nums[nums.size() - 1]
while (nums.size() > 1 && nums.front() == nums.back()) nums.pop_back();
int left = 0, right = nums.size() - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (nums[mid] == target) return true;
// [3, 4, 5, 1, 2]
if (nums[mid] > nums[right])
{
// 有序区间[left, mid]
if (target >= nums[left] && target < nums[mid]) right = mid - 1;
// 无序区间[mid, right]
else left = mid + 1;
}
else
{
// 有序区间[mid, right]
if (target > nums[mid] && target <= nums[right]) left = mid + 1;
// 无序区间[left, mid]
else right = mid - 1;
}
}
return false;
}
};
注意：需要先移除重复的末尾元素以减少干扰，再给left和right赋值。
建议采用第二种写法，因为第二种写法相当于在33.搜索旋转排序数组的基础上仅仅添加了移除重复的末尾元素的代码。这道题相当与上一题区别在于这道题包含了重复元素，其实影响到的是，当左端点和右端点相等时，无法判断mid在左半边有序数组还是右半边有序数组，所以只需要一直pop直到左端点和右端点不相等就可以了。
442. 数组中重复的数据
448. 找到所有数组中消失的数字
只有当数字的范围和数组的大小相等，或者有一定偏移关系时，才可以用原地哈希。本题的数字范围1-n，本题的数组中有n个元素，数组下标的范围是0-n-1。这种原地哈希算法适用于和正整数有关，且数字范围和数组长度有关的题目里，映射之后能利用映射关系（下标和值一一对应）来找到解。
对于本题，本质就是将原数组的下标为nums[i] - 1处放上nums[i]，最终希望达到的效果是nums[nums[i] - 1] == nums[i]。本题的代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> res;
// 将nums[i]放到下标为nums[i] - 1的位置上
// 由于原来下标为nums[i] - 1的位置上可能有数，因此需要将该数暂存到nums[i]上
// 之后可以通过while循环将再将该数放到合适的位置上去
// 可以举例子来模拟，即可以弄清楚这个过程
for (int i = 0; i < nums.size(); i ++ )
{
while (nums[nums[i] - 1] != nums[i])
{
int idx = nums[i] - 1;
int tmp = nums[idx];
nums[idx] = nums[i];
nums[i] = tmp;
}
}
for (int i = 0; i < nums.size(); i ++ )
{
// 若nums[i]上的数字不为i + 1，则说明该数字缺失，将其插入结果集中
if (nums[i] != i + 1)
res.push_back(i + 1);
}
return res;
}
};
本题的精简注释版本如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
vector<int> findDisappearedNumbers(vector<int>& nums) {
vector<int> res;
int n = nums.size();
for (int i = 0; i < n; i ++ )
{
// 确保将nums[i]放到下标为nums[i] - 1的位置上
while (nums[nums[i] - 1] != nums[i])
{
int idx = nums[i] - 1; // 即将占用的元素的下标
int tmp = nums[idx]; // 暂存下标为idx处的元素，因为其即将被nums[i]占用
nums[idx] = nums[i]; // 将nums[i]放到下标为nums[i] - 1的位置上
nums[i] = tmp; // 将原来数组中下标为nums[i] - 1的数暂存到位置i
}
}
for (int i = 0; i < n; i ++ )
if (nums[i] != i + 1) res.push_back(i + 1);
return res;
}
};
while循环中的顺序：先写：1
2int idx = nums[i] - 1;
nums[idx] = nums[i];
确保nums[i]被放在了下标为nums[i] - 1处。
再将原本下标为idx处的元素缓存下来，暂存到下标i处：1
2int tmp = nums[idx];
nums[i] = tmp;
由此构成完整的代码：1
2
3
4int idx = nums[i] - 1;
int tmp = nums[idx];
nums[idx] = nums[i];
nums[i] = tmp;
442. 数组中重复的数据
本题依然可以用448的原地哈希法完成，唯一地不同在于，448是将i + 1插入res数组中，本题是将nums[i]插入res数组中，举一个实际的例子即可理解为什么是将nums[i]插入结果集中。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> res;
int n = nums.size();
for (int i = 0; i < n; i ++ )
{
while (nums[nums[i] - 1] != nums[i])
{
int idx = nums[i] - 1;
int tmp = nums[idx];
nums[idx] = nums[i];
nums[i] = tmp;
}
}
for (int i = 0; i < n; i ++ )
{
if (nums[i] != i + 1) res.push_back(nums[i]);
}
return res;
}
};
对原地哈希可进行总结：
情景：数组的长度为
n，数组中元素的范围为[1, n]若是找缺失的数字，则插入结果集的是索引下标+1；若是找出现了两遍的数字，则插入结果集的是元素的值
nums[i]使用代码块：
1
2
3
4
5
6
7
8
9
10for (int i = 0; i < n; i ++ )
{
while (nums[nums[i] - 1] != nums[i])
{
int idx = nums[i] - 1;
int tmp = nums[idx];
nums[idx] = nums[i];
nums[i] = tmp;
}
}对数组进行原地哈希后，数组中出现过的数字
nums[i]会被重新放置在下标为nums[i] - 1的位置上。范围为[1, n]但数组中没出现过的数字nums[j]，其本来应该放置在下标为nums[j] - 1处，但由于没有出现过，现在下标为nums[j] - 1处放置了原数组中的重复元素。这是因为循环的条件nums[nums[i] - 1] != nums[i]，当未填满的位置填入了重复元素后，while循环也会终止。例如，对[4, 3, 2, 2, 3, 1]进行原地哈希，结果为[1, 2, 3, 4, 3, 2]，原数组中出现过的1, 2, 3, 4被放置在下标为0, 1, 2, 3的位置上，原数组中没有出现过5, 6，因此下标为4，5处放置了原数组中重复的元素2, 3。原地哈希法的时间复杂度都为O(n)，空间复杂度都为O(1)
为什么是 O(n) 时间复杂度？
每个元素在整个过程中最多被处理两次（一次是放置在正确位置，一次是在最终遍历中检查），因此总体时间复杂度是 O(2n)==O(n)。
41. 缺失的第一个正数
本题的思路和448、442相同，只不过while循环多了限制条件，同时返回值时需要考虑一种特殊情况。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
30class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n; i ++ )
{
// 为避免nums[i] - 1超出索引的范围，需要对nums[i]的大小进行限制
// 0 <= nums[i] - 1 <= n - 1，因此1 <= nums[i] <= n
// 不需要对此范围之外的数进行操作，也无法用原地哈希法操作它们，因为它们会超出索引范围
while (nums[i] >= 1 && nums[i] <= n && nums[nums[i] - 1] != nums[i])
{
// 这四行代码可以简写为swap(nums[nums[i] - 1], nums[i]);
int idx = nums[i] - 1;
int tmp = nums[idx];
nums[idx] = nums[i];
nums[i] = tmp;
}
}
for (int i = 0; i < n; i ++ )
{
if (nums[i] != i + 1)
return i + 1;
}
// 特殊情况, nums = [1], 上面的循环不会返回结果，此时返回n + 1即可
return n + 1;
}
};
本题中，数的个数为n个，但数的范围不在[1, n]中。需要返回缺失的第一个正整数。虽然乍一看不完全符合上题总结的原地哈希法的使用条件，但加上限制条件的原地哈希法依然可以被应用于解决本题。
203.移除链表元素
本题不能这样写：1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
for (ListNode* cur = dummyHead; cur != NULL; cur = cur->next)
{
if (cur->next != NULL && cur->next->val == val)
cur->next = cur->next->next;
}
return dummyHead->next;
}
};
这样写会导致删除节点后，cur 指针向后移动到了 cur->next->next，从而可能跳过了紧接着的需要删除的节点。比如：1
1 -> 2 -> 2 -> 3, target = 2
上述写法会导致第三个节点2不能被删除。
本题应当用while循环写，对一个节点，如果是目标节点，则将其删除，否则，向后移动一个节点，不能同时既删除节点又后移一位。本题正确的代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != NULL)
{
// 如果既删又后移，则会漏掉节点
if (cur->next->val == val) cur->next = cur->next->next; // 要么删
else cur = cur->next; // 要么后移
}
return dummyHead->next;
}
};
本题的完整主函数：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int x): val(x), next(NULL) {}
};
ListNode* remove(ListNode* head, int val)
{
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != NULL)
{
if (cur->next->val == val) cur->next = cur->next->next;
else cur = cur->next;
}
return dummyHead->next;
}
int main()
{
// head = [1,2,6,3]
ListNode* node1 = new ListNode(1);
ListNode* node2 = new ListNode(2);
ListNode* node3 = new ListNode(6);
ListNode* node4 = new ListNode(3);
node1->next = node2;
node2->next = node3;
node3->next = node4;
ListNode* head = remove(node1, 3);
for (ListNode* cur = head; cur != NULL; cur = cur->next) cout << cur->val << ' ';
cout << endl;
return 0;
}
构造链表时，也可以采用函数写法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
using namespace std;
struct ListNode
{
int val;
ListNode* next;
ListNode(int x): val(x), next(NULL) {}
};
ListNode* appendNode(ListNode*& head, int val)
{
// 头为空，则将新节点作为头节点
if (head == NULL) head = new ListNode(val);
// 头不为空，则遍历到链表最后一个节点，将新节点添加到最后一个节点之后
else
{
ListNode* cur = head;
while (cur->next != NULL) cur = cur->next;
cur->next = new ListNode(val);
}
return head;
}
ListNode* remove(ListNode* head, int val)
{
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != NULL)
{
if (cur->next->val == val) cur->next = cur->next->next;
else cur = cur->next;
}
return dummyHead->next;
}
int main()
{
// head = [1,2,6,3]
ListNode* node = NULL;
appendNode(node, 1);
appendNode(node, 2);
appendNode(node, 6);
appendNode(node, 3);
ListNode* head = remove(node, 3);
for (ListNode* cur = head; cur != NULL; cur = cur->next) cout << cur->val << ' ';
cout << endl;
return 0;
}
在定义链表时，特别要注意下面用来赋值的这句话：ListNode(int x): val(x), next(NULL) {}。
707.设计链表
本题的细节很多，需要特别注意。1
2
3
4
5
6
7
8
9
10
11
12
13
14// get函数的复杂写法
int get(int index) {
if (index < 0 || index > _size - 1) return -1;
LinkedList* cur = _dummyHead;
index ++ ;
while (cur != NULL)
{
cur = cur->next;
index -- ;
if (index == 0) break;
}
return cur->val;
}
本题的完整代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59class MyLinkedList {
public:
struct LinkedList
{
int val;
LinkedList* next;
LinkedList(int x): val(x), next(NULL) {}
};
MyLinkedList() {
_dummyHead = new LinkedList(0);
_size = 0;
}
int get(int index) {
if (index < 0 || index > _size - 1) return -1;
LinkedList* cur = _dummyHead->next;
while (index -- ) cur = cur->next;
return cur->val;
}
void addAtHead(int val) {
LinkedList* head = new LinkedList(val);
head->next = _dummyHead->next;
_dummyHead->next = head;
_size ++ ;
}
void addAtTail(int val) {
LinkedList* tail = new LinkedList(val);
LinkedList* cur = _dummyHead;
while (cur->next != NULL) cur = cur->next;
cur->next = tail;
_size ++ ;
}
void addAtIndex(int index, int val) {
if (index < 0 || index > _size) return;
LinkedList* newNode = new LinkedList(val);
LinkedList* cur = _dummyHead;
while (index -- ) cur = cur->next;
newNode->next = cur->next;
cur->next = newNode;
_size ++ ;
}
void deleteAtIndex(int index) {
if (index < 0 || index > _size - 1) return;
LinkedList* cur = _dummyHead;
while (index -- ) cur = cur->next;
cur->next = cur->next->next;
_size -- ;
}
private:
LinkedList* _dummyHead;
int _size;
};
注意事项：
带下划线的变量表示类中的变量，而非局部变量
记得在private中定义类中的变量
注意插入节点时先更新后面的边，再更新前面的边
别忘记_size ++ / _size —
注意对参数index进行判断
while (index -- ) cur = cur->next的意思是，首先判断index是否大于0，是，则index = index - 1，然后执行cur = cur->next
206.反转链表
我记得有递归写法，迭代写法，先尝试实现迭代写法，其本质是双指针。记住下面的图，即可写出本题的双指针法的代码：
注意：pre从NULL开始，cur在NULL结束。
一个经典的错误：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
while (cur->next)
{
ListNode* tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return cur;
}
};
这样写的结果是导致未将列表的最后一个节点（即反转后的头节点）的 next 指针正确设置。
本题的递归写法其实更加好写，但其空间复杂度为O(n)，高于双指针写法：1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
ListNode* reverseList(ListNode* head) {
// 终止条件
if (head == NULL || head->next == NULL) return head;
ListNode* last = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return last;
}
};
24. 两两交换链表中的节点
首先尝试用双指针做法解决本题。直接看答案，记住本题的方法。其实不需要双指针，本题是一道单纯的模拟题，但要搞清楚循环终止条件。看过博客后，我写出了以下的代码：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
27class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
// 终止条件：分别对应有偶数个节点和有奇数个节点
while (cur->next && cur->next->next)
{
// 存1
ListNode* tmp = cur->next;
// 存3
ListNode* tmp1 = cur->next->next->next;
// d->2
cur->next = cur->next->next;
// 2->1
cur->next->next = tmp;
// 1->3
tmp->next = tmp1;
// 后移两位
cur = cur->next->next;
}
return dummyHead->next;
}
};
19.删除链表的倒数第N个节点
本题的笨办法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
int num = -1;
// 计算节点数目
while (cur)
{
cur = cur->next;
num ++ ;
}
// 倒数第n个节点是正数第num - n个节点
cur = dummyHead;
while (num > n) // 不可以写成(num - n) --
{
cur = cur->next;
num -- ;
}
cur->next = cur->next->next;
return dummyHead->next;
}
};
看博客，复习巧妙解法。本题的巧妙解法是快慢双指针。快指针先移动n位，然后快慢指针同时移动，直到快指针移动到链表的最后一个节点。此时，慢指针就指向了需要删除的节点。据此，我写出了本题的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* fast = dummyHead;
ListNode* slow = dummyHead;
// && fast可加可不加，因为本题有限制n<=链表长度，若无此限制，则必须加，否则会出现空指针异常
while (n -- && fast) fast = fast->next;
while (fast->next)
{
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return dummyHead->next;
}
};
也可以让快指针先移动n + 1步，然后快慢指针同时移动，直到快指针移动到链表的NULL节点。
160.相交链表
本题拿到我没什么思路，直接看以前的博客。本题的思路：首先计算两个链表的长度，将较长的链表作为链表a，较短的链表作为链表b。然后a链表从sizea - sizeb处开始, b链表从0处开始遍历，直到找到二者的交汇点。本质上体现的是一种末尾对齐的思想。示意图和代码如下所示：
1 | class Solution { |
时间复杂度O(n + m)，空间复杂度O(1)。
142.环形链表II
我记得本题是用快慢指针解决的，快指针一次走两格，慢指针一次走一格，二者必然会在节点处相遇。我还记得公式怎么推导，但具体的思路记不清楚了，看博客。看完博客后，我写出了如下的代码：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
26class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode* fast = head, * slow = head;
// fast != NULL保证fast->next不报空指针异常
// fast->next != NULL保证fast->next->next不报空指针异常
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
ListNode* node1 = head, * node2 = fast;
while (node1 != node2)
{
node1 = node1->next;
node2 = node2->next;
}
return node1;
}
}
return NULL;
}
};
本题的思路：快慢指针必然会在环中的某处相交，且慢指针在进入环的第一圈中就会和快指针相交。记下交点，让一个指针从起点开始走，另一个指针从交点开始走，二者相交的位置就是环的入口。详细的数学推导和细节见博客。
时间复杂度O(n)，空间复杂度O(1)。
242.有效的字母异位词
本题简单，用数组做哈希，用数组统计一个字符串中各个字母出现的次数，然后遍历另一个字符串，在数组中做减减操作，最后判断数组中的所有元素是否都为0。我独立写出了本题的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
vector<int> hash(26, 0);
for (int i = 0; i < s.size(); i ++ )
{
int tmp1 = s[i] - 'a';
hash[tmp1] ++ ;
int tmp2 = t[i] - 'a';
hash[tmp2] -- ;
}
for (int i = 0; i < 26; i ++ )
{
if (hash[i]) return false;
}
return true;
}
};
需要注意，数组的长度为26，而非s.size()，因为s和t中只含有26个英文字母。可以不用vector，用int类型的数组即可。
本题更简洁的版本的代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
int hash[26] = {0};
for (int i = 0; i < s.size(); i ++ )
{
hash[s[i] - 'a'] ++ ;
hash[t[i] - 'a'] -- ;
}
for (int i = 0; i < 26; i ++ )
if (hash[i]) return false;
return true;
}
};
349. 两个数组的交集
由于本题数据范围的限制，可以用数组做哈希，也可以用unordered_set做哈希。我首先写出了数组做哈希的写法（数组索引的范围与元素取值的范围相同），数组做哈希非常快：
数组哈希，数组去重
1 | class Solution { |
尝试用unordered_set做本题。我不记得怎么用unordered_set做了，也忘记了unordered_set的基本做法，复习博客。
数组哈希，set去重
可以将数组和set结合，这样只需要一个数组即可完成本题：
1 | class Solution { |
这里的set只是起到了去重的功能，没有起到哈希的功能，哈希的任务还是由数组承担了。注意如何将set转换为vector输出，直接vector<int> (res.begin(), res.end())。
set哈希，set去重
也可以完全用set做本题，set既用来做哈希，又用来去重，代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14// 完全用set做本题
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> res;
unordered_set<int> s1(nums1.begin(), nums1.end());
for (int i = 0; i < nums2.size(); i ++ )
if (s1.find(nums2[i]) != s1.end()) res.insert(nums2[i]);
return vector<int> (res.begin(), res.end());
}
};
202. 快乐数
我记得本题有个巧妙的做法。本题使用的数据结构应该是set。我直接看博客复习本题的写法。我错误的根本原因还是对本题的算法思路理解不清晰。在明确了思路后，我写下了如下的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
bool isHappy(int n) {
unordered_set<int> s;
while (1)
{
int sum = 0; // 用于存储各位数字的平方和
while (n)
{
int digit = n % 10;
sum += digit * digit;
n = n / 10;
}
if (sum == 1) return true;
if (s.find(sum) != s.end()) return false;
n = sum;
s.insert(sum);
}
}
};
本题的思路其实很简单，关键在于对平方和的计算和分类讨论（分为三类）。开一个死循环，计算n的各位数字的平方和。若平方和为1，则是快乐数。若平方和在set中出现过，则说明进入了死循环，不是快乐数。否则，将平方和加入到set中，将sum赋给n，进入下一重循环。
时间复杂度和空间复杂度都是O(logn)，详情参见博客。
1. 两数之和
本题要用map解决。用map的key存储索引，map的value存储nums中的值。首先将数组中的值依次存入map中，然后再在map中搜索target - nums[i]，若找到，则返回一对索引。本题思路我是清楚的，但由于忘了map的一些写法，因此复习博客。
实际上，我对本题的理解还是不够深刻。应该是用map的key存储数组中的值，map的value存储数组中的元素的下标，因为我们的目的是快速查找值是否出现过，被快速查找的对象应该被作为key。
先查再插
看完博客后，我写出了以下的代码：
1 | class Solution { |
本题的思路为：先查后插。先查现有的map中有无target - nums[i]，有，则将其索引和i一起加入结果集。无，则将遍历到的元素继续插入map中。这样天然的可以防止同一个元素被取出两次。
记住map的一些用法：
m.insert({nums[i], i})m.find(key) != m.end()auto it = m.find(t); int value = it->second;
插完再查
本题更复杂版本的代码，由于没有先查后插，导致要对找到的索引进行判断，其不能等于当前遍历到的索引，否则会导致同一个数字被使用了两次：
1 | class Solution { |
压缩字符串（面试真题）
将aaaabb压缩为a4b2，将abcde保持原样不动。我独立写出了以下的代码，可以通过所有的测试样例：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
using namespace std;
string compress(string s)
{
if (s.size() == 1) return s;
string res;
char tmp = s[0];
int size = 1;
for (int i = 1; i < s.size(); i ++ )
{
res += tmp;
while (i < s.size() && s[i] == s[i - 1])
{
i ++ ;
size ++ ;
}
if (size > 1) res += to_string(size); // 也可以写成res += '0' + size;
if (i < s.size()) tmp = s[i];
size = 1;
}
// 处理最后一个字符
if (s[s.size() - 1] != s[s.size() - 2]) res += s[s.size() - 1];
return res;
}
int main()
{
// 将aaabb转换为a3b2输出
// 将abcde原样输出
string s = "aaa";
string res = compress(s);
cout << res << endl;
}
其实没有必要在for循环中嵌套while循环，直接用一个for循环就可以搞定。以下的写法为推荐写法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std;
// aaabb->a3b2
string compress(string s)
{
if (s.size() == 0 || s.size() == 1) return s;
string res;
char tmp = s[0];
int size = 1;
for (int i = 1; i < s.size(); i ++ )
{
// 出现相同字母
if (s[i] == s[i - 1]) size ++ ;
// 出现不同字母
else
{
// 将上一个字符和其出现次数（>1）插入res中
res += tmp;
if (size > 1) res += to_string(size);
// 恢复现场
tmp = s[i];
size = 1;
}
}
// 处理字符串的最后一位
res += tmp;
if (size > 1) res += to_string(size);
return res;
}
int main()
{
string s = "aaaanbv";
string res = compress(s);
cout << res << endl;
}
本题的关键在于分两种情况讨论：出现相同的字母/出现不同的字母，最后记得处理字符串的最后一位
通过本题，记住常用操作——将数字转换为字符：to_string(size)
可以写出上述操作的逆过程的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
using namespace std;
bool isdigit(char s)
{
if (s >= '0' && s <= '9') return true;
return false;
}
string decompress(string s)
{
string res;
// s的第一个元素必为字母，从第二个元素开始可能为数字
// 一对对处理，先处理字母，再处理数字（可能有，也可能没有）
for (int i = 0; i < s.size(); i ++ )
{
// 处理字母
char tmp = s[i];
// 处理数字，计算count
int count = 0;
while (i + 1 < s.size() && isdigit(s[i + 1]))
{
count = count * 10 + s[i + 1] - '0';
i ++ ;
}
// 字母加入结果集
if (count == 0) res += tmp;
// 若有数字，则将字母重复数字遍
else while (count -- ) res += tmp; // 也可调用函数res.append(count, tmp);
}
return res;
}
int main()
{
string s = "a56b12";
string res = decompress(s);
cout << res << endl;
}
本题的关键在于字母和数字成对出现（当然数字可能没有），成对地处理字母和数字，将它们成对地放入res中。
454.四数相加II
本题用哈希做的时间复杂度应该为O(n^2)。先枚举nums1和nums2中所有元素之和的组合，然后再在nums3和nums4中查找所有元素之和为-nums1[i] - nums2[j]的情况。由于涉及到索引，所以要用map，map的key存数值，map的value存索引。value似乎要存一组索引，比如(i, j)，我忘记怎么写了，看下博客。
实际上，应该是用map的key存储和，map的value存储出现这个和的次数。据此，我写出了以下的代码：
1 | class Solution { |
更简洁的写法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> m;
for (int num1: nums1)
for (int num2: nums2)
m[num1 + num2] ++ ;
int count = 0;
for (int num3: nums3)
for (int num4: nums4)
if (m.find(-num3 - num4) != m.end())
count += m[-num3 - num4];
return count;
}
};
注意：
- 用map的key存储和，map的value存储出现这个和的次数
- map的key不可重复，map的value可以重复。本题中的map起到一个将相同的和归拢，并用value统计其出现次数的作用
- cpp中的map中的value是支持++操作的，且value可以通过key直接索引到，就像普通的数组那样
- 时间和空间复杂度均为$O(n^2)$，空间复杂度为$O(n^2)$是两数组的数字各不相同，产生了$n^2$种组合。
383. 赎金信
本题用数组做哈希就可以，因为对象就是26个小写英文字母。据此，我写出了以下的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int cnt[26] = {0};
for (int i = 0; i < magazine.size(); i ++ )
cnt[magazine[i] - 'a'] ++ ;
for (int i = 0; i < ransomNote.size(); i ++ )
cnt[ransomNote[i] - 'a'] -- ;
for (int num: cnt)
if (num < 0) return false;
return true;
}
};
终极优化版本：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int cnt[26] = {0};
// Each letter in magazine can only be used once in ransomNote
if (ransomNote.size() > magazine.size()) return false;
for (char m: magazine)
cnt[m - 'a'] ++ ;
for (char r: ransomNote)
{
cnt[r - 'a'] -- ;
if (cnt[r - 'a'] < 0) return false;
}
return true;
}
};
Day 27 Leetcode 93, 78, 90
链接
知识
93.复原IP地址
cpp中的string是有pop_back方法的，用于弹出字符串中的最后一个元素。
字符串中在i的后面插入一个逗点
1
s.insert(s.begin() + i + 1 , '.');
删除特定位置处的逗点
1
s.erase(s.begin() + i + 1);
初次尝试
93.复原IP地址
我尝试按照131.分割回文串的思路做本题，也写出了相应的代码，但运行结果和答案相差很大，而且代码非常复杂。我来看看卡尔的解法，看看如何写出正确而简单地处理这种字符串类型的回溯题的代码。
78.子集
据卡尔说，子集问题，就是收集树形结构中，每一个节点的结果。 整体代码其实和回溯模板都是差不多的。 对于本题的树形结构，我有一个想法：以1, 2, 3为例，首先选中1前面的空位，则要收集空和123。然后选中1，则要收集1和23。然后选中2，则要收集2和13。然后选中3，则要收集3和12。共有8个子集。但本题的代码我写不出来，直接看卡尔的视频讲解。
90.子集II
本题是40.组合总和II再加上78.子集。利用40题的去重办法（树层去重，用used数组，即if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0)），利用78题的子集问题的解法（主要是在所有节点而不仅仅是叶子节点上收集答案）。据此，我独立写出了本题的代码：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
34class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int startIndex, vector<int>& used)
{
res.push_back(path);
// 终止条件
if (startIndex >= nums.size()) return;
// 单层递归逻辑
for (int i = startIndex; i < nums.size(); i ++ )
{
// 树层去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
// 处理节点
path.push_back(nums[i]);
used[i] = 1;
// 递归
backtracking(nums, i + 1, used);
// 回溯
path.pop_back();
used[i] = 0;
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> used(nums.size(), 0);
sort(nums.begin(), nums.end()); // 一定记得要对nums排序
backtracking(nums, 0, used);
return res;
}
};
实现
93.复原IP地址
合法的IP地址：
- 每个整数位于 0 到 255 之间组成
- 数字前不能有0，即不能有先导0
- 不能出现非0-9的字符
因此本题不仅需要对字符串进行切割，还要对子串进行合法性的判断。本题在回溯算法的切割问题中是一道较有难度的题。做了131.分割回文串后，再来做本题，会易于理解一些。使用回溯算法暴力枚举分割的每一种情况。画树形结构图。
画出了上述树形图后，写代码还会有疑惑：
如何模拟切割线
怎么固定切割线，再在剩余的字符串中进行切割
切割出的子串如何表达
接下来写具体的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39vector<string> res;
// startIndex表示下一层递归切割的位置，即切割线
// 一个IP需要有三个逗点进行分割，pointSum用于统计逗点的数量, pointSum决定了树的深度
void backtracking(string& s, int startIndex, int pointSum)
{
// 终止条件
// 每次加逗点，都是对其前面的子串做合法性判断
// 此时还需要专门对最后一个子串做合法性判断，最后一个子串合法了，才能将整个IP地址加入结果集中
// isvalid用于判断一个子串是否合法：数字前不能有0，数字在0-255之间，子串中不能有非法字符
if (pointSum == 3) {
if (isvalid(s, startIndex, s.size() - 1)) // 左闭右闭
{
res.push_back(s); // s会在后面被修改，具体来说是被切割并加上逗点
return;
}
}
// 单层搜索逻辑
for (int i = startIndex; i < s.size(); i ++ )
{
// 切割后，对产生的第一个子串的合法性进行判断。子串的区间：[startindex, i]
if (isvalid(s, startIndex, i))
{
// 进入下一层递归前，需要在子串后面加上逗点
// 将.插入到s.begin() + i的后面，故传入的参数是s.begin() + i + 1
s.insert(s.begin() + i + 1, '.');
pointSum += 1; // 逗点数量+1
// 递归
// 由于给字符串s额外加了一个逗点，因此是i + 2（本来是i + 1）
backtracking(s, i + 2, pointSum);
// 回溯
s.erase(s.begin() + i + 1); // 删除s中插入的逗点
pointSum -= 1;
}
}
}
上述代码的精妙之处在于，就是在原来的字符串s的基础上进行修改，修改就是在合适的位置上添加逗点。本题的关键在于如何模拟切割的过程。切割的过程本质上和组合问题的取数的过程是一样的。另外还需要对子串进行合法性的判断，子串是[startIndex, i]。子串合法后再加上逗点。
根据上述核心代码，我独立写出了解决本题的完整的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72// 直接在s的基础上添加逗号，得到可能的IP地址
class Solution {
public:
vector<string> res;
// 判断区间[start, end]的合法性
// 三个要求：1. 没有非数字的字符
// 2. 在0-255之间
// 3. 没有先导0
bool isvalid(string& s, int start, int end)
{
if (start > end) return false;
string tmp = s.substr(start, end - start + 1);
// 先导0
if (tmp.size() > 1 && tmp[0] == '0') return false;
int sum = 0;
int d = 1;
for (int i = tmp.size() - 1; i >= 0; i -- )
{
// 非数字的字符
if (tmp[i] < '0' || tmp[i] > '9') return false;
sum += (tmp[i] - '0') * d;
d = d * 10;
if (sum > 255) return false;
}
return true;
}
// startIndex为分割线，dotSum为逗点数目
void backtracking(string& s, int startIndex, int dotSum)
{
// 终止条件
if (dotSum == 3)
{
// 对第四段(s的最后一段)做合法性判断
if (isvalid(s, startIndex, s.size() - 1))
{
res.push_back(s);
}
return;
}
// 单层搜索逻辑
// 区间[startIndex, i]
for (int i = startIndex; i < s.size(); i ++ )
{
// 对区间合法性进行判断
if (isvalid(s, startIndex, i))
{
// 合法，则插入逗点
s.insert(s.begin() + i + 1, '.');
dotSum ++ ;
// 递归，本区间终止于i, 故下一个区间开始于i + 2
backtracking(s, i + 2, dotSum);
// 回溯
s.erase(s.begin() + i + 1);
dotSum -- ;
}
}
}
vector<string> restoreIpAddresses(string s) {
backtracking(s, 0, 0);
return res;
}
};
isvalid函数可以写的更简洁更自然：
1 | bool isvalid(string& s, int start, int end) |
- 时间复杂度: $O(3^4)$，IP地址最多包含4个数字，每个数字最多有3种可能的分割方式（1位，2位，3位）；则搜索树的最大深度为4，每个节点最多有3个子节点（对应每个数字可能是1位，2位，3位的情况）。
- 空间复杂度: $O(n)$，原因如下：
- 递归栈：递归的深度固定，最多为4，因为IP地址由四部分组成。但这并不直接决定空间复杂度，因为递归深度很小。
- 存储当前解：在递归过程中，需要存储当前正在构建的IP地址，这需要额外的空间。此外，每次递归调用时，都可能创建字符串的子串来表示IP地址的某一部分。字符串的最大长度为输入字符串的长度n，因此需要额外的空间来存储这些子串。
- 输出解的集合：输出的解的数量并不直接影响空间复杂度的理论计算，但实际上会使用额外空间来存储所有可能的IP地址。然而，这些空间通常不计入空间复杂度计算中，因为它不依赖于递归过程中的临时存储需求。
78.子集
之前讲的组合问题、分割问题，我们都是在树形结构的叶子节点上收获结果，因此在终止条件处收获结果。可以画出如下的树形结构：
观察如上树形结构，发现我们想收获的结果其实在每一个节点中。因此不是在终止条件中收获结果，而是每进入一层递归就将单个结果放入结果集中。现在开始对着树形结果写代码：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// 一维数组存放单个结果
vector<int> path;
// 二维数组作为结果集
vector<vector<int>> res;
// startIndex：下一层递归从哪里开始取数
void backtracking(vector<int> nums, int startIndex)
{
// 每进入一层递归，都要将当前的path放入结果集中
// 因为要将叶子节点的集合放入结果集中，然后再结束，因此先有本逻辑，再有终止条件
res.push_back(path);
// 终止条件：走到叶子节点，叶子节点的剩余集合都为空
// 本终止条件可以不写，因为单层搜索逻辑中的for循环已经对startIndex的大小进行了限制
if (startIndex >= nums.size()) return;
// 单层搜索逻辑
for (int i = startIndex; i < nums.size(); i ++ )
{
// 每进入一层递归，都要收获当前节点的结果，放入单个结果数组中
path.push_back(nums[i]);
// 进入下一层递归
backtracking(nums, i + 1);
// 回溯
path.pop_back();
}
}
不写终止条件的写法如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int startIndex)
{
res.push_back(path);
for (int i = startIndex; i < nums.size(); i ++ )
{
path.push_back(nums[i]);
backtracking(nums, i + 1);
path.pop_back();
}
return;
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
return res;
}
};
90.子集II
与78的区别：给的集合中允许有重复的元素，因此需要对重复子集去重。本题的关键在于去重，本题是子集+组合总和II（树层去重）的结合，并没有新的知识点。
本题的树形结构。used数组用于记录某个元素是否出现过。因为去重要让大小相邻的元素挨在一起，因此需要先对数组进行排序。本题的去重是树层去重（树层上相邻的元素如果相等，则不能重复取，否则会得到重复的子集），树枝不需要去重。
现在开始写代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23vector<int> path; // 单个结果
vector<vector<int>> res; // 结果集
void backtracking(vector<int>& nums, int startIndex, vector<int>& used)
{
// 终止条件不需要写，在for循环中实际上已经限制了startIndex的大小
res.push_back(path); // 收获结果，需要在每个节点都收获结果
// 单层递归逻辑
for (int i = startIndex; i < nums.size(); i ++ )
{
// 树层去重, used[i - 1] == 0意味着第i - 1个元素是第i个元素的回溯
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] = 0) continue;
// 处理节点
path.push_back(nums[i]);
used[i] = 1;
// 递归
backtracking(nums, i + 1, used);
// 回溯
path.pop_back();
used[i] = 0;
}
}
回溯中的去重逻辑都这么写。本题去重也可以用startIndex和i进行比较来实现，但这种去重写法并不通用，遇到排列问题时依然要用used数组的写法进行去重。去重的写法掌握used数组写法即可。
本题的时间和空间复杂度和78相同。时间复杂度: $O(n\times2^n)$，空间复杂度: $O(n)$。
本题也可以用哈希法去重，但时间复杂度更高，虽然也能够通过所有测试样例且不超时，代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int startIndex)
{
res.push_back(path);
unordered_set<int> s;
for (int i = startIndex; i < nums.size(); i ++ )
{
// set去重
if (s.find(nums[i]) != s.end()) continue;
// 处理节点
s.insert(nums[i]);
path.push_back(nums[i]);
// 递归
backtracking(nums, i + 1);
// 回溯
path.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end()); // set去重依然需要排序
backtracking(nums, 0);
return res;
}
};
因此，本题的去重写法有三种：
used数组去重startIndex去重set去重
掌握第一种即可。第一种是思路最清晰也最通用的。
本题像78一样，也可以不写终止条件，因为startIndex的大小在for循环中已经得到了限制。精简版本的代码如下所示：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
30class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums, int startIndex, vector<int>& used)
{
res.push_back(path);
for (int i = startIndex; i < nums.size(); i ++ )
{
// 去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
// 处理节点
path.push_back(nums[i]);
used[i] = 1;
// 递归
backtracking(nums, i + 1, used);
// 回溯
path.pop_back();
used[i] = 0;
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<int> used(nums.size(), 0);
sort(nums.begin(), nums.end());
backtracking(nums, 0, used);
return res;
}
};
心得与备忘录
93.复原IP地址
- 本题是131.分割回文串的加强版。因为和131同样是用回溯法求解的分割问题，所以基本原理是相同的，比如
startIndex用于作为分割线，分割的区间是[startIndex, i]。 - 本题的终止条件和131有显著地不同。131的终止条件是
startIndex移动到字符串的末尾，而本题的终止条件是添加了3个逗点，且最后一段区间是合法的。3个逗点的终止条件也限制了树的深度。 - 一般处理字符串的问题都比较复杂。本题对字符串处理的精妙之处在于直接在原本的字符串
s上进行修改，添加逗点，作为分隔符从而得到合法的IP地址。本题还用到了两个和字符串有关的STL，分别是insert和erase函数。 - 本题对区间合法性的判断较为复杂，共有3个要求：
- 段位以0为开头的数字不合法
- 段位里有非正整数字符不合法
- 段位如果大于255了不合法
- 段位若大于255，则立即判断为不合法，
return false。若完成for循环后再对num进行判断，可能出现整数型变量溢出
- 本题的时间复杂度：$O(3^4)$，空间复杂度：$O(n)$
- 本题的细节比较多，比较容易写错，属于回溯法解决分割问题中的难题，需要不断复习。
78.子集
- 子集是收集树形结构中树的所有节点的结果。而组合问题、分割问题是收集树形结构中叶子节点的结果。
- 子集也是一种组合问题，因为它的集合是无序的，子集{1,2}和子集{2,1}是一样的。那么既然是无序，取过的元素不会重复取，写回溯算法的时候，for就要从startIndex开始。
- 先收集结果集，再写终止条件的原因：当递归到叶子节点时，要先将叶子节点的结果放入结果集中，再终止，因此先写收集结果集的逻辑，再写终止条件。否则叶子节点的结果无法被放入结果集中。
- 本题也可以不写终止条件，因为单层递归逻辑的for循环中实际上限制了
startIndex的大小，因此最后return即可。但初学者还是建议写终止条件，和标准的回溯模板保持一致。 - 本题的时间复杂度: $O(n\times2^n)$，空间复杂度: $O(n)$。时间和空间复杂度的分析同77.组合。
90.子集II
本题是40.组合总和II与78.子集这两题的结合。
40的精华在于去重（树层去重），78的精华在于在每个节点处都收集结果（而不是像组合、分割问题那样在叶子节点，即终止条件处收集结果），而是在递归函数的开始处（进入递归相当于进入一个节点）收集结果。本题结合了两题的精华。
树层去重掌握
used数组写法即可，具体代码为：1
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
- 树层去重前，需要对
nums数组进行排序。 - 本题的时间和空间复杂度和上一题（78）相同。
- 去重共有三种写法，掌握思路最清晰也最通用的
used数组写法即可。 - 本题像78一样，也可以不写终止条件，因为
startIndex的大小在for循环中已经得到了限制。
Day 26 Leetcode 39, 40, 131
链接
知识
40.组合总和II
创建一个和a数组大小相同的b数组，将其中的元素全部置为0。1
2vector<int> a;
vector<int> b(a.size(), 0);
131.分割回文串
substr(i, j) 会从索引 i 开始，取长度为 j 的子字符串。
void backtracking(const string& s, int startIndex)中使用const的原因：
- 防止修改：
const关键字确保s字符串在backtracking函数中不会被修改。这是一种安全措施，可以防止函数意外地更改输入数据，从而保持数据的完整性。在处理函数参数时，尤其是在不应该或不需要修改输入的情况下，使用const可以提供这种保护。 - 接口设计：在函数原型中使用
const声明参数可以向函数的用户清楚地表明这个参数是用来输入数据的，不应该被函数改变。这有助于提高代码的可读性和可维护性，使得其他开发者更容易理解每个函数的作用和行为。
初次尝试
39.组合总和
本题是集合里元素可以用无数次，那么和组合问题的差别，其实仅在于startIndex上的控制。本题若是想不重不漏，则下一层遍历的起始位置应该与上一层取出的数相同。而对于组合问题，下一层遍历的起始位置应该是上一层取出的数的下一个（因为组合问题中的元素不能重复使用）。据此，我写出了以下的代码。
1 | class Solution { |
40.组合总和II
本题我能顺畅地写出不加去重的版本，如下所示。但对去重没有思路。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
35class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& candidates, int target, int s, int startIndex)
{
// 终止条件
if (s > target) return;
if (s == target)
{
res.push_back(path);
return;
}
// 单层搜索逻辑
for (int i = startIndex; i < candidates.size(); i ++ )
{
// 处理节点
path.push_back(candidates[i]);
s += candidates[i];
// 递归
backtracking(candidates, target, s, i + 1);
// 回溯
path.pop_back();
s -= candidates[i];
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
backtracking(candidates, target, 0, 0);
return res;
}
};
对以下测试样例会出现报错：1
2
3
4
5
6
7
8candidates =
[10,1,2,7,6,1,5]
target =
8
Output
[[1,2,5],[1,7],[1,6,1],[2,6],[2,1,5],[7,1]]
Expected
[[1,1,6],[1,2,5],[1,7],[2,6]]
很明显，上述代码是需要去重的。
131.分割回文串
拿到本题，我没有思路，因为没有做过分割问题，直接看卡尔的讲解。
实现
39.组合总和
本题与组合问题的区别：集合中的元素可以重复选取，组合中元素的数量不加限定。集合中都是正整数（若有0，则会进入死循环），且集合中没有重复的元素（这意味着不用做去重的操作）。
本题通过和来限制树的深度，而组合问题通过组合中元素的数量来限制树的深度。本题的树形结构如下所示：
由于集合中的元素可以重复使用，因此下一层的集合中应该包括本层选取的元素。现在开始写本题的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28vector<vector<int>> res;
vector<int> path;
// 可以用sum表示组合的和，也可以不用sum，让target不断做减法，直到target == 0
// startIndex用于设置下一层递归的起点
void backtracking(vector<int>& candidate, int target, int sum, int startIndex)
{
// 终止条件
if (sum > target) return;
if (sum == target)
{
res.push_back(path);
return;
}
// 单层搜索的逻辑
for (int i = startIndex; i < candidate.size(); i ++ )
{
// 处理节点
path.push_back(candidate[i]);
sum += candidate[i];
// 递归，注意下一层的startIndex是从i开始，因为集合中的元素可以重复选取
backtracking(candidate, target, sum, i);
// 回溯
sum -= candidate[i];
path.pop_back();
}
}
上述代码和回溯算法的模板是类似的。本题依然可以做剪枝的操作。具体来说，是对for循环进行剪枝。对candidate数组进行排序后，若某个分支的和大于target，那么就没必要对其后面的分支进行搜索了。加入剪枝操作的完整代码如下所示（注意添加了注释的部分，就是实现剪枝的具体代码）：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
32class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& candidates, int target, int s, int startIndex)
{
if (s > target) return;
if (s == target)
{
res.push_back(path);
return;
}
// 剪枝操作
for (int i = startIndex; i < candidates.size() && s + candidates[i] <= target; i ++ )
{
s += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, s, i);
s -= candidates[i];
path.pop_back();
}
return;
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
sort(candidates.begin(), candidates.end()); // 排序
backtracking(candidates, target, 0, 0);
return res;
}
};
剪枝操作总结：对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]，相当于把下一层组合可能的sum从小到大扫了过去）已经大于target，就可以结束本轮for循环的遍历。
时间复杂度: $O(n \times 2^n)$，注意这只是复杂度的上界，因为剪枝的存在，真实的时间复杂度远小于此。本题的时间复杂度分析同77. 组合。
空间复杂度: $O(target)$
为何是$O(target)$:
- 递归栈深度： 空间复杂度首先取决于递归调用的最大深度，因为这直接影响了调用栈的大小。在组合总和问题中，你可以多次选择同一个数字，直到其和超过目标值
target或恰好等于target。最糟糕的情况发生在选择了最小元素直到达到target时，这种情况下，递归的最大深度大约是target / min(candidates)。如果最小的候选数很小，理论上递归的深度可以接近target。 - 路径存储： 在递归过程中，我们还需要存储当前的组合路径（即当前选取的数字集合）。在最坏的情况下，即当所有选取的数字加起来等于
target时，路径的长度也可以接近于target / min(candidates)。尽管路径的具体长度依赖于候选数字的大小，但在分析空间复杂度时，我们考虑最坏情况，即多次选取最小值，使得路径长度和递归深度都接近于target。
40.组合总和II
本题差别：本题的集合中有重复的元素（之前的所有组合问题的集合中都没重复元素），不能有重复的组合。这说明我们要去重。另外，集合中的元素在组合中只能使用一次，这需要用一个变量进行控制。
一种朴素的想法：用之前的方法搜索组合，搜索出若干组合，其中肯定有重复的。用map或者set进行去重，输出去重后的所有组合。本方法实现起来较麻烦，且特别容易超时。
接下来介绍在搜索的过程中直接去重的方法：使用过的元素不重复使用。为了讲清楚本题的去重过程，卡尔自创了两个词汇：树层去重，树枝去重。去重要考虑到这两个维度。接下来画树形图，从两个维度看如何去重。去重前还需要对集合进行排序。去重需要一个数组used来告诉我们哪些元素使用过，哪些元素没用过。用过的元素的下标在used中对应的值为1，没用过的元素的下标在used中对应的值为0。
上述树除去used数组外的基本部分，还是下一层第一个取的数是上一层取的数往后挪一位（即backtracking(candidates, target, s, 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
37vector<int> path;
vector<vector<int>> res;
// 本代码的重点在于树层去重的过程
// used数组用于标记某个元素是否使用过，用过1，没用过0
// 调用本函数前需要对集合做排序，目的是让值相同的元素在位置上相邻，方便做树层去重
void backtracking(vector<int> nums, int targetSum, int sum, int startIndex, vector<int> used)
{
// 终止条件
if (sum > targetSum) return;
if (sum == targetSum)
{
res.push_back(path);
return;
}
// 单层搜索逻辑
// for循环是在同一层遍历各个节点，因此接下来就要写树层去重的逻辑
for (int i = startIndex; i < nums.size(); i ++ )
{
// 树层去重, i > 0的目的是让i - 1 >= 0，也可以写作i > startIndex
// used[i - 1] == 0对应于上面树的情况，就是第1个1没用，直接用了第2个1，此时重复读取，需要树层去重
// 若nums[i] == nums[i - 1] && used[i - 1] == 1，则说明是树枝的状态，由于不需要树枝去重，所以此时不需要去重
// 后续在回溯算法中遇到去重问题并使用used数组时，基本都是这种写法
if (i > startIndex && nums[i] == nums[i - 1] && used[i - 1] == 0) continue;
// 收集元素
path.push_back(nums[i]);
sum += nums[i];
used[i] = 1;
// 递归
backtracking(nums, targetSum, sum, i + 1, used);
// 回溯
path.pop_back();
sum -= nums[i];
used[i] = 0;
}
}
可以用used数组进行去重，也可以用startIndex进行去重，这里不再深入讲解。用startIndex去重比较抽象，因此理解用used数组去重即可，更易于理解且通用。本题的关键在于理解去重的思路。
本题的完整代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& candidates, int target, int s, int startIndex, vector<int> used)
{
// 终止条件
if (s > target) return;
if (s == target)
{
res.push_back(path);
return;
}
// 单层搜索逻辑
for (int i = startIndex; i < candidates.size(); i ++ )
{
// 树层去重
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == 0) continue;
// 处理节点
path.push_back(candidates[i]);
used[i] = 1;
s += candidates[i];
// 递归
backtracking(candidates, target, s, i + 1, used);
// 回溯
path.pop_back();
used[i] = 0;
s -= candidates[i];
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// used数组用于标记candidates数组中的元素是否使用过，因此used数组大小应该与candidates数组大小保持相同
vector<int> used(candidates.size(), 0);
sort(candidates.begin(), candidates.end()); // 别忘记排序
backtracking(candidates, target, 0, 0, used);
return res;
}
};
时间复杂度: $O(n \times 2^n)$。同77.组合和39.组合总和。
空间复杂度：$O(n)$。原因：树的最大深度为n（同candidates数组的长度）。
131.分割回文串
aab。有两种分割方案：aa|b和a|a|b。本题要求我们返回所有的分割方案。如何使用回溯算法解决这个问题？
分割问题和组合问题非常相似。例如abcdef，对组合问题，如果选择了a，则在bcdef中选择下一个字母；如果选择了b，则在cdef中选择下一个字母。同理，对于分割问题，如果分割了a，则接下来分割bcdef。再分割b，则接下来分割cdef。接下来画分割问题的树形结构。
切割线到了字符串的末尾，则切割完毕。结果都在叶子节点。画树形结构较为简单，具体的代码实现中有几个难点，现在开始写具体的代码：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
35vector<string> path;
vector<vector<string>> res;
// 注意传入的变量类型是const string，再加上引用
// startIndex控制下一次切割的位置
void backtracking(const string& s, int startIndex)
{
// 终止条件
// 切割线到字符串的末尾，则终止
// 切割线用startIndex表示
if (startIndex >= s.size())
{
// 将判断是否是回文的逻辑放入单层搜索的逻辑中
// 因此终止条件中的path都是符合回文条件的
res.push_back(path);
return;
}
// 单层搜索的逻辑
for (int i = startIndex; i < s.size(); i ++ )
{
// 如何用代码表示切割出的子串
// 切割的子串：[startIndex, i]，左闭右闭的区间
// 用于判断是否回文的函数
if (isPalindrome(s, startIndex, i)) // 传入字符串，子串的起始位置，子串的终止位置
{
path.push_back(子串); // 是回文，则将子串放入path中
}
else continue;
// 递归
backtracking(s, i + 1); // 下一层切割点从上一层切割点的下个位置开始，否则会重复
// 回溯
path.pop_back();
}
}
isPalindrome函数用双指针算法可以轻松实现。注意本题的两个细节：
startIndex是切割线如何表示子串的范围：
[startIndex, i]
完整的代码如下所示：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44class Solution {
public:
vector<string> path;
vector<vector<string>> res;
// 判断[start, end]是否是回文子串
bool isPalindrome(const string& s, int start, int end)
{
for (int i = start, j = end; i <= j; i ++ , j -- )
if (s[i] != s[j])
return false;
return true;
}
void backtracking(const string& s, int startIndex)
{
// 终止条件
if (startIndex >= s.size())
{
res.push_back(path);
return;
}
// 单层搜索逻辑
for (int i = startIndex; i < s.size(); i ++ )
{
// 是回文子串，则将其加入path中
if (isPalindrome(s, startIndex, i))
path.push_back(s.substr(startIndex, i - startIndex + 1));
else continue;
// 递归
backtracking(s, i + 1);
// 回溯
path.pop_back();
}
}
vector<vector<string>> partition(string s) {
backtracking(s, 0);
return res;
}
};
时间复杂度: $O(n \times 2^n)$，时间复杂度同77.组合、39.组合总和、40.组合总和II。
空间复杂度: $O(n^2)$，原因解释如下：
- 递归栈的空间：最深的递归发生在当字符串每个字符都被分割时，因此递归深度最大为$n$（其中$n$是字符串的长度）。每一层递归需要保存当前索引和路径，这些额外的空间可以认为是常数级别的。
- 路径存储空间 (
path和res):path变量在最坏情况下（每个字符都独立成一个回文串时）会存储$n$个元素。res变量存储的是所有可能的分割方案。在极端情况下，如输入字符串完全由相同字符组成（例如 “aaaa”），分割方案的数量和其中每个方案的长度都可能接近$n$。但通常来说，我们只计算这个变量直接占用的空间，即指针或引用的空间，这通常也是$O(n^2)$，因为每个回文分割的保存都可能需要一个长度为 的$n$字符串的复制。
- 辅助空间：
- 检查回文所用的额外空间是常量级的，不随输入大小变化。
将以上所有考虑结合，整个算法的空间复杂度主要由存储所有分割方案的数组
res决定。由于每个分割方案可能包含多个字符串，而每个字符串又可能需要$O(n)$的空间，因此在最坏情况下，这部分的空间复杂度为$O(n⋅k)$，其中 $k$是分割方案的数量，这在极端情况下可以达到$O(n^2)$。
心得与备忘录
39.组合总和
- 本题通过
target来限制树的深度，而77. 组合通过组合中元素的个数来限制树的深度。 - 本题是集合里元素可以用无数次，那么和组合问题的差别，其实仅在于
startIndex上的控制。本题若是想不重不漏，则下一层遍历的起始位置应该与上一层取出的数相同。而对于组合问题，下一层遍历的起始位置应该是上一层取出的数的下一个（因为组合问题中的元素不能重复使用）。 - 本题的时间复杂度：$O(n \times 2^n)$，空间复杂度：$O(target)$。
- 本题可以进行剪枝操作。具体来说，是对for循环进行剪枝。对
candidate数组进行排序后，若某个分支的和大于target，那么就没必要对其后面的分支进行搜索了。体现在代码上，就是对总集合排序之后，如果下一层的sum（就是本层的sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。本题的剪枝不好想，要多加注意。
40.组合总和II
本题的难点：集合有重复元素，但组合不能重复。
本题需要对组合去重，但不能在搜索完整棵树后用哈希法去重，容易超时。需要在搜索的过程中去重，这需要用到
used数组。其中用过的元素标记为1，没用过的元素标记为0。去重：只需要树层去重（树的同一层若两元素值相同，则右侧的值所在的路径必然被包含在左侧的值所在的路径中），不需要树枝去重（集合中的元素值可以相同，每个元素均可以使用一次，因此不需要对树枝去重）。
本题不可忽视的几个细节：
集合需要进行排序，这是为了将值相同的元素放在集合中相邻的位置，便于树层去重
used数组的大小需要与candidates数组保持相同，因为其是用来标记candidates数组中元素的使用情况的注意树层去重的代码的写法，建议结合实际例子（实现中的图片）进行理解
1
2// 树层去重
if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == 0) continue;candidates[i] == candidates[i - 1] && used[i - 1] == 0说明同一树层上相邻的两个元素相同，此时需要进行树层去重used[i - 1] == 1，说明同一树枝上的candidates[i - 1]被使用过（同一树枝从上往下遍历，未进行回溯，因此candidates[i - 1]始终被标记为被使用过，即used[i - 1] = 1）used[i - 1] == 0，说明同一树层上的candidates[i - 1]被使用过（同一树层从左往右经历过回溯的过程：先对candidates[i - 1]所在的树枝从上往下遍历，然后回溯，再对candidates[i]所在的树枝从上往下遍历。在回溯的过程中，candidates[i - 1]被重新标记为未被使用过，即used[i - 1] = 0）
本题的去重代码不好写，同时细节较多需要注意。因此本题容易写错，需要时常复习。
后续在回溯算法中遇到去重问题并使用
used数组时，基本都是这种写法：if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == 0) continue;。本题也可以用
startIndex进行去重，但比较难理解，因此不要求掌握。本题可以像39.组合总和一样进行剪枝操作，只需要在for循环中对i加上限制条件：
s + candidates[i] <= target即可。
131.分割回文串
首先，切割问题其实本质和组合问题是相同的。
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…..。接着选取一个b后，再从cdef中再去选取第二个，以此类推。
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…..。接着从b那里切下去，在cded中再去切割第二段，以此类推。
可以观察本题的树形结构图，能够更加直观地理解切割问题和组合问题的相似。
什么是切割线？
递归参数需要传入
startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。终止条件：切割线
startIndex移动到了字符串的末尾，即startIndex >= s.size()如何截取子串？
[startIndex, i]之间的字符串就是子串。用substr函数截取即可。需要判断子串是否是回文串，是则放入path中，不是则continue。使用最简单的双指针算法即可写出判断字符串是否是回文串的函数。
本题的空间复杂度$O(n^2)$。是极端情况下的空间复杂度，原因参见本题的实现部分。
从主函数传入的参数，在定义其他函数时若需要这个参数，则需要将其设置为
const类型。目的是防止其他函数对这个参数的修改，同时向函数的用户清楚地表明这个参数是用来输入数据的。不加const不影响代码的正常运行，但加了const后代码更加规范。