leetcode 37. 解数独-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 37. 解数独。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023.7.26

leetcode 37. 解数独,leetcode专栏,leetcode,算法,职场和发展,c++,数据结构

这题也是回溯经典应用题，和之前n皇后问题的最大区别是，之前n皇后问题每行只需要放一个皇后，本质上属于一维的，即回溯的for循环只有一层。此时是一个二维的回溯递归，for循环有两层。

本题回溯函数的返回值为bool类型，原因是本题我们只需要返回一个解集即可，（即一个棋盘），遇到合适的棋盘直接返回就行。而之前的组合、分割、排列等问题都需要返回所有解集情况。

和n皇后问题一样，需要设一个valid函数判断此时的棋盘合不合规矩。

下面看代码：

class Solution {
public:
    bool valid(int row, int col, char value, vector<vector<char>>& board)
    {
        //判断行
        for(int i=0;i<9;i++)
        {
            if(board[row][i] == value) return false;
        }
        //判断列
        for(int j=0;j<9;j++)
        {
            if(board[j][col] == value) return false; 
        }
        //判断斜线
        int start_row = row / 3 * 3;
        int start_col = col / 3 * 3;
        for(int i=start_row; i<start_row+3; i++)
        {
            for(int j=start_col; j<start_col+3; j++)
            {
                if(board[i][j]==value) return false;
            }
        }
        return true;
    }
    bool backtrack(vector<vector<char>>& board)
    {
        for(int i=0; i<board.size(); i++)//遍历行
        {
            for(int j=0; j<board[0].size(); j++)//遍历列
            {
                if(board[i][j] == '.')
                {
                    for(char k='1'; k<='9'; k++)
                    {
                        if(valid(i,j,k,board))//此位置放k是否合适。
                        {
                            board[i][j] = k;
                            if(backtrack(board)) return true;
                            board[i][j] = '.';
                        }
                    }
                    return false; //9个数试完还没找到就返回false
                }
            }
        }
        return true;
    }
    void solveSudoku(vector<vector<char>>& board) {
        backtrack(board);
    }
};

时间复杂度：O(9^m),m为 . 的个数

空间复杂度: O(n^2) 文章来源地址https://www.toymoban.com/news/detail-610579.html

到了这里，关于leetcode 37. 解数独的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！