题目描述
Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
- Each row must contain the digits 1-9 without repetition.
- Each column must contain the digits 1-9 without repetition.
- Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
A partially filled sudoku which is valid.
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
样例
Example 1:
Input:
[
["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"]
]
Output: true
Example 2:
Input:
[
["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"]
]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being
modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
- 这道题让我们验证一个方阵是否为数独矩阵,判断标准是看各行各列是否有重复数字,以及每个小的3x3的小方阵里面是否有重复数字,如果都无重复,则当前矩阵是数独矩阵,但不代表待数独矩阵有解,只是单纯的判断当前未填完的矩阵是否是数独矩阵。
那么根据数独矩阵的定义,我们在遍历每个数字的时候,就看看包含当前位置的行和列以及3x3小方阵中是否已经出现该数字,那么我们需要三个标志矩阵,分别记录各行,各列,各小方阵是否出现某个数字,其中行和列标志下标很好对应,就是小方阵的下标需要稍稍转换一下,具体代码如下:
C++ 代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<vector<bool>> row(9,vector<bool>(9,false));
vector<vector<bool>> col(9,vector<bool>(9,false));
vector<vector<bool>> sub(9,vector<bool>(9,false));
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]!='.'){
int c=board[i][j]-'1';
if(row[i][c]||col[j][c]||sub[(i/3)*3+(j/3)][c])
return false;
row[i][c]=true;
col[j][c]=true;
sub[(i/3)*3+(j/3)][c]=true;
}
}
}
return true;
}
};
算法
(位运算判重)
- 分别使用一个整型数组记录每行、每列和每个九宫格内数字的存在情况。
- 位运算可以极大的简化判断,提高效率,具体看代码。
C++ 代码
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<int> row(9), col(9), squ(9); // 使用三个整型数组判重。
for (int i = 0; i < 9; i++)
for (int j = 0; j < 9; j++) {
if (board[i][j] == '.')
continue;
if (board[i][j] < '1' || board[i][j] > '9') return false;
int num = board[i][j] - '0';
// 以row[i] & (1 << num)为例,这是判断第i行中,num数字是否出现过。
// 即row[i]值的二进制表示中,第num位是否是1。
// 以下col和squ同理。
if ((row[i] & (1 << num)) ||
(col[j] & (1 << num)) ||
(squ[(i / 3) * 3 + (j / 3)] & (1 << num)))
return false;
row[i] |= (1 << num);
col[j] |= (1 << num);
squ[(i / 3) * 3 + (j / 3)] |= (1 << num);
}
return true;
}
};