本节内容
今天这三道题都非常难，那么这么难的题，为啥一天做三道？
因为 一刷 也不求大家能把这么难的问题解决，所以 大家一刷的时候，就了解一下题目的要求，了解一下解题思路，不求能直接写出代码，先大概熟悉一下这些题，二刷的时候，随着对回溯算法的深入理解，再去解决如下三题。
大家今天的任务，其实是 对回溯算法章节做一个总结就行。
重点是看 回溯算法总结篇：
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html
332.重新安排行程※
建议：
题目链接： https://leetcode.cn/problems/reconstruct-itinerary/
文章讲解： https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html
视频讲解：
题目分析
方案一
好不夸张的讲，此题我花费了超过3个小时，尝试了多种方案，多次时间超时，最终此方案成功AC。
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
73
74
75
76
77
78
79
80
81
82
83
| class Solution {
private List<String> temp = new ArrayList<>();
private List<List<String>> resultTemp = new ArrayList<>();
private int[] used;
public List<String> findItinerary(List<List<String>> tickets) {
used = new int[tickets.size()];
temp.add("JFK");
HashMap<String, PriorityQueue<String>> ticketsMap = new HashMap<>();
PriorityQueue<String> queue;
for (List<String> ticket : tickets) {
if (ticketsMap.containsKey(ticket.get(0))) {
queue = ticketsMap.get(ticket.get(0));
} else {
queue = new PriorityQueue<String>((o1, o2) -> o1.compareTo(o2));
}
queue.add(ticket.get(1));
ticketsMap.put(ticket.get(0), queue);
}
backtracking(ticketsMap, 0, tickets.size());
return resultTemp.get(0);
}
private void backtracking(HashMap<String, PriorityQueue<String>> ticketsMap, int size, int length) {
if (length == size) {
resultTemp.add(new ArrayList<>(temp));
return;
}
PriorityQueue<String> queue = ticketsMap.get(temp.get(temp.size() - 1));
int index = 0;
while (queue != null && !queue.isEmpty() && resultTemp.isEmpty() && index < queue.size()) {
String poll = findIndexOfQueue(queue, index);
temp.add(poll);
backtracking(ticketsMap, size + 1, length);
temp.remove(temp.size() - 1);
queue.add(poll);
index++;
}
}
private String findIndexOfQueue(PriorityQueue<String> queue, int index) {
String[] list = new String[index + 1];
for (int i = 0; i <= index; i++) {
list[i] = queue.poll();
}
for (int i = 0; i < index; i++) {
queue.add(list[i]);
}
return list[index];
}
}
|
结果
解答成功:
执行耗时:10 ms,击败了67.60% 的Java用户
内存消耗:43.1 MB,击败了60.07% 的Java用户
代码随想录
https://programmercarl.com/0332.%E9%87%8D%E6%96%B0%E5%AE%89%E6%8E%92%E8%A1%8C%E7%A8%8B.html
思路
直觉上来看 这道题和回溯法没有什么关系，更像是图论中的深度优先搜索。
实际上确实是深搜，但这是深搜中使用了回溯的例子，在查找路径的时候，如果不回溯，怎么能查到目标路径呢。
所以倾向于说本题应该使用回溯法，那么我也用回溯法的思路来讲解本题，其实深搜一般都使用了回溯法的思路，在图论系列中我会再详细讲解深搜。
这里就是先给大家拓展一下，原来回溯法还可以这么玩！
这道题目有几个难点：
- 一个行程中，如果航班处理不好容易变成一个圈，成为死循环
- 有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
- 使用回溯法（也可以说深搜） 的话，那么终止条件是什么呢？
- 搜索的过程中，如何遍历一个机场所对应的所有机场。
如何理解死循环
对于死循环，我来举一个有重复机场的例子：
为什么要举这个例子呢，就是告诉大家，出发机场和到达机场也会重复的，如果在解题的过程中没有对集合元素处理好，就会死循环。
该记录映射关系
有多种解法，字母序靠前排在前面，让很多同学望而退步，如何该记录映射关系呢 ？
一个机场映射多个机场，机场之间要靠字母序排列，一个机场映射多个机场，可以使用std::unordered_map，如果让多个机场之间再有顺序的话，就是用std::map 或者std::multimap 或者 std::multiset。
这样存放映射关系可以定义为 unordered_map<string, multiset<string>> targets 或者 unordered_map<string, map<string, int>> targets。
含义如下：
unordered_map<string, multiset> targets：unordered_map<出发机场, 到达机场的集合> targets
unordered_map<string, map<string, int>> targets：unordered_map<出发机场, map<到达机场, 航班次数>> targets
这两个结构，我选择了后者，因为如果使用unordered_map<string, multiset<string>> targets 遍历multiset的时候，不能删除元素，一旦删除元素，迭代器就失效了。
再说一下为什么一定要增删元素呢，正如开篇我给出的图中所示，出发机场和到达机场是会重复的，搜索的过程没及时删除目的机场就会死循环。
所以搜索的过程中就是要不断的删multiset里的元素，那么推荐使用unordered_map<string, map<string, int>> targets。
在遍历 unordered_map<出发机场, map<到达机场, 航班次数>> targets的过程中，可以使用”航班次数”这个字段的数字做相应的增减，来标记到达机场是否使用过了。
如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。
相当于说我不删，我就做一个标记！
回溯法
这道题目我使用回溯法，那么下面按照我总结的回溯模板来：
1
2
3
4
5
6
7
8
9
10
11
12
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果
}
}
|
本题以输入：[[“JFK”, “KUL”], [“JFK”, “NRT”], [“NRT”, “JFK”]为例，抽象为树形结构如下：
开始回溯三部曲讲解：
在讲解映射关系的时候，已经讲过了，使用unordered_map<string, map<string, int>> targets; 来记录航班的映射关系，我定义为全局变量。
当然把参数放进函数里传进去也是可以的，我是尽量控制函数里参数的长度。
参数里还需要ticketNum，表示有多少个航班（终止条件会用上）。
代码如下：
1
2
3
|
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
|
注意函数返回值我用的是bool！
我们之前讲解回溯算法的时候，一般函数返回值都是void，这次为什么是bool呢？
因为我们只需要找到一个行程，就是在树形结构中唯一的一条通向叶子节点的路线，如图：
所以找到了这个叶子节点了直接返回。
当然本题的targets和result都需要初始化，代码如下：
1
2
3
4
| for (const vector<string>& vec : tickets) {
targets[vec[0]][vec[1]]++;
}
result.push_back("JFK");
|
拿题目中的示例为例，输入: [[“MUC”, “LHR”], [“JFK”, “MUC”], [“SFO”, “SJC”], [“LHR”, “SFO”]] ，这是有4个航班，那么只要找出一种行程，行程里的机场个数是5就可以了。
所以终止条件是：我们回溯遍历的过程中，遇到的机场个数，如果达到了（航班数量+1），那么我们就找到了一个行程，把所有航班串在一起了。
代码如下：
1
2
3
| if (result.size() == ticketNum + 1) {
return true;
}
|
本题的result就是记录路径的（就一条），在如下单层搜索的逻辑中result就添加元素了。
回溯的过程中，如何遍历一个机场所对应的所有机场呢？
这里刚刚说过，在选择映射函数的时候，不能选择unordered_map<string, multiset<string>> targets， 因为一旦有元素增删multiset的迭代器就会失效，当然可能有牛逼的容器删除元素迭代器不会失效，这里就不在讨论了。
可以说本题既要找到一个对数据进行排序的容器，而且还要容易增删元素，迭代器还不能失效。
所以我选择了unordered_map<string, map<string, int>> targets 来做机场之间的映射。
遍历过程如下：
1
2
3
4
5
6
7
8
9
| for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
if (target.second > 0 ) {
result.push_back(target.first);
target.second--;
if (backtracking(ticketNum, result)) return true;
result.pop_back();
target.second++;
}
}
|
可以看出 通过unordered_map<string, map<string, int>> targets里的int字段来判断 这个集合里的机场是否使用过，这样避免了直接去删元素。
分析完毕，此时完整C++代码如下：
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
| class Solution {
private:
unordered_map<string, map<string, int>> targets;
bool backtracking(int ticketNum, vector<string>& result) {
if (result.size() == ticketNum + 1) {
return true;
}
for (pair<const string, int>& target : targets[result[result.size() - 1]]) {
if (target.second > 0 ) {
result.push_back(target.first);
target.second--;
if (backtracking(ticketNum, result)) return true;
result.pop_back();
target.second++;
}
}
return false;
}
public:
vector<string> findItinerary(vector<vector<string>>& tickets) {
targets.clear();
vector<string> result;
for (const vector<string>& vec : tickets) {
targets[vec[0]][vec[1]]++;
}
result.push_back("JFK");
backtracking(tickets.size(), result);
return result;
}
};
|
一波分析之后，可以看出我就是按照回溯算法的模板来的。
代码中
1
| for (pair<const string, int>& target : targets[result[result.size() - 1]])
|
pair里要有const，因为map中的key是不可修改的，所以是pair<const string, int>。
如果不加const，也可以复制一份pair，例如这么写：
1
| for (pair<string, int>target : targets[result[result.size() - 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
| class Solution {
private LinkedList<String> res;
private LinkedList<String> path = new LinkedList<>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
path.add("JFK");
boolean[] used = new boolean[tickets.size()];
backTracking((ArrayList) tickets, used);
return res;
}
public boolean backTracking(ArrayList<List<String>> tickets, boolean[] used) {
if (path.size() == tickets.size() + 1) {
res = new LinkedList(path);
return true;
}
for (int i = 0; i < tickets.size(); i++) {
if (!used[i] && tickets.get(i).get(0).equals(path.getLast())) {
path.add(tickets.get(i).get(1));
used[i] = true;
if (backTracking(tickets, used)) {
return true;
}
used[i] = false;
path.removeLast();
}
}
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
36
37
38
39
40
41
42
43
44
| class Solution {
private Deque<String> res;
private Map<String, Map<String, Integer>> map;
private boolean backTracking(int ticketNum){
if(res.size() == ticketNum + 1){
return true;
}
String last = res.getLast();
if(map.containsKey(last)){
for(Map.Entry<String, Integer> target : map.get(last).entrySet()){
int count = target.getValue();
if(count > 0){
res.add(target.getKey());
target.setValue(count - 1);
if(backTracking(ticketNum)) return true;
res.removeLast();
target.setValue(count);
}
}
}
return false;
}
public List<String> findItinerary(List<List<String>> tickets) {
map = new HashMap<String, Map<String, Integer>>();
res = new LinkedList<>();
for(List<String> t : tickets){
Map<String, Integer> temp;
if(map.containsKey(t.get(0))){
temp = map.get(t.get(0));
temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);
}else{
temp = new TreeMap<>();
temp.put(t.get(1), 1);
}
map.put(t.get(0), temp);
}
res.add("JFK");
backTracking(tickets.size());
return new ArrayList<>(res);
}
}
|
51. N皇后※
建议：
题目链接： https://leetcode.cn/problems/n-queens/
文章讲解： https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html
视频讲解： https://www.bilibili.com/video/BV1Rd4y1c7Bq
题目分析
方案一
苍天呐，不容易，大概一个小时解决。
重点是要想好如何解决 同一行或同一列或同一斜线
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
73
74
75
76
77
78
| class Solution {
private String[] strings;
private List<List<String>> result = new ArrayList<>();
private int[] path;
public List<List<String>> solveNQueens(int n) {
strings = new String[n];
StringBuilder stringBuilder = new StringBuilder();
for (int i = 0; i < n; i++) {
stringBuilder = new StringBuilder();
for (int j = 0; j < i; j++) {
stringBuilder.append('.');
}
stringBuilder.append('Q');
for (int j = i + 1; j < n; j++) {
stringBuilder.append('.');
}
strings[i] = stringBuilder.toString();
}
path = new int[n];
backtracking(1, n);
return result;
}
private void backtracking(int row, int n) {
if (row == n + 1) {
List<String> temp = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
temp.add("");
}
for (int i = 0; i < path.length; i++) {
temp.set(path[i] - 1, strings[i]);
}
result.add(temp);
return;
}
for (int i = 0; i < n; i++) {
if (path[i] == 0 && isAvailable(row, i)) {
path[i] = row;
backtracking(row + 1, n);
path[i] = 0;
}
}
}
private boolean isAvailable(int row, int col) {
for (int i = 0; i < path.length; i++) {
if (path[i] != 0 && Math.abs(row - path[i]) == Math.abs(col - i)) {
return false;
}
}
return true;
}
}
|
结果
解答成功:
执行耗时:2 ms,击败了91.68% 的Java用户
内存消耗:42.4 MB,击败了72.86% 的Java用户
分析
时间复杂度：
O( n! )
空间复杂度：
O( n )
代码随想录
https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html
思路
都知道n皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列问题之后，遇到这种二维矩阵还会有点不知所措。
首先来看一下皇后们的约束条件：
- 不能同行
- 不能同列
- 不能同斜线
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
下面我用一个 3 * 3 的棋盘，将搜索过程抽象为一棵树，如图：
从图中，可以看出，二维矩阵中矩阵的高就是这棵树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
那么我们用皇后们的约束条件，来回溯搜索这棵树，只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。
回溯三部曲
按照我总结的如下回溯模板，我们来依次分析：
1
2
3
4
5
6
7
8
9
10
11
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果
}
}
|
我依然是定义全局变量二维数组result来记录最终结果。
参数n是棋盘的大小，然后用row来记录当前遍历到棋盘的第几层了。
代码如下：
1
2
| vector<vector<string>> result;
void backtracking(int n, int row, vector<string>& chessboard) {
|
在如下树形结构中：
可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。
代码如下：
1
2
3
4
| if (row == n) {
result.push_back(chessboard);
return;
}
|
递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
每次都是要从新的一行的起始位置开始搜，所以都是从0开始。
代码如下：
1
2
3
4
5
6
7
| for (int col = 0; col < n; col++) {
if (isValid(row, col, chessboard, n)) {
chessboard[row][col] = 'Q';
backtracking(n, row + 1, chessboard);
chessboard[row][col] = '.';
}
}
|
按照如下标准去重：
- 不能同行
- 不能同列
- 不能同斜线 （45度和135度角）
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| bool isValid(int row, int col, vector<string>& chessboard, int n) {
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;
}
|
在这份代码中，细心的同学可以发现为什么没有在同行进行检查呢？
因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。
那么按照这个模板不难写出如下C++代码：
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
| class Solution {
private:
vector<vector<string>> result;
void backtracking(int n, int row, vector<string>& chessboard) {
if (row == n) {
result.push_back(chessboard);
return;
}
for (int col = 0; col < n; col++) {
if (isValid(row, col, chessboard, n)) {
chessboard[row][col] = 'Q';
backtracking(n, row + 1, chessboard);
chessboard[row][col] = '.';
}
}
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
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;
}
public:
vector<vector<string>> solveNQueens(int n) {
result.clear();
std::vector<std::string> chessboard(n, std::string(n, '.'));
backtracking(n, 0, chessboard);
return result;
}
};
|
可以看出，除了验证棋盘合法性的代码，省下来部分就是按照回溯法模板来的。
本题是我们解决棋盘问题的第一道题目。
如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手，可能知道要用回溯法，但也不知道该怎么去搜。
这里明确给出了棋盘的宽度就是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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| class Solution {
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char[][] chessboard = new char[n][n];
for (char[] c : chessboard) {
Arrays.fill(c, '.');
}
backTrack(n, 0, chessboard);
return res;
}
public void backTrack(int n, int row, char[][] chessboard) {
if (row == n) {
res.add(Array2List(chessboard));
return;
}
for (int col = 0;col < n; ++col) {
if (isValid (row, col, n, chessboard)) {
chessboard[row][col] = 'Q';
backTrack(n, row+1, chessboard);
chessboard[row][col] = '.';
}
}
}
public List Array2List(char[][] chessboard) {
List<String> list = new ArrayList<>();
for (char[] c : chessboard) {
list.add(String.copyValueOf(c));
}
return list;
}
public boolean isValid(int row, int col, int n, char[][] chessboard) {
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-1; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
}
|
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
|
class Solution {
List<List<String>> res = new ArrayList<>();
boolean[] usedCol, usedDiag45, usedDiag135;
public List<List<String>> solveNQueens(int n) {
usedCol = new boolean[n];
usedDiag45 = new boolean[2 * n - 1];
usedDiag135 = new boolean[2 * n - 1];
int[] board = new int[n];
backTracking(board, n, 0);
return res;
}
private void backTracking(int[] board, int n, int row) {
if (row == n) {
List<String> temp = new ArrayList<>();
for (int i : board) {
char[] str = new char[n];
Arrays.fill(str, '.');
str[i] = 'Q';
temp.add(new String(str));
}
res.add(temp);
return;
}
for (int col = 0; col < n; col++) {
if (usedCol[col] | usedDiag45[row + col] | usedDiag135[row - col + n - 1]) {
continue;
}
board[row] = col;
usedCol[col] = true;
usedDiag45[row + col] = true;
usedDiag135[row - col + n - 1] = true;
backTracking(board, n, row + 1);
usedCol[col] = false;
usedDiag45[row + col] = false;
usedDiag135[row - col + n - 1] = false;
}
}
}
|
37. 解数独※
建议：
题目链接： https://leetcode.cn/problems/sudoku-solver/
文章讲解： https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html
视频讲解： https://www.bilibili.com/video/BV1TW4y1471V
题目分析
示例 1：
方案一
此方案可以优化以下，像上题的题解一样，用哈希数组，判断数据是否在哈希数组中，需要维护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
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
| class Solution {
private boolean flag = true;
public void solveSudoku(char[][] board) {
backtracking(0, 0, board);
}
private void backtracking(int row, int col, char[][] board) {
if (row == 9) {
flag = false;
return;
}
if (board[row][col] != '.') {
if (col == 8) {
backtracking(row + 1, 0, board);
} else {
backtracking(row, col + 1, board);
}
} else {
for (int i = 0; i < 9; i++) {
if (isAvailable(row, col, (char) ('1' + i), board)){
board[row][col] = (char) ('1' + i);
if (col == 8) {
backtracking(row + 1, 0, board);
} else {
backtracking(row, col + 1, board);
}
if (flag)
board[row][col] = '.';
}
}
}
}
private boolean isAvailable(int row, int col, char ch,char[][] board) {
for (int i = 0; i < 9; i++) {
if (ch == board[i][col]) return false;
}
for (int i = 0; i < 9; i++) {
if (ch == board[row][i]) return false;
}
int rowLeave = row / 3;
int colLeave = col / 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (ch == board[3 * rowLeave + i][3 * colLeave + j]) return false;
}
}
return true;
}
}
|
结果
解答成功:
执行耗时:7 ms,击败了31.57% 的Java用户
内存消耗:39.1 MB,击败了22.10% 的Java用户
分析
时间复杂度：
O( n! ) n为数组中没有填写的空格个数
空间复杂度：
O( n )
代码随想录
https://programmercarl.com/0037.%E8%A7%A3%E6%95%B0%E7%8B%AC.html
思路
棋盘搜索问题可以使用回溯法暴力搜索，只不过这次我们要做的是二维递归。
怎么做二维递归呢？
N皇后问题 是因为每一行每一列只放一个皇后，只需要一层for循环遍历一行，递归来遍历列，然后一行一列确定皇后的唯一位置。
本题就不一样了，本题中棋盘的每一个位置都要放一个数字（而N皇后是一行只放一个皇后），并检查数字是否合法，解数独的树形结构要比N皇后更宽更深。
因为这个树形结构太大了，我抽取一部分，如图所示：
回溯三部曲
递归函数的返回值需要是bool类型，为什么呢？
因为解数独找到一个符合的条件（就在树的叶子节点上）立刻就返回，相当于找从根节点到叶子节点一条唯一路径，所以需要使用bool返回值。
代码如下：
1
| bool backtracking(vector<vector<char>>& board)
|
本题递归不用终止条件，解数独是要遍历整个树形结构寻找可能的叶子节点就立刻返回。
不用终止条件会不会死循环？
递归的下一层的棋盘一定比上一层的棋盘多一个数，等数填满了棋盘自然就终止（填满当然好了，说明找到结果了），所以不需要终止条件！
那么有没有永远填不满的情况呢？
这个问题我在递归单层搜索逻辑里再来讲！
在树形图中可以看出我们需要的是一个二维的递归（也就是两个for循环嵌套着递归）
一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！
代码如下：（详细看注释）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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] != '.') continue;
for (char k = '1'; k <= '9'; k++) {
if (isValid(i, j, k, board)) {
board[i][j] = k;
if (backtracking(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
|
注意这里return false的地方，这里放return false 是有讲究的。
因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
那么会直接返回， 这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！
判断棋盘是否合法
判断棋盘是否合法有如下三个维度：
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| bool isValid(int row, int col, char val, vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == val) {
return false;
}
}
for (int j = 0; j < 9; j++) {
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
|
最后整体C++代码如下：
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
| class Solution {
private:
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;
if (backtracking(board)) return true;
board[i][j] = '.';
}
}
return false;
}
}
}
return true;
}
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
for (int i = 0; i < 9; i++) {
if (board[row][i] == val) {
return false;
}
}
for (int j = 0; j < 9; j++) {
if (board[j][col] == val) {
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] == val ) {
return false;
}
}
}
return true;
}
public:
void solveSudoku(vector<vector<char>>& board) {
backtracking(board);
}
};
|
解数独可以说是非常难的题目了，如果还一直停留在单层递归的逻辑中，这道题目可以让大家瞬间崩溃。
一波分析之后，再看代码会发现其实也不难，唯一难点就是理解二维递归的思维逻辑。
代码实现
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
| class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHelper(board);
}
private boolean solveSudokuHelper(char[][] board){
for (int i = 0; i < 9; i++){
for (int j = 0; j < 9; j++){
if (board[i][j] != '.'){
continue;
}
for (char k = '1'; k <= '9'; k++){
if (isValidSudoku(i, j, k, board)){
board[i][j] = k;
if (solveSudokuHelper(board)){
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
private boolean isValidSudoku(int row, int col, char val, char[][] board){
for (int i = 0; i < 9; i++){
if (board[row][i] == val){
return false;
}
}
for (int j = 0; j < 9; j++){
if (board[j][col] == val){
return false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++){
for (int j = startCol; j < startCol + 3; j++){
if (board[i][j] == val){
return false;
}
}
}
return true;
}
}
|
回溯总结※
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html
回溯法理论基础
回溯是递归的副产品，只要有递归就会有回溯，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。
回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。
回溯算法能解决如下问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 棋盘问题：N皇后，解数独等等
回溯法的模板：
1
2
3
4
5
6
7
8
9
10
11
12
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果
}
}
|
这个模板会伴随整个回溯法系列！
组合问题
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html#%E7%BB%84%E5%90%88%E9%97%AE%E9%A2%98
在文中开始的时候给大家列举k层for循环例子，进而得出都是同样是暴力解法，为什么要用回溯法！
此时大家应该深有体会回溯法的魅力，用递归控制for循环嵌套的数量！
本题把回溯问题抽象为树形结构，如题：
可以直观的看出其搜索的过程：for循环横向遍历，递归纵向遍历，回溯不断调整结果集，这个理念贯穿整个回溯法系列，也是我做了很多回溯的题目，不断摸索其规律才总结出来的。
优化回溯算法只有剪枝一种方法，把回溯法代码做了剪枝优化，树形结构如图：
剪枝精髓是：for循环在寻找起点的时候要有一个范围，如果这个起点到集合终止之间的元素已经不够题目要求的k个元素了，就没有必要搜索了。
在for循环上做剪枝操作是回溯法剪枝的常见套路！
切割问题
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html#%E5%88%87%E5%89%B2%E9%97%AE%E9%A2%98
难点：
- 切割问题其实类似组合问题
- 如何模拟那些切割线
- 切割问题中递归如何终止
- 在递归循环中如何截取子串
- 如何判断回文
如果想到了用求解组合问题的思路来解决 切割问题本题就成功一大半了，接下来就可以对着模板照葫芦画瓢。
但后序如何模拟切割线，如何终止，如何截取子串，其实都不好想，最后判断回文算是最简单的了。
所以本题应该是一个道hard题目了。
除了这些难点，本题还有细节，例如：切割过的地方不能重复切割所以递归函数需要传入i + 1。
树形结构如下：
子集问题
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html#%E5%AD%90%E9%9B%86%E9%97%AE%E9%A2%98
排列问题
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html#%E6%8E%92%E5%88%97%E9%97%AE%E9%A2%98
去重问题
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html#%E5%8E%BB%E9%87%8D%E9%97%AE%E9%A2%98
可以使用used数组来去重的，使用set也可以用来去重！
使用set去重的版本相对于used数组的版本效率都要低很多
棋盘问题
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html#%E6%A3%8B%E7%9B%98%E9%97%AE%E9%A2%98
性能分析
https://programmercarl.com/%E5%9B%9E%E6%BA%AF%E6%80%BB%E7%BB%93.html#%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90
以下在计算空间复杂度的时候都把系统栈（不是数据结构里的栈）所占空间算进去。
子集问题分析：
- 时间复杂度：O(2^n)，因为每一个元素的状态无外乎取与不取，所以时间复杂度为O(2^n)
- 空间复杂度：O(n)，递归深度为n，所以系统栈所用空间为O(n)，每一层递归所用的空间都是常数级别，注意代码里的result和path都是全局变量，就算是放在参数里，传的也是引用，并不会新申请内存空间，最终空间复杂度为O(n)
排列问题分析：
- 时间复杂度：O(n!)，这个可以从排列的树形图中很明显发现，每一层节点为n，第二层每一个分支都延伸了n-1个分支，再往下又是n-2个分支，所以一直到叶子节点一共就是 n * n-1 * n-2 * ….. 1 = n!。
- 空间复杂度：O(n)，和子集问题同理。
组合问题分析：
- 时间复杂度：O(2^n)，组合问题其实就是一种子集的问题，所以组合问题最坏的情况，也不会超过子集问题的时间复杂度。
- 空间复杂度：O(n)，和子集问题同理。
N皇后问题分析：
- 时间复杂度：O(n!) ，其实如果看树形图的话，直觉上是O(n^n)，但皇后之间不能见面所以在搜索的过程中是有剪枝的，最差也就是O（n!），n!表示n * (n-1) * …. * 1。
- 空间复杂度：O(n)，和子集问题同理。
解数独问题分析：
- 时间复杂度：O(9^m) , m是’.’的数目。
- 空间复杂度：O(n^2)，递归的深度是n^2
一般说道回溯算法的复杂度，都说是指数级别的时间复杂度
