代码随想录计划
Day 26–回溯算法
总结
回溯算法解决的问题，是一些使用for循环嵌套无法解决的问题。这些问题能被求解出来已经很不错了，所以回溯算法的时间复杂度通常都很高。回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。
回溯是递归的副产品，只要有递归就会有回溯，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。
回溯算法能解决如下问题：
- 组合问题：N个数里面按一定规则找出k个数的集合
- 排列问题：N个数按一定规则全排列，有几种排列方式
- 切割问题：一个字符串按一定规则有几种切割方式
- 子集问题：一个N个数的集合里有多少符合条件的子集
- 棋盘问题：N皇后，解数独等等
如今，组合，排列，切割，子集我们已经都做过相关题目了。
总体来说，做回溯题目时可以将回溯过程抽象为一个N叉树，以便我们理解回溯过程。
组合，排列，子集问题相对来说简单一些，根据回溯算法的模板加上对题目的理解基本就可以做出来。在一些基础题目上再加上去重的操作就是进阶题目。切割问题难一些。
剩下的棋盘问题都是非常难的题目
N皇后
这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后_哔哩哔哩_bilibili
建议直接看视频，听完视频写下来觉得也不是很难。自己写可能是另一回事。
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;
}
}
// 检查45度对角线
for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
// 检查135度对角线
for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
if (chessboard[i][j] == 'Q') {
return false;
}
}
return true;
}
}
解数独
看视频吧，难度更大了
回溯算法二维递归？解数独不过如此！| LeetCode：37. 解数独_哔哩哔哩_bilibili
class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHelper(board);
}
private boolean solveSudokuHelper(char[][] board){
//「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，
// 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」
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++){
// (i, j) 这个位置放k是否合适
if (isValidSudoku(i, j, k, board)){
board[i][j] = k;
if (solveSudokuHelper(board)){
// 如果找到合适一组立刻返回
return true;
}
board[i][j] = '.';
}
}
// 9个数都试完了，都不行，那么就返回false
return false;
// 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！
// 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」
}
}
// 遍历完没有返回false，说明找到了合适棋盘位置了
return true;
}
/**
* 判断棋盘是否合法有如下三个维度:
* 同行是否重复
* 同列是否重复
* 9宫格里是否重复
*/
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;
}
}
// 9宫格里是否重复
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;
}
}
