网站上的洗衣液瓶子做花瓶怎么材质,有没有做衣服的网站吗,如何做图片 网站 链接,现在黄金多少钱一克题目
力扣题目链接
思路
卡哥的思路#xff0c;注意看他解释为什么是“二维回溯”。我的思路#xff0c;类似y总解决 N 皇后问题时的第二种方法#xff0c;即从左上到右下枚举棋盘的每个位置。 至于为什么与 N 皇后问题不一样#xff0c;我认为是因为它每一行不止放一个…题目
力扣题目链接
思路
卡哥的思路注意看他解释为什么是“二维回溯”。我的思路类似y总解决 N 皇后问题时的第二种方法即从左上到右下枚举棋盘的每个位置。 至于为什么与 N 皇后问题不一样我认为是因为它每一行不止放一个每一行的每个位置都要进行考虑。
代码
卡哥代码见上方思路。我的代码
class Solution {
private:bool isValid(int row, int col, char val, vectorvectorchar board) {// 判断该行是否有重复for (int i 0; i 9; i) {if (board[row][i] val) {return false;}}// 判断该列是否有重复for (int i 0; i 9; i) {if (board[i][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;}// 有返回值是因为只需要找到一种可行的方案好好理解一下bool backtracking(int x, int y, vectorvectorchar board) {// 遍历到一行的末尾了就开始遍历下一行if (y 9) {y 0;x;}// x 9说明 0~8 这9行都遍历完了if (x 9) {return true;}// 如果该位置还没填数的if (board[x][y] .) {// 遍历9种可能for (char i 1; i 9; i) {if (isValid(x, y, i, board)) {board[x][y] i;if (backtracking(x, y 1, board)) {return true;}board[x][y] .;}}// 9种都不行就返回falsereturn false;}else {return backtracking(x, y 1, board);}}public:void solveSudoku(vectorvectorchar board) {backtracking(0, 0, board);}
};对于回溯函数为什么需要返回值的解释
ChatGPT 你原来的代码返回值为void在找到一个解之后会继续尝试其他可能的填充选项并继续回溯这样会导致找到的解可能会被覆盖从而使最终输出的可能不是第一个找到的解甚至可能无法正确地保留一个有效解。 详细分析 回溯的本质 你的回溯算法会从左上角开始遍历整个数独网格。如果在某个位置找到了一个有效的填充数字算法会继续前进直到填满整个网格或者无法找到合适的数字为止。如果算法到达了一个无法继续的状态即当前路径不再可行它会回退到上一个状态并尝试其他可能的数字。 没有提前终止 你的代码中没有检测到第一个有效解后提前终止的机制。当回溯算法在最后一格填上数字时虽然它找到了一个有效解但是它不会立即返回而是继续尝试回溯试图寻找其他可能的解。由于继续回溯它可能会更改已经填好的数字尝试其他路径结果导致解被覆盖或者递归无限循环而导致栈溢出如你之前遇到的无限递归问题。 覆盖问题 在回溯过程中每当你在一个位置填入一个数字后都会立即调用递归函数进入下一步。如果在某个位置找到的第一个有效数字满足所有条件继续前进最后递归完成一整次操作后如果继续回溯这个数字可能会被回溯掉并试图用下一个数字替换。因为没有及时终止算法会尝试其他可能的数字组合可能覆盖掉第一个找到的有效解。 解决方法 为了避免上述问题关键在于找到第一个有效解后立即终止进一步的回溯和搜索。这可以通过让递归函数在找到一个有效解时返回true来实现以阻止后续的任何修改。
