免费建站平台哪个稳定常州网站制作建设

免费建站平台哪个稳定,常州网站制作建设,沧州网站建设的集成商,forceful wordpress哈喽各位#xff0c;我是前端小L。 欢迎来到我们的回溯算法专题第十篇#xff01;数独游戏大家应该都玩过#xff0c;规则极其“简单粗暴”#xff1a; 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能…哈喽各位我是前端小L。欢迎来到我们的回溯算法专题第十篇数独游戏大家应该都玩过规则极其“简单粗暴”数字 1-9在每一行只能出现一次。数字 1-9在每一列只能出现一次。数字 1-9在每一个以粗实线分隔的3x3 宫内只能出现一次。我们现在的任务是写一个程序把一个残缺的数独填完。 这道题和之前最大的不同在于我们要找的不是“所有解”而是“一个解”。一旦找到立刻停止这意味着我们的递归函数要有返回值 (bool)用来告诉上一层“搞定了别试了快撤”力扣 37. 解数独https://leetcode.cn/problems/sudoku-solver/题目分析输入9x9的二维字符数组board。空位用.表示。目标原地修改board填入唯一的一个可行解。核心思维如何遍历二维空格在 N 皇后中我们通过backtrack(row 1)来控制递归深度。 但在数独中空格是散落在棋盘各处的。 我们通常采用双重循环 递归的策略递归逻辑伪代码Plaintextfunction backtrack(board): for i from 0 to 8: for j from 0 to 8: if board[i][j] is Empty: // 发现一个坑尝试填 1-9 for k from 1 to 9: if isValid(i, j, k): 填入 k if backtrack(board) is True: return True // 找到了一路绿灯返回 撤销 k (回溯) return False // 1-9 都试过了都不行说明前面的步骤填错了无解 return True // 遍历完所有格子没返回 False说明填满了注意到了吗这个递归结构和之前的很不一样。它在函数内部就开启了对整个棋盘的扫描。一旦发现空格就通过递归去填下一个空格。isValid的九宫格判定判断行和列很简单。难点在于判断3x3 九宫格。 对于任意坐标(r, c)它所属的 3x3 宫的左上角坐标是startRow (r / 3) * 3startCol (c / 3) * 3通过这两个基准点我们可以遍历该宫内的 9 个格子。代码实现 (C)C#include vector using namespace std; class Solution { private: // 判断在 board[row][col] 填入 val 是否合法 bool isValid(int row, int col, char val, vectorvectorchar board) { // 1. 检查行 for (int j 0; j 9; j) { if (board[row][j] val) return false; } // 2. 检查列 for (int i 0; i 9; i) { if (board[i][col] val) return false; } // 3. 检查 3x3 九宫格 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表示是否找到了一组解 // 如果找到立即停止后续搜索 bool backtrack(vectorvectorchar board) { // 遍历整个棋盘寻找空格 for (int i 0; i 9; i) { for (int j 0; j 9; j) { // 如果发现空格 if (board[i][j] .) { // 尝试填入 1 到 9 for (char k 1; k 9; k) { if (isValid(i, j, k, board)) { // 做选择 board[i][j] k; // 递归如果后续的填充成功了那我也直接返回 true if (backtrack(board)) return true; // 撤销选择 (回溯) board[i][j] .; } } // 9个数字都试完了还不行说明这个空格在这个局面下无解 // 或者是前面的步骤填错了需要回溯 return false; } } } // 如果两个循环跑完都没有返回 false说明没有空格了填满了 return true; } public: void solveSudoku(vectorvectorchar board) { backtrack(board); } };深度复杂度分析时间复杂度非常恐怖。数独的空白格可能有 M 个。每个格子有 9 种选择。理论上限是 O(9M)。但由于数独的约束非常强每填一个数其他格子的选择就少很多实际运行并不慢。空间复杂度O(M)。递归栈的深度等于空白格的数量。总结回溯算法的“毕业设计”恭喜你这道题通过标志着你已经攻克了回溯算法最险峻的山峰。让我们回顾一下回溯算法的“进化史”组合/子集startIndex控制不回头path收集结果。排列used数组控制不重复选关注顺序。切割startIndex作为切割线判断子串合法性。去重sortnums[i] nums[i-1]剪掉树层重复。棋盘N 皇后一维决策行二维约束。解数独二维决策每个格子找唯一解bool 返回值。这一套组合拳打下来所有的暴力搜索问题在你面前都将无所遁形。接下来学什么我们已经完成了DP内功、图论招式、回溯暴力美学。 接下来我建议我们稍微“换个口味”去探索一下算法面试中代码量最少但思维最巧妙的领域——贪心算法 (Greedy)。下一篇我们将从经典的**“分发饼干”**开始看看如何用“局部最优”推导出“全局最优”。准备好你的直觉了吗下期见