回溯章节总结
回溯是一种暴力搜索算法，适合解决的问题有：
- 组合问题
- 切割问题
- 子集问题
- 排列问题
- 棋盘问题
回溯可以抽象为一棵树形结构，横向为 for 循环控制宽度，纵向为递归控制的深度。
回溯算法实现一般需要一个叫 backtracking 的函数，其参数可以由自己在实现的过程中完善。函数内部需要先写一下递归的结束条件，且写一下结构收集的逻辑。
void backtracking(...参数) { if(满足终止条件) { 收集结果; return; } for(集合元素 in 可选项) { 处理节点; backtraing(...下一阶段参数); 撤销选择; } }
作业题
51. N 皇后
package jjn.carl.backtrack; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; /** * @author Jjn * @since 2023/7/29 16:28 */ public class LeetCode51 { public List<List<String>> solveNQueens(int n) { List<List<String>> result = new ArrayList<>(); char[][] board = new char[n][n]; for (char[] c : board) { Arrays.fill(c, '.'); } backtrack(n, result, 0, board); return result; } private void backtrack(int n, List<List<String>> result, int row, char[][] board) { if (row == n) { List<String> snapshot = new ArrayList<>(); for (int i = 0; i < n; i++) { snapshot.add(new String(board[i])); } result.add(snapshot); return; } for (int column = 0; column < n; column++) { if (isOkay(board, row, column, n)) { board[row][column] = 'Q'; backtrack(n, result, row + 1, board); board[row][column] = '.'; } } } private boolean isOkay(char[][] board, int row, int column, int n) { for (int i = 0; i < n; i++) { if (board[i][column] == 'Q') { return false; } } for (int i = row - 1, j = column - 1; i >= 0 && j >= 0; i--, j--) { if (board[i][j] == 'Q') { return false; } } for (int i = row - 1, j = column + 1; i >= 0 && j <= n - 1; i--, j++) { if (board[i][j] == 'Q') { return false; } } return true; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int i = scanner.nextInt(); List<List<String>> lists = new LeetCode51().solveNQueens(i); System.out.println(String.join(",", lists.toString())); } }
37. 解数独
class Solution { public void solveSudoku(char[][] board) { backtrack(board); } private boolean backtrack(char[][] board) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; 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; } private boolean isValid(int i, int j, int k, char[][] board) { for (int l = 0; l < 9; l++) { if (board[i][l] == k) { return false; } } for (int l = 0; l < 9; l++) { if (board[l][j] == k) { return false; } } int startHeight = (i / 3) * 3; int startWidth = (j / 3) * 3; for (int row = startHeight; row < startHeight + 3; row++) { for (int column = startWidth; column < startWidth + 3; column++) { if (board[row][column] == k) { return false; } } } return true; } }
