0%

LeetCode-Valid Sudoku

https://leetcode-cn.com/problems/valid-sudoku/

用最直接的思路,使用 map 验证是否存在重复,使用二重循环来运行三种判别方式。需要注意的是 sub-box 判断的坐标取法。

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
func isValidSudoku(board [][]byte) bool {
for i:=0;i<9;i++ {
mRow:=make(map[byte]bool)
mCol:=make(map[byte]bool)
mSub:=make(map[byte]bool)
for j:=0;j<9;j++ {
cRow:=board[i][j]
cCol:=board[j][i]
cSub:=board[3*(i/3)+j/3][3*(i%3)+j%3]
if cRow!='.' {
if _,ok:=mRow[cRow];ok {
return false
}
mRow[cRow]=true
}
if cCol!='.' {
if _,ok:=mCol[cCol];ok {
return false
}
mCol[cCol]=true
}
if cSub!='.' {
if _,ok:=mSub[cSub];ok {
return false
}
mSub[cSub]=true
}
}
}
return true
}

发现 Solution 里有一个 Trick 的方法,直接将“那里存在什么”作为一个整体存入哈希表里,如果重复直接返回错误。

这个答案中的代码贴在下面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean isValidSudoku(char[][] board) {
Set seen = new HashSet();
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) {
char number = board[i][j];
if (number != '.')
if (!seen.add(number + " in row " + i) ||
!seen.add(number + " in column " + j) ||
!seen.add(number + " in block " + i/3 + "-" + j/3))
return false;
}
}
return true;
}