代码随想录 Day30 - 回溯（六）
作者：jjn0703
- 2023-07-29 江苏
本文字数：1972 字
阅读完需：约 6 分钟
回溯章节总结
回溯是一种暴力搜索算法，适合解决的问题有：
组合问题
切割问题
子集问题
排列问题
棋盘问题
回溯可以抽象为一棵树形结构，横向为 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; }}复制代码
划线
评论
复制
发布于: 刚刚阅读数: 3
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/c0ed75f3b78b3241d315706f9】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论