目录

[Medium]LeetCode#36. 有效的数独

Resowolf 收录于 LeetCode

2019-05-10 约 553 字预计阅读 2 分钟

https://img.cdn.resowolf.com/static/LeetCode_Medium.png

目录

[Medium]LeetCode#36. 有效的数独

题目原地址

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
[
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1:
输入:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
[
  ["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:
输入:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
[
  ["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 存在, 因此这个数独是无效的。
说明:
一个有效的数独（部分已被填充）不一定是可解的。只需要根据以上规则，验证已经填入的数字是否有效即可。给定数独序列只包含数字 1-9 和字符 ‘.’ 。给定数独永远是 9x9 形式的。

在一次遍历中处理完所有的行和列及块重点是找到如何计算块的index =(i/3)3 + l/3

 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
func isValidSudoku(board [][]byte) bool {
    res := true
	//行map
	lMap := make(map[string]int)
	//列map
	rMap := make(map[string]int)
	//块map
	bMap := make([]map[string]int, 9)
	for i := 0; i < 9; i++ {
		for l := 0; l < 9; l++ {
			sIL:=string(board[i][l])
			sLI:=string(board[l][i])
			//处理行
			lMap[sIL]++
			//处理行
			rMap[sLI]++
			//处理块
			bIndex := (i/3)*3 + l/3
			if bMap[bIndex] == nil {
				bMap[bIndex] = make(map[string]int)
			}
			bMap[bIndex][sIL]++
			if (sIL != "." && (lMap[sIL] > 1 || bMap[bIndex][sIL] > 1)) || (sLI != "." && rMap[sLI] > 1){
				res = false
				break
			}
		}
		lMap = make(map[string]int)
		rMap = make(map[string]int)
		if !res {
			break
		}
	}
	return res
}