有效的数独

难度: Medium

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

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

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

示例 1：

输入：board = 
[["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：

输入：board = 
[["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 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

Submission

运行时间: 56 ms

内存: 14.9 MB

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        row = [set() for _ in range(9)]
        col = [set() for _ in range(9)]
        block = [set() for _ in range(9)]

        for i in range(9):
            for j in range(9):
                val = board[i][j]
                if val == '.':
                    continue
                pos = i // 3 * 3 + j // 3
                if val in row[i] or val in col[j] or val in block[pos]:
                    return False
                else:
                    row[i].add(val)
                    col[j].add(val)
                    block[pos].add(val)
        return True

Explain

题解的思路是使用三个哈希表来分别记录每一行、每一列和每个3x3宫格中已经出现过的数字。遍历数独矩阵，对于每个非空的单元格，检查其值是否已经在对应的行、列或3x3宫格的哈希表中出现过。如果出现过，说明数独无效，返回False；否则将该值添加到对应的哈希表中。遍历完整个矩阵后，如果没有发现重复的数字，说明数独有效，返回True。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        # 初始化三个哈希表，分别记录每一行、每一列和每个3x3宫格中已经出现过的数字
        row = [set() for _ in range(9)]
        col = [set() for _ in range(9)]
        block = [set() for _ in range(9)]

        for i in range(9):
            for j in range(9):
                val = board[i][j]
                if val == '.':  # 如果当前单元格为空，跳过
                    continue
                pos = i // 3 * 3 + j // 3  # 计算当前单元格所在的3x3宫格编号
                if val in row[i] or val in col[j] or val in block[pos]:  # 如果当前单元格的值已经在对应的行、列或3x3宫格中出现过，返回False
                    return False
                else:  # 否则将当前单元格的值添加到对应的行、列和3x3宫格的哈希表中
                    row[i].add(val)
                    col[j].add(val)
                    block[pos].add(val)
        return True  # 遍历完整个矩阵后，如果没有发现重复的数字，返回True

Explore

在检查数独是否有效的过程中，对于数独板上的每一个非空单元格，我们首先读取其值。然后，我们需要确定这个值是否已经存在于当前单元格所在的行、列或宫格的哈希表中。如果该值已存在，说明在数独的行、列或宫格中已经有重复的数字，因此数独无效；如果不存在，则将这个值添加到相应的哈希表中，表示该行、列或宫格已经包含了这个数字。这种方法可以快速地检查并记录每个数字出现的情况，保证数独的每个行、列和宫格内的数字都是唯一的。

在数独验证的实现中，我们使用三组哈希表，分别代表数独的每一行、每一列和每一个3x3宫格。这些哈希表用于存储已经在对应行、列或宫格中出现过的数字。对于数独板上的每个单元格，我们首先检查该单元格的值。若该值不为空，则计算它应属于的宫格的索引，这可以通过行索引整除3乘以3加上列索引整除3得到。接下来，我们查询该值是否已经存在于对应的行、列或宫格的哈希表中。如果存在，返回False表示数独无效。如果不存在，则将该值添加到三个哈希表的相应位置。这样的查询和更新操作都是O(1)的时间复杂度，使得整个数独验证过程非常高效。

在处理数独问题时，选择哈希表而不是数组或链表主要基于效率和简便性的考虑。哈希表提供了常数时间复杂度的插入和查找操作，这使得检查数字是否已存在变得非常快速。相比之下，如果使用数组，虽然空间利用率可能更高，但在检查一个数字是否存在时可能需要遍历整个数组，其时间复杂度为O(n)。链表虽然可以动态增长，但其查找和插入（如果需要保持有序）的平均时间复杂度也是O(n)。因此，哈希表在这种需要频繁查找和插入的场景下，提供了最佳的时间效率。