Skip to content

Commit f791f40

Browse files
linwtlinwt
committed
回溯题型13道
1 parent 711a312 commit f791f40

16 files changed

+783
-3
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,16 +8,26 @@
88
17. 电话号码的字母组合
99
20. 有效的括号
1010
21. 合并两个有序链表
11+
37. 解数独
12+
39. 组合总和
13+
40. 组合总和 II
1114
46. 全排列
15+
47. 全排列 II
16+
51. N 皇后
1217
53. 最大子数组和
1318
70. 爬楼梯
19+
77. 组合
20+
78. 子集
21+
90. 子集 II
22+
93. 复原 IP 地址
1423
94. 二叉树的中序遍历
1524
101. 对称二叉树
1625
102. 二叉树的层序遍历
1726
104. 二叉树的最大深度
1827
105. 从前序与中序遍历序列构造二叉树
1928
114. 二叉树展开为链表
2029
121. 买卖股票的最佳时机
30+
131. 分割回文串
2131
136. 只出现一次的数字
2232
141. 环形链表
2333
144. 二叉树的前序遍历
@@ -27,6 +37,7 @@
2737
169. 多数元素
2838
200. 岛屿数量
2939
206. 反转链表
40+
216. 组合总和 III
3041
226. 翻转二叉树
3142
234. 回文链表
3243
236. 二叉树的最近公共祖先
@@ -39,6 +50,8 @@
3950
437. 路径总和
4051
448. 找到所有数组中消失的数字
4152
461. 汉明距离
53+
491. 递增子序列
54+
494. 目标和
4255
538. 把二叉搜索树转换为累加树
4356
543. 二叉树的直径
4457
560. 和为 K 的子数组

‎leetcode_Java/Solution0017.java

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,13 @@
11
// 电话号码的字母组合
22

33
/*
4-
回溯
4+
回溯：
5+
1、使用HashMap定义数字和字符串的对应关系。每个数字代表不同的集合，即求不同集合的子集
6+
2、定义全局变量res存放所有子结果，sb存放临时子结果
7+
3、调用递归函数，处理得到所有子结果，返回结果
8+
4、定义递归函数：
9+
1）终止条件，存储子结果
10+
2）for循环遍历数字对应的字符串，选择 → 递归 → 撤销，回溯
511
*/
612
class Solution {
713
private Map<Character, String> map = new HashMap<Character, String>(){{

‎leetcode_Java/Solution0037.java

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
// 解数独
2+
3+
4+
/*
5+
回溯：
6+
1、本题中棋盘的每一个位置都要放一个数字，并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
7+
2、为什么递归函数的返回值需要是bool类型？
8+
因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值
9+
3、本题在原二维数组上操作，因此不需要增加额外的数据结构
10+
4、本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回
11+
5、本题需要 二维递归，也就是两个for循环嵌套着递归
12+
一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！
13+
*/
14+
class Solution {
15+
public void solveSudoku(char[][] board) {
16+
backtrack(board);
17+
}
18+
19+
private boolean backtrack(char[][] board) {
20+
for (int row = 0; row < 9; row++) {
21+
for (int col = 0; col < 9; col++) {
22+
if (board[row][col] != '.') {
23+
continue;
24+
}
25+
for (char val = '1'; val <= '9'; val++) {
26+
if (isValid(row, col, val, board)) {
27+
board[row][col] = val;
28+
if (backtrack(board)) {
29+
return true;
30+
}
31+
board[row][col] = '.';
32+
}
33+
}
34+
// 9个数都试完了，都不行，那么就返回false
35+
return false;
36+
}
37+
}
38+
// 遍历完没有返回false，说明找到了合适棋盘位置
39+
return true;
40+
}
41+
42+
private boolean isValid(int row, int col, char val, char[][] board) {
43+
// 判断同一行是否有重复的数
44+
for (int i = 0; i < 9; i++) {
45+
if (board[row][i] == val) {
46+
return false;
47+
}
48+
}
49+
// 判断同一列是否有重复的数
50+
for (int j = 0; j < 9; j++) {
51+
if (board[j][col] == val) {
52+
return false;
53+
}
54+
}
55+
// 判断九宫格是否有重复的数
56+
int startRow = (row / 3) * 3;
57+
int startCol = (col / 3) * 3;
58+
for (int i = startRow; i < startRow + 3; i++) {
59+
for (int j = startCol; j < startCol + 3; j++) {
60+
if (board[i][j] == val) {
61+
return false;
62+
}
63+
}
64+
}
65+
return true;
66+
}
67+
}

‎leetcode_Java/Solution0039.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
// 组合总和
2+
3+
4+
/*
5+
回溯：
6+
1、定义全局变量res存放回溯过程得到的所有子结果
7+
2、定义全局变量track存放回溯过程的临时子结果
8+
3、调用递归函数，处理得到所有子结果，返回结果
9+
4、定义递归函数
10+
1）终止条件，总和等于目标值，存储子结果
11+
2）剪枝条件，总和大于目标值，结束
12+
3）for循环遍历数组，做选择 → 递归 → 撤销选择，回溯
13+
*/
14+
class Solution {
15+
private List<List<Integer>> res = new ArrayList<>();
16+
private Deque<Integer> track = new LinkedList<>();
17+
18+
public List<List<Integer>> combinationSum(int[] candidates, int target) {
19+
backtrack(candidates, 0, target);
20+
return res;
21+
}
22+
23+
private void backtrack(int[] candidates, int index, int target) {
24+
int sum = track.stream().mapToInt(x -> x).sum();
25+
if (sum == target) {
26+
res.add(new ArrayList<>(track));
27+
return;
28+
}
29+
if (sum > target) {
30+
return;
31+
}
32+
for (int i = index; i < candidates.length; i++) {
33+
track.addLast(candidates[i]);
34+
backtrack(candidates, i, target);
35+
track.removeLast();
36+
}
37+
}
38+
}

‎leetcode_Java/Solution0040.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
// 组合总和 II
2+
3+
4+
/*
5+
回溯：
6+
1、思路与'39.组合总和'相同
7+
2、不同点：有重复元素，解集不能包含重复的组合，因此要过滤重复的选择
8+
3、增加剪枝条件：先数组排序，同一层元素做选择时，如果该元素前面出现过，则跳过，因为前面的选择已经包含当前情况了
9+
*/
10+
class Solution {
11+
private List<List<Integer>> res = new ArrayList<>();
12+
private Deque<Integer> track = new LinkedList<>();
13+
14+
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
15+
Arrays.sort(candidates);
16+
backtrack(candidates, 0, target);
17+
return res;
18+
}
19+
20+
private void backtrack(int[] candidates, int startIndex, int target) {
21+
int sum = track.stream().mapToInt(x -> x).sum();
22+
if (sum == target) {
23+
res.add(new ArrayList<>(track));
24+
return;
25+
}
26+
if (sum > target) {
27+
return;
28+
}
29+
for (int i = startIndex; i < candidates.length; i++) {
30+
if (i > startIndex && candidates[i] == candidates[i - 1]) {
31+
continue;
32+
}
33+
track.addLast(candidates[i]);
34+
backtrack(candidates, i + 1, target);
35+
track.removeLast();
36+
}
37+
}
38+
}

‎leetcode_Java/Solution0046.java

Lines changed: 33 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,11 +4,42 @@
44
/*
55
回溯：
66
1、定义全局变量res存放回溯过程得到的所有子结果
7-
2、定义局部变量track存放回溯过程的临时子结果
7+
2、定义全局变量track存放回溯过程的临时子结果
88
3、调用递归函数，处理得到所有子结果，返回结果
99
4、定义递归函数
1010
1）终止条件，存储子结果
11-
2）for循环：剪枝条件 → 做选择 → 递归 → 撤销选择 → 回溯
11+
2）for循环：剪枝条件 → 做选择 → 递归 → 撤销选择，回溯
12+
5、由于存储子结果的变量在遍历过程中作为临时存储，当需要添加子结果时拷贝一份即可，因此可以重复使用
13+
*/
14+
class Solution {
15+
private List<List<Integer>> res = new ArrayList<>();
16+
private LinkedList<Integer> track = new LinkedList<>();
17+
18+
public List<List<Integer>> permute(int[] nums) {
19+
backtrack(nums);
20+
return res;
21+
}
22+
23+
private void backtrack(int[] nums) {
24+
if (track.size() == nums.length) {
25+
res.add(new ArrayList(track));
26+
return;
27+
}
28+
for (int i = 0; i < nums.length; i++) {
29+
if (track.contains(nums[i])) {
30+
continue;
31+
}
32+
track.addLast(nums[i]);
33+
backtrack(nums);
34+
track.removeLast();
35+
}
36+
}
37+
}
38+
39+
40+
41+
/*
42+
逻辑同上
1243
*/
1344
class Solution {
1445
private List<List<Integer>> res = new ArrayList<>();

‎leetcode_Java/Solution0047.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
// 全排列 II
2+
3+
4+
/*
5+
回溯：
6+
1、定义全局变量res存放回溯过程得到的所有子结果，定义全局变量track存放回溯过程的临时子结果，定义全局便变量used存放数组元素使用过情况
7+
2、包含重复的元素，因此做选择时，树层要去重，树枝不用去重。去重必须先数组排序
8+
3、调用递归函数，处理得到所有子结果，返回结果
9+
4、定义递归函数
10+
1）终止条件，子结果大小满足条件，存储子结果
11+
2）for循环遍历数组：剪枝条件 → 做选择 → 递归 → 撤销选择，回溯
12+
① 剪枝条件：当前元素使用过则跳过；或者当前元素未使用过，但同一层前面有同样的元素未使用过，该元素在本层可以使用，则需要跳过重复选择
13+
② 做选择：元素只加入子结果，标记当前元素已使用
14+
③ 递归：进入下一层，同样遍历整个数组，通过used标记判断元素是否有效可用
15+
④ 回溯：撤销选择，移除子结果最后一个元素，标记当前元素未使用
16+
*/
17+
class Solution {
18+
private List<List<Integer>> res = new ArrayList<>();
19+
private Deque<Integer> track = new LinkedList<>();
20+
private boolean[] used;
21+
22+
public List<List<Integer>> permuteUnique(int[] nums) {
23+
used = new boolean[nums.length];
24+
Arrays.sort(nums);
25+
backtrack(nums);
26+
return res;
27+
}
28+
29+
private void backtrack(int[] nums) {
30+
if (track.size() == nums.length) {
31+
res.add(new ArrayList<>(track));
32+
return;
33+
}
34+
for (int i = 0; i < nums.length; i++) {
35+
if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) {
36+
continue;
37+
}
38+
track.addLast(nums[i]);
39+
used[i] = true;
40+
backtrack(nums);
41+
track.removeLast();
42+
used[i] = false;
43+
}
44+
}
45+
}

0 commit comments

Comments
 (0)