题目
题目地址
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 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）或者 '.'
解题思路-分别处理
分别处理每一行、每一列以及每一个九宫格，哪一部分验证失败，都返回 false，如果都验证通过，返回 true。
代码实现
|
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
function getOrigin(){
return {
'1':0,
'2':0,
'3':0,
'4':0,
'5':0,
'6':0,
'7':0,
'8':0,
'9':0,
}
}
function checkArr(arr){
const counts = getOrigin()
for(let i = 0;i<9;i++){
if(counts[arr[i]]){
return false
}else{
counts[arr[i]]++
}
}
return true
}
var isValidSudoku = function(board) {
// 处理每一行
for(let i = 0;i<9;i++){
if(!checkArr(board[i])){
return false
}
}
// 处理每一列
for(let i = 0;i<9;i++){
const arr = []
for(let j = 0;j<9;j++){
if(board[j][i] === '.'){
continue
}
arr.push(board[j][i])
}
if(!checkArr(arr)){
return false
}
}
// 处理 9 个九宫格
for(let i = 0;i<3;i++){
for(let j = 0;j<3;j++){
const arr = []
for(let k = j*3;k<j*3+3;k++){
for(let h = 3*i;h<3*i+3;h++){
if(board[k][h] === '.'){
continue
}
arr.push(board[k][h])
}
}
if(!checkArr(arr)){
return false
}
}
}
return true
}
|
解题思路-一次扫描判断所有
首先创建 lines 记录每一行出现的数字的次数，columns 记录每一列出现的数字的次数，scratchableLatexs 记录每一个九空格出现的数字的次数。
然后双层循环可以遍历输入数组中的每一个元素，根据当前 i,j 值判断属于哪一行，哪一列以及哪一个九宫格，分别判断即可。
代码实现
|
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
|
function getOrigin(){
return {
'1':0,
'2':0,
'3':0,
'4':0,
'5':0,
'6':0,
'7':0,
'8':0,
'9':0,
}
}
var isValidSudoku = function(board) {
const lines = []
const columns = []
const scratchableLatexs = []
for(let i = 0;i<9;i++){
lines[i] = getOrigin()
columns[i] = getOrigin()
scratchableLatexs[i] = getOrigin()
}
for(let i = 0;i<9;i++){
for(let j = 0;j<9;j++){
const item = board[i][j]
if(item === '.'){
continue
}
if(lines[i][item]){
return false
}else{
lines[i][item]++
}
if(columns[j][item]){
return false
}else{
columns[j][item]++
}
if(i<3){
if(j<3){
if(scratchableLatexs[0][item]){
return false
}else{
scratchableLatexs[0][item]++
}
}else if(j<6){
if(scratchableLatexs[1][item]){
return false
}else{
scratchableLatexs[1][item]++
}
}else{
if(scratchableLatexs[2][item]){
return false
}else{
scratchableLatexs[2][item]++
}
}
}else if(i<6){
if(j<3){
if(scratchableLatexs[3][item]){
return false
}else{
scratchableLatexs[3][item]++
}
}else if(j<6){
if(scratchableLatexs[4][item]){
return false
}else{
scratchableLatexs[4][item]++
}
}else{
if(scratchableLatexs[5][item]){
return false
}else{
scratchableLatexs[5][item]++
}
}
}else{
if(j<3){
if(scratchableLatexs[6][item]){
return false
}else{
scratchableLatexs[6][item]++
}
}else if(j<6){
if(scratchableLatexs[7][item]){
return false
}else{
scratchableLatexs[7][item]++
}
}else{
if(scratchableLatexs[8][item]){
return false
}else{
scratchableLatexs[8][item]++
}
}
}
}
}
return true
}
|
|
