算法练习第五天——有效数独

法练习第五天——有效数独

有效数独题目

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

数字 1-9 在每一行只能出现一次。

数字 1-9 在每一列只能出现一次。

数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。

只需要根据以上规则，验证已经填入的数字是否有效即可。

空白格用 '.' 表示。

示例：

输入：shudu =

[[".","6","1",".","3",".",".","2","."]

,[".","5",".",".",".","8","1",".","7"]

,[".",".",".",".",".","7",".","3","4"]

,[".",".","9",".",".","6",".","7","8"]

,[".",".","3","2",".","9","5",".","."]

,["5","7",".","3",".",".","9",".","."]

,["1","9",".","7",".",".",".",".","."]

,["8",".","2","4",".",".",".","6","."]

,[".","4",".",".","1",".","2","5","."]]

输出：true

解题思路

这道题其实就是让我们判断行、列、九宫格内是否存在重复的元素，如果存在返回False，否则返回True

我们可以分别维护行、列、九宫格三个哈希表，然后每次判断是否存在即可。

这里唯一需要思考的是，如果判断当前的单元格，在哪个九宫格中，简单推倒下就能得出:  x // 3 * 3 + y // 3

方法一：遍历

以下代码以golang为例：

func isyouxiaoshudu(board [][]byte) bool {
    var rows, columns [9][9]int
    var subboxes [3][3][9]int
    for i, row := range board {
        for j, c := range row {
            if c == '.' {
                continue
            }
            index := c - '1'
            rows[i][index]++
            columns[j][index]++
            subboxes[i/3][j/3][index]++
            if rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i/3][j/3][index] > 1 {
                return false
            }
        }
    }
    return true
}

改解法复杂度分析

时间复杂度：O(1)。数独共有 81 个单元格，只需要对每个单元格遍历一次即可。

空间复杂度：O(1)。由于数独的大小固定，因此哈希表的空间也是固定的。