【LeetCode】36. 有效的数独

叁歲伎倆 2022-05-03 00:56 186阅读 0赞

**题目链接**：[https://leetcode-cn.com/problems/valid-sudoku/description/][https_leetcode-cn.com_problems_valid-sudoku_description]

#### 题目描述 ####

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。  
数字 1-9 在每一列只能出现一次。  
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

![在这里插入图片描述][250px-Sudoku-by-L2G-20050714.svg.png]  
上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

#### 示例 ####

\[  
\[“5”,“3”,".",".",“7”,".",".",".","."\],  
\[“6”,".",".",“1”,“9”,“5”,".",".","."\],  
\[".",“9”,“8”,".",".",".",".",“6”,"."\],  
\[“8”,".",".",".",“6”,".",".",".",“3”\],  
\[“4”,".",".",“8”,".",“3”,".",".",“1”\],  
\[“7”,".",".",".",“2”,".",".",".",“6”\],  
\[".",“6”,".",".",".",".",“2”,“8”,"."\],  
\[".",".",".",“4”,“1”,“9”,".",".",“5”\],  
\[".",".",".",".",“8”,".",".",“7”,“9”\]  
\]  
输出: true

**说明**:

*  一个有效的数独（部分已被填充）不一定是可解的。
 *  只需要根据以上规则，验证已经填入的数字是否有效即可。
 *  给定数独序列只包含数字 1-9 和字符 ‘.’ 。
 *  给定数独永远是 9x9 形式的。

#### 解决方法 ####

**分别对每一行、每一列及每一个3\*3宫格进行验证**

class Solution { 
    public:
        bool isValidSudoku(vector<vector<char>>& board) { 
            for (int i=0;i<9;i++) //验证每一行
                if (!isRow(board,i))
                    return false;
            for (int i=0;i<9;i++) //验证每一列
                if (!isColumn(board,i))
                    return false;
            for (int i=0;i<9;i++) //验证每一个3x3宫
                if (!isPalace(board,i))
                    return false;
            return true;
        }
    private:
        bool isRow(vector<vector<char>> board, int row){ 
            vector<int> times(10,0);
            for (int i=0;i<9;i++)
                if (isdigit(board[row][i])) times[board[row][i]-'0']++;
            for (int i=0;i<10;i++)
                if (times[i]>=2) return false;
            return true;
        }
        bool isColumn(vector<vector<char>> board, int column){ 
            vector<int> times(10,0);
            for (int i=0;i<9;i++)
                if (isdigit(board[i][column])) times[board[i][column]-'0']++;
            for (int i=0;i<10;i++)
                if (times[i]>=2) return false;
            return true;
        }
        bool isPalace(vector<vector<char>> board, int k){ 
            vector<int> times(10,0);
            int startX,startY;
            if (k==0) { startX=0;startY=0;}
            if (k==1) { startX=0;startY=3;}
            if (k==2) { startX=0;startY=6;}
            if (k==3) { startX=3;startY=0;}
            if (k==4) { startX=3;startY=3;}
            if (k==5) { startX=3;startY=6;}
            if (k==6) { startX=6;startY=0;}
            if (k==7) { startX=6;startY=3;}
            if (k==8) { startX=6;startY=6;}
            for (int i=startX;i<startX+3;i++)
                for (int j=startY;j<startY+3;j++)
                    if (isdigit(board[i][j])) times[board[i][j]-'0']++;
            for (int i=0;i<10;i++)
                if (times[i]>=2) return false;
            return true;
        }    
    };

[https_leetcode-cn.com_problems_valid-sudoku_description]: https://leetcode-cn.com/problems/valid-sudoku/description/
[250px-Sudoku-by-L2G-20050714.svg.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png