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

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

题目原地址

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。


上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

示例 1:

输入:

[
  ["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:

输入:

[
  ["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 相同。
但由于位于左上角的 3×3 宫内有两个 8 存在, 因此这个数独是无效的。
说明:

一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 ‘.’ 。
给定数独永远是 9×9 形式的。

  • 在一次遍历中处理完所有的行和列及块 重点是找到如何计算块的**index =(i/3)*3 + l/3****
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
}