力扣每日一题36：有效的数独

题目描述：

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

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

• 一个有效的数独（部分已被填充）不一定是可解的。
• 只需要根据以上规则，验证已经填入的数字是否有效即可。
• 空白格用 '.' 表示。

示例 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 存在, 因此这个数独是无效的。

提示：

• board.length == 9
• board[i].length == 9
• board[i][j] 是一位数字（1-9）或者 '.'

通过次数

396.1K

提交次数

627.9K

通过率

63.1%

思路和题解：

题目已经给出了数独有效的三个规则，并且这三个规则都满足才能保证数独有效，我们可以针对每一个规则都判断一遍。对于规则1，我们可以把每一行都判断一遍，由于给出的是一个不完整的数独，所以只要查看每一行是否有重复即可，不用判断是否每一个都刚好出现一次。对于规则2，只是把行换成了列而已。对于规则3，我们只要判断每个九宫格就行了。下面是这种方法的代码：

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {//判断3*3宫格int i=0,j=0;int row=0,col=0;while(row<7){col=0;while(col<7){int visited[10]={0};for(i=row;i<row+3;i++){for(j=col;j<col+3;j++)if(board[i][j]>='1'&&board[i][j]<='9')visited[board[i][j]-'0']++;}for(i=1;i<=9;i++)if(visited[i]>1)return false;col+=3;}row+=3;}//判断每一行for(row=0;row<9;row++){int visited[10]={0};for(col=0;col<9;col++){if(board[row][col]>='1'&&board[row][col]<='9')visited[board[row][col]-'0']++;}for(i=1;i<=9;i++)if(visited[i]>1)return false;}//判断每一列for(col=0;col<9;col++){int visited[10]={0};for(row=0;row<9;row++){if(board[row][col]>='1'&&board[row][col]<='9')visited[board[row][col]-'0']++;}for(i=1;i<=9;i++)if(visited[i]>1)return false;}return true;}
};

对于上述的方法，如果运气不好的话，我们要遍历三次九宫格才能判断出一个九宫格是否有效。如果我们用三个数组分别记住每一行的数字1-9出现的次数、每一列的数字1-9出现的次数、每一个九宫格的数字1-9出现的次数，每次遍历的时候如果遍历的是'.'，那就直接遍历下一个；如果出现的是数字num，那么就对应行的数字+1，对应列的数字+1，对应九宫格的数字+1，在+1后，如果对应行的数字>1或对应列的数字>1或对应九宫格的数字>1，那就放回false。遍历结束返回true。由于官方题解的代码我和的思路差不多，而且可读性更强，所以我就直接给出了官方题解代码。

class Solution {
public:bool isValidSudoku(vector<vector<char>>& board) {int rows[9][9];int columns[9][9];int subboxes[3][3][9];memset(rows,0,sizeof(rows));memset(columns,0,sizeof(columns));memset(subboxes,0,sizeof(subboxes));for (int i = 0; i < 9; i++) {for (int j = 0; j < 9; j++) {char c = board[i][j];if (c != '.') {int index = c - '0' - 1;rows[i][index]++;columns[j][index]++;subboxes[i / 3][j / 3][index]++;if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {return false;}}}}return true;}
};