题目内容

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

注意：

1、一个有效的数独（部分已被填充）不一定是可解的。
2、只需要根据以上规则，验证已经填入的数字是否有效即可。

示例

示例 1：

输入：board =
[[“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

示例 2：

输入：board =
[[“8”,”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”]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示

1、board.length == 9
2、board[i].length == 9
3、board[i][j] 是一位数字或者 ‘.’

题解

本题是根据规则，利用布尔数组进行判断，具体通过代码注释进行解释。

代码

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool st[9];
        //判断行
        for(int i = 0; i < 9; i++){
            memset(st, 0, sizeof st);//将每行的布尔数组初始化为false
            for(int j = 0; j < 9; j++){
              	//看每行是否存在重复
                if(board[i][j] != '.'){
                  	//如果当前位置不为空，用t表示当前位置的数，
                    int t = board[i][j] - '1'; //把字符的1-9改为下标的0-8，这样能够和布尔数组的下标保持一致。
                    if(st[t]) return false;//当st[t]为true，则说明这个数之前已经出现过，那么直接返回false
                    st[t] = true;//将false修改为true
                }
            }
        }
        
        //判断列，与行的思路一致
        for(int i = 0; i < 9; i++){
            memset(st, 0, sizeof st);//将每行的布尔数组清空
            for(int j = 0; j < 9; j++){
                if(board[j][i] != '.'){
                    int t = board[j][i] - '1'; //把字符的1-9改为下标的0-8
                    if(st[t]) return false;
                    st[t] = true;
                }
            }
        }

        //判断小方格，因为每个小方格3x3，所以外层判断中步长为3.
        for(int i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
              	//每一次的小方格去遍历前，都会将st数组变为false
                memset(st, 0, sizeof st);
              	//遍历每一个的小方格
                for(int x = 0; x < 3; x++){
                    for(int y = 0; y < 3; y++){
                        if(board[i + x][j + y] != '.'){
                            int t = board[i + x][j + y] - '1';
                            if(st[t]) return false;
                            st[t] = true;
                        }
                    }
                }
            }
        }

        return true;
    }
};