# 第三十周ARTS总结
# Algorithm
2ms | 90.46% Run time
42.8MB | 97.10% Memory
public boolean isValidSudoku(char[][] board) {
// 遍历每一行
for (int i = 0; i < 9; i++) {
List<Character> chars = new ArrayList<>();
for (int j = 0; j < 9; j++) {
if ('.' == board[i][j]) {
continue;
}
if (!chars.contains(board[i][j])) {
chars.add(board[i][j]);
} else {
return false;
}
}
}
// 遍历每一列
for (int i = 0; i < 9; i++) {
List<Character> chars = new ArrayList<>();
for (int j = 0; j < 9; j++) {
if ('.' == board[j][i]) {
continue;
}
if (!chars.contains(board[j][i])) {
chars.add(board[j][i]);
} else {
return false;
}
}
}
// 遍历每一3*3矩阵
int x = 0;
int y = 0;
while (x <= 6 && y <= 6) {
if (contain(board, x, y)) {
return false;
} else {
if (y == 6) {
x = x + 3;
y = 0;
} else {
y = y + 3;
}
}
}
return true;
}
/**
* 行从索引x开始，列从索引y开始的一个3*3矩阵是否重复
*
* @param board
* @param x
* @param y
* @return
*/
private boolean contain(char[][] board, int x, int y) {
List<Character> chars = new ArrayList<>();
for (int i = x; i < x + 3; i++) {
for (int j = y; j < y + 3; j++) {
if ('.' == board[i][j]) {
continue;
}
if (!chars.contains(board[i][j])) {
chars.add(board[i][j]);
} else {
return true;
}
}
}
return false;
}
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
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
# Review
# Tip
- mipmap-anydpi-v26的用处：用来适配APP的启动图标；
# Share
暂无内容