一、暴力递归和回溯
1.1、暴力递归概念说明
暴力递归就是尝试
- 将问题转换为规模缩小了的同类问题的子问题。
- 有明确的不需要继续进行递归的条件，这个条件是递归的退出条件
- 有当得到了子问题的结果**之后的决策过程
- 不记录每一个子问题的解
1.2、回溯算法概念说明
回溯算法实际上就是 N 叉树的遍历 ，这个 N 等于当前可做的选择（choices）的总数，同时，在前序遍历的位置作出当前选择（choose 过程），然后开始递归，最后在后序遍历的位置取消当前选择（unchoose 过程）。
1
2
3
4
5
6
7
8
9
| result = []
def backtrack(路径, 选择列表) :
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
|
回溯算法相当于一个决策过程，递归地遍历一棵决策树，穷举所有的决策，同时把符合条件的决策挑出来。
在过程中，我们需要思考三个问题：
- 路径：也就是已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：也就是到达决策树底层，此时无法继续做选择的条件
1.3、逆序一个栈
1、题目描述
给定一个栈，在不申请额外数据结构的前提下，使用递归函数逆序这个栈
2、解题思路
比如说，有一个栈，元素从顶而下分别是 [1,2,3] ，那么这个函数可以将栈底的 3 取出，同时将栈变为 [1,2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| /**
* 这个方法的作用是，将栈底的元素取出并返回。
* @param stack
* @return
*/
public static int getLastElementFromStack(Stack<Integer> stack) {
// 使用一个临时变量来接收当前传入栈栈顶的元素
int result = stack.pop();
if (stack.isEmpty()) {
// 如果取出元素后栈为空，那么证明 result 保存的就是栈底元素
// 此时直接返回即可
return result;
} else {
// 否则进行递归，获取栈的最后一个元素
int last = getLastElementFromStack(stack);
// 将临时变量压入栈中
stack.push(result);
return last;
}
}
|
假设现在有一个栈，栈元素自顶而下依次是 [1,2,3] ，那么我们使用上面那个函数获取栈底元素 3 的过程如下
在第二次进行递归调用时，之前的栈顶元素会在第一次方法调用中被 result 变量保存，不会丢失
在第三次调用 getLastElementFromStack 函数后，此时已经获取到了栈底元素，于是进行退栈
假设我们此时要逆序的栈还是 [1,2,3] ，那么第一次进入 reverseStack 时，他会将栈底元素 3 保存在 temp 中，然后将 [1,2] 作为参数继续进行递归，此时第二次调用 reverseStack ，将 2 保存到 temp 中，同时将 [1] 作为参数继续进行递归，此时第三次调用 reverseStack ，将 1 保存到 temp 中，然后将 [] 作为参数继续进行递归，此时第四次调用 reverseStack ，由于传入的栈为空，那么进行返回，此时回到第三次调用时的栈帧中，将第三次调用时保存的 1 压入到栈中，此时栈为 [1] ，然后此次调用结束，然后分别回到第二次、第一次调用时产生的栈帧中，将该栈帧中 temp 保存的 2 和 3 依次压入栈中，此时逆序完成。
1
2
3
4
5
6
7
8
9
| public static void reverseStack(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
// 获取当前栈的最后一个元素
int temp = getLastElementFromStack(stack);
reverseStack(stack);
stack.push(temp);
}
|
1.4、获取一个字符串的全部子序列
1、解题思路
对于这道题，我们可以遍历字符串，然后对这个字符串的每个字符都进行一次选择，即是否选择将当前遍历到的字符加入到结果中，对全部的字符都选择一遍后，就可以得到全部的字符串子序列
2、解题代码
1
2
3
4
5
6
7
8
9
10
11
12
| public static void getSubsequenceList(int index, String str, List<String> result, String path) {
// 如果当前 index 与字符串长度相同，那么证明已经对字符串的最后一个字符做出了选择
// 此时直接将 path 加入到结果列表中并返回即可
if (index == str.length()) {
result.add(path);
return;
}
// 进行选择，这个函数表示不将当前字符选择进子序列中
getSubsequenceList(index + 1, str, result, path);
// 这个函数表示将当前字符选择进子序列中
getSubsequenceList(index + 1, str, result, path + str.charAt(index));
}
|
1.5、转换结果
1、题目描述
规定 1 对应 A 、2 对应 B 、3 对应 C ，那么一个数字字符串比如 111 可以转换为 AAA 、KA 和 AK
给定一个只有数字组成的字符串 str ，返回有多少种转换结果.
2、解题思路
以 11111 为例，它的转换过程可以如下
- 将第一个 1 转为 A ，然后把剩下四个 1 看为另外一个部分，对剩下的部分进行转换
- 将前面两个 1 转为 K ，然后将剩下的三个 1 看为另一个部分，对剩下的部分进行转换
由于 111 无法转换为对应的数，所以 11111 没有其他的分支
3、解题代码
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
|
public static int process(String str, int index) {
if (index == str.length()) {
return 1;
}
if (str.charAt(index) == '0') {
return 0;
}
if (str.charAt(index) == '1') {
int result = process(str, index + 1);
if (index + 1 < str.length()) {
result += process(str, index + 2);
}
return result;
}
if (str.charAt(index) == '2') {
int result = process(str, index + 1);
if (index + 1 < str.length() && str.charAt(index + 1) >= '0' && str.charAt(index + 1) <= '6') {
result += process(str, index + 2);
}
return result;
}
return process(str, index + 1);
}
|
1.6、全排列
1、题目描述
给定一个不含重复数字的数组 **nums ，返回其 **所有可能的全排列 。你可以 按任意顺序 返回答案。
1
2
| 输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
|
1
2
| 输入：nums = [0,1]
输出：[[0,1],[1,0]]
|
2、解题思路
- 使用回溯算法解决这道题，我们需要明确这道题的三个条件
- 路径：当前已经进行排列的数字集合，我们将他们放在一个列表中
- 选择列表：nums 数组中不存在于 路径 中的那些元素
- 结束条件：当 nums.length 等于路径列表的长度时，此时 nums 中的所有元素都在路径列表中出现
3、解题代码
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
| public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
LinkedList<Integer> path = new LinkedList<>();
dfs(nums, path, result);
return result;
}
private void dfs(int[] nums, LinkedList<Integer> path, List<List<Integer>> result) {
if (nums.length == path.size()) {
result.add(new LinkedList(path));
return;
}
for (int i = 0;i < nums.length;i++) {
if (path.contains(nums[i])) {
continue;
}
path.addLast(nums[i]);
dfs(nums, path, result);
path.removeLast();
}
}
|
1.7、子集
1、题目描述
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
1
2
| 输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
|
2、解题思路
- 使用回溯算法解决这道题，这道题与 1.4 获取字符串的全部子序列一题的解题思路一致，都是在每一步分别对当前元素进行选择，然后收集选择对应的结果
3、解题代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) return result;
LinkedList<Integer> path = new LinkedList<>();
dfs(0, nums, result, path);
return result;
}
private void dfs(int index, int[] nums, List<List<Integer>> result, LinkedList<Integer> path) {
if (index == nums.length) {
result.add(new LinkedList(path));
return;
}
path.addLast(nums[index]);
dfs(index + 1, nums, result, path);
path.removeLast();
dfs(index + 1, nums, result, path);
}
|
