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.
image.png
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.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
The given board contain only digits 1-9 and the character '.'.
The given board size is always 9x9.
有效数独
题目的意思就是 保证
每行
每列
每3x3 的小方格 内 不允许出现重复数字
于是乎 ，我就依次检查
每行
每列
每3x3
..............
这题应该有啥优雅的写法，我先写个不用动脑的。。
#include <unordered_map>
using namespace std;
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
//row
for(int i = 0; i < 9; i++){
up.clear();
for(int j = 0; j < 9;j++){
up[board[i][j]]++;
if( board[i][j] !='.' && up[board[i][j]] > 1 )
return false;
}
}
// column
for(int i = 0; i < 9; i++){
up.clear();
for(int j = 0; j < 9;j++){
up[board[j][i]]++;
if( board[j][i] !='.' && up[board[j][i]] > 1 )
return false;
}
}
// 3X3
for(int i = 0; i < 9 ; i+=3){
for(int j = 0; j < 9; j+=3){
if (!isValid33(board, i,j))
return false;
}
}
return true;
}
private:
unordered_map<char,int> up;
bool isValid33(vector<vector<char>>& board,int x, int y){
up.clear();
for(int i = x; i < x+3; i++){
for(int j = y; j < y +3; j++){
up[board[i][j]]++;
if( board[i][j] !='.' && up[board[i][j]] > 1 )
return false;
}
}
return true;
}
};
所以这题 就是考 行， 列，3X3 在一个循环内的对应关系。
行转列很简单
主要是 行 转 3 X3
比如
(0,0), (0,1),(0,2) | (0,3),(0,4),(0,5)| (0,6),(0,7),(0,8) |
(1,0), (1,1),(0,2) | (1,3),(1,4),(1,5)| (1,6),(1,7),(1,8) |
.....
(3,0), (3,1),(3,2) | (3,3),(3,4),(3,5)| (3,6),(3,7),(3,8) |
我们希望在遍历行的同时，把 第一个3X3 映射到第0 个哈希表中， 第二个3x3映射到第二个哈希表中。。。以此类推
我们发现 i 增的比较慢(外循环)
i/3 的序列是
0,0,0,0,0,0,0,0,0,
......x 2
1,1,1,1,1,1,1,1,1,
......x 2
2,2,2,2,2,2,2,2,2
.......x 2
j增的比较快（内循环）
j/3 的序列是
0,0,0,1,1,1,2,2,2
0,0,0,1,1,1,2,2,2
0,0,0,1,1,1,2,2,2
.....x 6
我们想要的 序列是：
0,0,0,1,1,1,2,2,2
...x 2
3,3,3,4,4,4,5,5,5
...x 2
6,6,6,7,7,7,8,8,8
..x 2
所以我们不难得出， i/3*3 + j/3 就是最终的 3x3 对应的哈希表编号
搞定 循环内 row,col, 3x3 的对应哈希表下标， 就可以把3个循环写在一起了。
这里因为只有9个数字(1..9)， 所以我使用 比特位来做哈希数组，节省空间.
比特位作哈希数组，就是运用3个操作(<< , & ,|)
1<< k ， 把 1 向左移动K位，
类似 hash_map[5] ==1
使用比特位就是 (00000001) << 5 == (00010000)
这样第5 个比特位就占上了，
如果再出现5 ， 那么(00010000) & (00010000) 就会不等于0 。
反之， 就把该数字 | 到比特数组上， 把该比特位占上。
代码如下。
#include <vector>
using namespace std;
class Solution {
private:
vector<int> row = vector<int>(9);
vector<int> col =vector<int>(9);
vector<int> sub = vector<int>(9);
int sub_index = 0;
int bits;
public:
bool isValidSudoku(vector<vector<char>>& board) {
for(int i = 0;i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] != '.'){
sub_index = i/3*3+ j/3;
// 使用 1个数字的不同比特位， 来当作一个哈希数组
bits = (1<< (board[i][j]-'0'));
if(row[i] & bits || col[j] & bits || sub[sub_index] & bits)
return false;// 有比特位被占， 说明有数字已经出现过
// 没有出现过， 把该比特位占上
row[i] |=bits;
col[j] |=bits;
sub[sub_index] |=bits;
}
}
}
return true;
}
};
