描述
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.
分析
数独的规则只有3条，每一行，每一列，每一个小方块（一共9个小方块），1-9九个数字最多只能出现一次。细节题，按照条件判断即可。
解决方案1（C++）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
int rows[9];
int cols[9];
int block[9];
for(int i = 0; i < 9; i++) {
memset(rows, 0, sizeof(int)*9);
memset(cols, 0, sizeof(int)*9);
for(int j = 0; j < 9; j++) {
if(board[i][j] != '.') {
if(rows[board[i][j]-'1'] > 0){
return false;
}else{
rows[board[i][j]-'1']++;
}
}
if(board[j][i] != '.') {
if(cols[board[j][i]-'1'] > 0) {
return false;
}else {
cols[board[j][i]-'1']++;
}
}
}
}
for(int i = 0; i < 3; i++) {
for(int j = 0; j < 3; j++) {
memset(block, 0, sizeof(int)*9);
for(int a = 0; a < 3; a++) {
for(int b = 0; b < 3; b++) {
if(board[3*i+a][3*j+b] != '.') {
if(block[board[3*i+a][3*j+b]-'1']>0)return false;
else block[board[3*i+a][3*j+b]-'1']++;
}
}
}
}
}
return true;
}
};
|
「先解决，再优化」：一共9个小块，可以用i，j表示，在两层循环中，第a个小块可以表示为(i/3)*3+j/3，时间复杂度$O(n^2)$，空间复杂度$O(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
bool isValidSudoku(vector<vector<char> > &board) {
vector<vector<bool>> rows(9, vector<bool>(9,false));
vector<vector<bool>> cols(9, vector<bool>(9,false));
vector<vector<bool>> block(9, vector<bool>(9,false));
for(int i = 0; i < 9; i++) {
for(int j = 0; j < 9; j++) {
if(board[i][j] != '.') {
int num = board[i][j] - '1';
if(rows[i][num] || cols[j][num] || block[(i/3)*3+j/3][num]) {
return false;
}
rows[i][num] = cols[j][num] = block[(i/3)*3+j/3][num] = true;
}
}
}
return true;
}
};
|
相关问题
sudoku solver