算法训练营（day30）
回溯算法模板
1
2
3
4
5
6
7
8
9
10
11
12
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果
}
}
|
332. 重新安排行程
题目链接：https://leetcode.cn/problems/reconstruct-itinerary/description/
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
- 例如，行程
["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
解题思路
解题过程：回溯
- 定义终止条件：当
path 内元素等于 tickets.size() + 1 时，终止
- 避免路径重复使用，定义
used
- 定义循环条件
- 横向：从
0 遍历到 tickets.size()
- 纵向：
- 判断当前路径是否被使用
path 的终点是否等于 该路径的起点 tickets.get(i).get(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
| class Solution {
LinkedList<String> result;
LinkedList<String> path = new LinkedList<>();
boolean[] used;
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets, (a, b) -> a.get(1).compareTo(b.get(1)));
used = new boolean[tickets.size()];
path.add("JFK");
backTrack((ArrayList) tickets, used);
return result;
}
public boolean backTrack(ArrayList<List<String>> tickets, boolean[] used){
if(path.size() == tickets.size() + 1){
result = 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(backTrack(tickets, used)){
return true;
}
used[i] = false;
path.removeLast();
}
}
return false;
}
}
|
51. N 皇后
题目链接：https://leetcode.cn/problems/n-queens/description/
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
解题思路
解题过程：
定义终止条件：当到达棋盘最底行时，终止
定义合法条件：
- 棋盘每一列 只能 有一个皇后
- 45°方位 只能 有一个皇后
- 135°方位 只能 有一个皇后
设计降维方法：将棋盘二维数组转化为一维集合
定义循环条件
横向：从 0 遍历到棋盘的最底层 row
纵向：遍历棋盘的列 col
回溯：回滚 chessBoard[row][col]
详细代码
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
| class Solution {
List<List<String>> result = 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 result;
}
public void backTrack(int n, int row, char[][] chessBoard){
if(row == n){
result.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;
}
}
|
37. 解数独
题目链接：https://leetcode.cn/problems/sudoku-solver/description/
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
- 数字
1-9 在每一行只能出现一次。
- 数字
1-9 在每一列只能出现一次。
- 数字
1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
解题思路
解题过程：
定义合法条件：
- 数独每一行数字不能相同
- 数独每一列数字不能相同
- 每个九宫格内数字不能相同
定义循环条件
横向：从 0 遍历到数组的最底层 row
纵向：遍历棋盘的列 col
跳过数独原有数字，给 空 位置进行赋值回溯
如果合法则输出，不合法则回溯
回溯：回滚 board[row][col]
详细代码
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
| class Solution {
public void solveSudoku(char[][] board) {
backTrack(board);
}
public boolean isValid(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;
}
public boolean backTrack(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(isValid(i, j, k, board)){
board[i][j] = k;
if(backTrack(board)){
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
}
|
