🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
⭐数独⭐
🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
前言
回溯算法是⼀种经典的递归算法，通常⽤于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想：从⼀个初始状态开始，按照⼀定的规则向前搜索，当搜索到某个状态⽆法前进 时，回退到前⼀个状态，再按照其他的规则搜索。
回溯算法在搜索过程中维护⼀个状态树，通过遍历 状态树来实现对所有可能解的搜索。 回溯算法的核⼼思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜 索；否则，回退到上⼀个状态，重新做出选择。
回溯算法通常⽤于解决具有多个解，且每个解都需要 搜索才能找到的问题。
回溯算法的模板
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Backtracking {public void backtracking(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();Arrays.sort(candidates);// 如果需要对candidates进行排序backtrack(result, new ArrayList<>(), candidates, target, 0);}private void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {if (remain < 0) { // 如果 remain 小于 0，表示当前的组合不符合要求，直接返回return;} else if (remain == 0) { // 如果 remain 等于 0，表示当前的组合符合要求，加入到结果中result.add(new ArrayList<>(tempList));} else {for (int i = start; i < candidates.length; i++) {if (i > start && candidates[i] == candidates[i - 1]) {continue; // 避免重复计算，如果当前数字和上一个数字相同，则跳过}tempList.add(candidates[i]); // 将当前数字加入到临时列表中backtrack(result, tempList, candidates, remain - candidates[i], i + 1); // 递归调用，继续向下搜索tempList.remove(tempList.size() - 1); // 回溯，将最后加入的数字移除，尝试下一个数字}}}
}
回溯算法是⼀种⾮常重要的算法，可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核⼼ 思想是搜索状态树，通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板⾮常简单，但是实 现起来需要注意⼀些细节，⽐如如何做出选择、如何撤销选择等。
1: 数独验证 (LeetCode 36. 有效的数独)
题目链接：36. 有效的数独 - 力扣（LeetCode）
算法思路
算法原理描述
我们需要检查一个9x9的数独板是否有效。有效的数独需要满足以下条件：
- 每一行、每一列以及每一个3x3的小方格中都包含数字1-9且不重复。
- 可以使用三个布尔数组来分别记录行、列以及小方格中的数字出现情况。
类定义及变量初始化
定义一个名为
Solution的类来封装解决方案逻辑。
boolean[][] row: 用于存储每行每个数字是否已经出现过。boolean[][] col: 用于存储每列每个数字是否已经出现过。boolean[][][] grid: 用于存储每个3x3小方格内每个数字是否已经出现过。主方法实现
主方法
isValidSudoku:
- 初始化
row,col和grid。- 遍历整个棋盘，对于非空格的单元格，标记对应的数字在行、列和小方格中已出现。
- 如果发现任何冲突，则返回
false。- 如果遍历完整个棋盘没有发现冲突，则返回
true。
代码实现
class Solution {public boolean isValidSudoku(char[][] board) {// 对每一行一列每个小方格记录并判断boolean[][] row = new boolean[9][10];boolean[][] col = new boolean[9][10];boolean[][][] grid = new boolean[3][3][10];for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char ch = board[i][j];if (ch != '.') {int num = ch - '0';if (row[i][num] || col[j][num] || grid[i / 3][j / 3][num]) {return false;}row[i][num] = true;col[j][num] = true;grid[i / 3][j / 3][num] = true;}}}return true;}
}2: 数独求解 (LeetCode 37. 解数独)
题⽬链接： 37. 解数独 - 力扣（LeetCode）
算法思路
算法原理描述
我们使用深度优先搜索（DFS）和回溯法来尝试填充数独板。通过递归地尝试每个空格可能的数字，并在发现冲突时进行回溯，直到找到一个完整的解或遍历完所有可能性。
类定义及变量初始化
定义一个名为
Solution的类来封装解决方案逻辑。
boolean[][] row: 用于存储每行每个数字是否已经出现过。boolean[][] col: 用于存储每列每个数字是否已经出现过。boolean[][][] grid: 用于存储每个3x3小方格内每个数字是否已经出现过。主方法实现
主方法
solveSudoku:
- 初始化
row,col和grid。- 标记已有的数字。
- 调用递归方法
dfs开始求解。
代码实现
class Solution {boolean[][] row, col;boolean[][][] grid;public void solveSudoku(char[][] board) {// 初始化布尔数组row = new boolean[9][10];col = new boolean[9][10];grid = new boolean[3][3][10];// 标记已有的数字for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] != '.') {int num = board[i][j] - '0';row[i][num] = true;col[j][num] = true;grid[i / 3][j / 3][num] = true;}}}// 开始深度优先搜索dfs(board);}public boolean dfs(char[][] board) {for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {if (board[i][j] == '.') { // 如果是空格for (int num = 1; num <= 9; num++) { // 尝试填入1-9的数字if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num]) { // 剪枝// 放置数字board[i][j] = (char) ('0' + num);row[i][num] = true;col[j][num] = true;grid[i / 3][j / 3][num] = true;if (dfs(board)) { // 递归调用return true; // 如果找到了解，直接返回true}// 回溯board[i][j] = '.';row[i][num] = false;col[j][num] = false;grid[i / 3][j / 3][num] = false;}}// 所有数字都尝试过了还没有返回，说明这个路径无效return false;}}}// 整个棋盘都被填充，说明找到了一个解return true;}
}总结
后续不再更新每日一题了，感觉有的题用不着写博客，后续只更新高质量的题咯，感谢阅览！！
