360企业网站认证,广州建造网站公司,成都哪个网站建设比较好,网络运营托管文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析#xff1a;本题也是一道困难题#xff0c;难点在于如何构建数独棋盘#xff0c;如何检查棋盘的合法性#xff… 文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引可以看这篇文章——【算法和数据结构】LeetCode题解。 一、题目 二、解法 思路分析本题也是一道困难题难点在于如何构建数独棋盘如何检查棋盘的合法性再一个难点在于如何对棋盘进行遍历并放置数字。数组棋盘的构建笔者采用了一个最朴素的方法将已知的‘.’和数字依次push_back进棋盘数组中然后根据数独的规则每行每列每个九空格内不能有重复的元素构建isValid函数然后利用两层嵌套循环遍历棋盘棋盘的每个点用1-9的数组依次带入如果合法则进行下一步的递归。最终得到一个数独的解这个解就是整个棋盘数组将其输出。 程序如下
class Solution {
private:bool isValid(vectorvectorchar board, char num, int row, int col) { // 检查棋盘是否合法 // 检查行列九空格内是否有重复元素for (int i 0; i board.size(); i) { // 检查列if (board[i][col] num) return false;}for (int j 0; j board[0].size(); j) { // 检查行if (board[row][j] num) return false;}// 检查九空格找到board[row][col]所在的九空格 然后用二层循环遍历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] num) return false;}}return true;}bool backtracking(vectorvectorchar board) {for (int row 0; row board.size(); row) {for (int col 0; col board[0].size(); col) {if (board[row][col] ! .) continue;for (char num 1; num 9; num) {if (isValid(board, num, row, col)) {board[row][col] num; // 放置数字处理节点;if(backtracking(board)) return true; // 递归board[row][col] .; // 回溯撤销处理结果}}return false; // 九个数字都不行说明数独无解}}return true;}
public:vectorvectorchar solveSudoku(vectorvectorchar board) {backtracking(board);return board;}
};复杂度分析
时间复杂度 O ( n ! ) O(n!) O(n!)。空间复杂度 O ( n ) O(n) O(n)。
三、完整代码
# include iostream
# include vector
# include string
using namespace std;class Solution {
private:bool isValid(vectorvectorchar board, char num, int row, int col) { // 检查棋盘是否合法 // 检查行列九空格内是否有重复元素for (int i 0; i board.size(); i) { // 检查列if (board[i][col] num) return false;}for (int j 0; j board[0].size(); j) { // 检查行if (board[row][j] num) return false;}// 检查九空格找到board[row][col]所在的九空格 然后用二层循环遍历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] num) return false;}}return true;}bool backtracking(vectorvectorchar board) {for (int row 0; row board.size(); row) {for (int col 0; col board[0].size(); col) {if (board[row][col] ! .) continue;for (char num 1; num 9; num) {if (isValid(board, num, row, col)) {board[row][col] num; // 放置数字处理节点;if(backtracking(board)) return true; // 递归board[row][col] .; // 回溯撤销处理结果}}return false; // 九个数字都不行说明数独无解}}return true;}
public:vectorvectorchar solveSudoku(vectorvectorchar board) {backtracking(board);return board;}
};int main() {vectorvectorchar board;board.push_back({ 5, 3, ., ., 7, ., ., ., . });board.push_back({ 6, ., ., 1, 9, 5, ., ., . });board.push_back({ ., 9, 8, ., ., ., ., 6, . });board.push_back({ 8, ., ., ., 6, ., ., ., 3 });board.push_back({ 4, ., ., 8, ., 3, ., ., 1 });board.push_back({ 7, ., ., ., 2, ., ., ., 6 });board.push_back({ ., 6, ., ., ., ., 2, 8, . });board.push_back({ ., ., ., 4, 1, 9, ., ., 5 });board.push_back({ ., ., ., ., 8, ., ., 7, 9 });Solution s1;vectorvectorchar result s1.solveSudoku(board);for (vectorvectorchar::iterator it result.begin(); it ! result.end(); it) {for (vectorchar::iterator jt (*it).begin(); jt ! (*it).end(); jt) {cout *jt ;}cout endl;}system(pause);return 0;
}end
