代码随想录中各类型的解题思路

1、递归三要素

1. 确定递归函数的参数和返回值：
   确定哪些参数是递归的过程中需要处理的，那么就在递归函数⾥加上这个参数， 并且还要明确每次递归的返回值是什么进⽽确定递归函数的返回类型。
2. 确定终⽌条件：
   写完了递归算法，运⾏的时候，经常会遇到栈溢出的错误，就是没写终⽌条件或者终⽌条件写的不对，操作系统也是⽤⼀个栈的结构来保存每⼀层递归的信息，如果递归没有终⽌，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑：
   确定每⼀层递归需要处理的信息。在这⾥也就会重复调⽤⾃⼰来实现递归的过程。

1、 递归的实现就是：每⼀次递归调⽤都会把函数的局部变量、参数值和返回地址等压⼊调⽤栈中，然后递归返回的时候，从栈顶弹出上⼀次递归的各项参数，所以这就是递归为什么可以返回上⼀层位置的原因。
2、 如果需要遍历整颗树，递归函数就不能有返回值。如果需要遍历某⼀条固定路线，递归函数就⼀定要有返回值！
3、如果需要搜索整颗⼆叉树，那么递归函数就不要返回值。如果要搜索其中⼀条符合条件的路径，递归函数就需要返回值，因为遇到符合条件的路径了就要及时返回。

例题1：二叉树的前序遍历

class Solution {
public:
 void traversal(TreeNode* cur, vector<int>& vec) {//（1）递归函数的参数和返回值
 	//（2）终⽌条件
 	if (cur == NULL) return;
 
 	// （3）单层递归的逻辑
	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;
 }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2、回溯三部曲

1. 回溯函数模板返回值以及参数
   （1）在回溯算法中，习惯将回溯函数命名为backtracking，这个起名⼤家随意。
   （2）回溯算法中函数返回值⼀般为void。
   （3）对于参数，因为回溯算法需要的参数可不像⼆叉树递归的时候那么容易⼀次性确定下来，所以⼀般是先写逻辑，然后需要什么参数，就填什么参数。
   综上，回溯函数伪代码如下：

void backtracking(参数)
1

2. 回溯函数终⽌条件
   （1）既然是树形结构，那么遍历树形结构⼀定要有终⽌条件。所以回溯也有要终⽌条件。
   （2）什么时候达到了终⽌条件，树中就可以看出，⼀般来说搜到叶⼦节点了，也就找到了满⾜条件的⼀条答案，把这个答案存放起来，并结束本层递归。
   综上，回溯函数终⽌条件伪代码如下：

if (终⽌条件) {
 存放结果;
 return;
}
1
2
3
4

3. 回溯搜索的遍历过程
   回溯法⼀般是在集合中递归搜索，集合的⼤⼩构成了树的宽度，递归的深度构成的树的深度。
   如图：
   
   注意图中，特意举例集合⼤⼩和孩⼦的数量是相等的！
   综上，回溯函数遍历过程伪代码如下：

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

for循环就是遍历集合区间，可以理解⼀个节点有多少个孩⼦，这个for循环就执⾏多少次。
backtracking这⾥⾃⼰调⽤⾃⼰，实现递归。
可从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了。
⼀般来说，搜索叶⼦节点就是找的其中⼀个结果了。

总结：回溯算法模板框架如下

void backtracking(参数) {
 if (终⽌条件) {
 	（1）存放结果;
 	（2）return;
 }
 for (选择：本层集合中元素（树中节点孩⼦的数量就是集合的⼤⼩）) {
 	（1）处理节点;
	（2）backtracking(路径，选择列表); // 递归
 	（3）回溯，撤销处理结果
 }
}
1
2
3
4
5
6
7
8
9
10
11

补充：

什么是回溯法：
回溯法也可以叫做回溯搜索法，它是⼀种搜索的⽅式。
回溯是递归的副产品，只要有递归就会有回溯。即回溯和递归是⼀⼀对应的，有⼀个递归，就要有⼀个回溯。
回溯函数也就是递归函数，指的都是⼀个函数。
回溯法的效率：
回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案。如果想让回溯法⾼效⼀些，可以加⼀些剪枝的操作，但也改不了回溯法就是穷举的本质。即，回溯法其实就是暴⼒查找。
如何理解回溯法：
回溯法解决的问题都可以抽象为树形结构（N叉树）。
因为回溯法解决的都是在集合中递归查找⼦集，集合的⼤⼩构成了树的宽度，递归的深度构成的树的深度。递归就要有终⽌条件，所以必然是⼀颗⾼度有限的树（N叉树）。
适用题目：
1、组合问题；
2、分割问题
3、子集问题
4、排列问题

例题1：给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合（无顺序。即顺序不同，但数一样的组合都视为一个组合）。
示例：
输⼊: n = 4, k = 2
输出: [
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
回溯法就是解决这种k层for循环嵌套的问题

class Solution {
private:
 vector<vector<int>> result; // 存放符合条件结果的集合
 vector<int> path; // ⽤来存放符合条件结果
 void backtracking(int n, int k, int startIndex) {// （1）回溯函数模板返回值以及参数
 	// （2）回溯函数终⽌条件
	if (path.size() == k) {
		result.push_back(path);
		return;
 	}
 	
 	// （3）回溯搜索的遍历过程
	for (int i = startIndex; i <= n; i++) {
		path.push_back(i); // 处理节点
		backtracking(n, k, i + 1); // 递归
		path.pop_back(); // 回溯，撤销处理的节点
	}
 }
public:
 vector<vector<int>> combine(int n, int k) {
 	result.clear(); // 可以不写
 	path.clear(); // 可以不写
 	backtracking(n, k, 1);
 	return result;
 }
};
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

优化：比如n=4,k=4。
可以剪枝的地⽅就在递归中每⼀层的for循环所选择的起始位置。
如果for循环选择的起始位置之后的元素个数 已经不⾜ 我们需要的元素个数了，那么就没有必要搜索了。

class Solution {
private:
 vector<vector<int>> result;
 vector<int> path;
 void backtracking(int n, int k, int startIndex) {
	 if (path.size() == k) {
		 result.push_back(path);
		 return;
	 }
	 for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) { // 优化的地⽅
		 path.push_back(i); // 处理节点
		 backtracking(n, k, i + 1);
		 path.pop_back(); // 回溯，撤销处理的节点
	 }
 }
public:
 vector<vector<int>> combine(int n, int k) {
	 backtracking(n, k, 1);
	 return result;
 }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1、对于组合问题，什么时候需要startIndex来 控制 for循环的起始位置呢？
答：如果是⼀个集合来求组合的话，就需要startIndex；如果是多个集合取组合，各个集合之间相互不影响，那么就不⽤startIndex。
2、复杂度问题：
（1）⼦集问题分析：
时间复杂度：O(n * 2^n)，因为每⼀个元素的状态⽆外乎取与不取，所以时间复杂度为O(2^n)，构造每⼀组⼦集都需要填进数组，⼜有需要O(n)，最终时间复杂度：O(n * 2^n)
空间复杂度：O(n)，递归深度为n，所以系统栈所⽤空间为O(n)，每⼀层递归所⽤的空间都是常数级别，注意代码⾥的result和path都是全局变量，就算是放在参数⾥，传的也是引⽤，并不会新申请内存空间，最终空间复杂度为O(n)
（2）排列问题分析：处理排列问题就不⽤使⽤startIndex了
时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每⼀层节点为n，第⼆层每⼀个分⽀都延伸了n-1个分⽀，再往下⼜是n-2个分⽀，所以⼀直到叶⼦节点⼀共就是 n * n-1 * n-2 * … 1 =n!。
空间复杂度：O(n)，和⼦集问题同理。
（3）组合问题分析：
时间复杂度：O(n * 2^n)，组合问题其实就是⼀种⼦集的问题，所以组合问题最坏的情况，也不会超过⼦集问题的时间复杂度。
空间复杂度：O(n)，和⼦集问题同理。
⼀般说道回溯算法的复杂度，都说是指数级别的时间复杂度，这也算是⼀个概括吧！

3、贪⼼算法⼀般分为如下四步：

1. 将问题分解为若⼲个⼦问题
2. 找出适合的贪⼼策略
3. 求解每⼀个⼦问题的最优解
4. 将局部最优解堆叠成全局最优解

1、贪⼼的本质是选择每⼀阶段的局部最优，从⽽达到全局最优。
2、⼿动模拟⼀下感觉可以局部最优推出整体最优，⽽且想不到反例，那么就试⼀试贪⼼。

4、动态规划五部曲

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

1、使用场景：如果某⼀问题有很多重叠⼦问题，使⽤动态规划是最有效的。
2、与贪心的区别：动态规划中每⼀个状态⼀定是由上⼀个状态推导出来的；贪⼼没有状态推导，⽽是从局部直接选最优的。即，动规是由前⼀个状态推导出来的，⽽贪⼼是局部直接选最优的。