哈希算法题目：有效的数独

题目描述
请你判断一个 9x9 的数独是否有效。数独部分空格内已填入了数字，空白格用 '.' 表示。

有效的数独需要满足以下三个条件：

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

解题思路分析
我们需要验证给定的数独棋盘是否满足三个条件。由于只需要验证现有数字的排列是否有效（不需要解数独），我们可以用哈希表来记录每个数字在行、列、宫中的出现情况。

详细解题步骤

步骤1：理解数据结构需求
对于9x9的数独，我们需要：

• 9个行哈希表：记录每行中数字1-9的出现情况
• 9个列哈希表：记录每列中数字1-9的出现情况
• 9个宫哈希表：记录每个3x3宫中数字1-9的出现情况

步骤2：设计哈希映射方案
我们可以用三种哈希集合来分别记录：

• rows[i]：第i行已出现的数字集合
• cols[j]：第j列已出现的数字集合
• boxes[box_index]：第box_index个宫已出现的数字集合

其中宫的索引计算：box_index = (i // 3) * 3 + (j // 3)

步骤3：遍历棋盘验证
遍历每个格子(i, j)：

1. 如果格子是'.'，跳过
2. 如果是数字，检查该数字是否已存在于对应的行、列、宫集合中
3. 如果存在，返回false（违反规则）
4. 如果不存在，将该数字添加到对应的三个集合中

步骤4：具体实现细节

def isValidSudoku(board):
    # 初始化9个行集合、9个列集合、9个宫集合
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    
    for i in range(9):
        for j in range(9):
            num = board[i][j]
            if num == '.':
                continue
                
            # 计算当前格子属于哪个3x3宫
            box_index = (i // 3) * 3 + (j // 3)
            
            # 检查数字是否已存在于对应的行、列、宫
            if (num in rows[i] or 
                num in cols[j] or 
                num in boxes[box_index]):
                return False
            
            # 将数字添加到对应的集合中
            rows[i].add(num)
            cols[j].add(num)
            boxes[box_index].add(num)
    
    return True

步骤5：复杂度分析

• 时间复杂度：O(1)，因为固定遍历81个格子
• 空间复杂度：O(1)，使用了固定大小的哈希集合（3×9=27个集合）

步骤6：测试用例验证
例如测试用例：

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。

关键点总结

1. 使用哈希集合来高效检查重复数字
2. 宫的索引计算是关键技巧：(i//3)*3 + (j//3)
3. 只需要验证现有数字，不需要解数独
4. 三个条件必须同时满足才算有效数独