有效的数独（LeetCode 36）：Python 解法、宫格索引与边界情况

有效的数独（LeetCode 36）给你一个部分填好的 9×9 棋盘，问你已填的格子是否违反了数独规则。你不需要解出这个谜题，只需检查每一行、每一列、每个 3×3 宫内没有数字重复。用三个已见数字集合一次遍历即可完成，时间复杂度为 O(81)，也就是常数级。

问题

棋盘是一个 9×9 的字符网格，每个字符是 1 到 9 的数字，或者用 . 表示空格。如果已填的格子满足以下规则，返回 true：

• 每一行没有重复数字。
• 每一列没有重复数字。
• 每个 3×3 宫内没有重复数字。

一个棋盘即使无解，也可能是有效的。只检查已填的格子。

思路：每个单元用三个集合

为每一行、每一列、每个宫各维护一个已见数字集合。对于每个已填的格子，检查该数字是否出现在这三个集合中，如果是新数字就加入。

唯一需要动脑的地方是宫的索引。对于第 r 行、第 c 列的格子，宫的编号是 (r // 3) * 3 + c // 3。它从左到右、从上到下把宫编号为 0 到 8。

def is_valid_sudoku(board):
    rows = [set() for _ in range(9)]
    cols = [set() for _ in range(9)]
    boxes = [set() for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == ".":
                continue
            b = (r // 3) * 3 + c // 3
            if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
                return False
            rows[r].add(ch)
            cols[c].add(ch)
            boxes[b].add(ch)
    return True

追踪

假设第 0 行第 0 列有一个 5，第 4 列又有一个 5。第一个 5 被加入 rows[0]、cols[0] 和 boxes[0]。到第 4 列时，ch in rows[0] 为真，函数立即返回 false。同一宫或同一列中的重复数字也会被另外两个集合以同样的方式捕获。

复杂度

棋盘始终是 9×9，所以时间是常数级，共访问 81 个格子。如果推广到 n×n 的棋盘，时间复杂度是 O(n²)，空间复杂度也是 O(n²)。两者都要说，因为面试官经常问它如何扩展。

面试官会问的变体

位掩码版本用整数替代每个集合。mask & (1 << d) 测试一个数字，mask |= 1 << d 记录它。它更快，但集合版本在时间压力下更容易写对，所以先写那个。

常见错误

• 检查了行和列，却忘了宫。
• 宫的公式写错，比如 r // 3 + c // 3，会给不同的宫相同的索引。
• 把 . 当成数字，导致两个空格被算作重复。
• 题目只要求判断有效性，却试图去解棋盘。

需要测试的边界情况

面试中如何讲解

1. 复述规则，说明你只做验证，不解题。
2. 说出三个单元，并说明每个都需要一个已见集合。
3. 给出宫的索引公式，并用一个例子解释。
4. 写出单次遍历和提前返回。
5. 说明复杂度，如果被问到就提供位掩码版本。

我在发布前用 20,000 个随机棋盘（有些有效，有些故意破坏）把上面的代码与简单的行、列、宫检查做了对比测试。像这样快速随机验证是练习时的好习惯。

相关练习

复杂度术语见我们的 Big O 速查表，接下来练什么见 LeetCode Blind 75 清单，如何练习见编程面试助手指南。

写代码时把你的思路说出来。一份记录能看出你是否在动手前说出了关键观察。在任何实时评估中都遵守雇主关于 AI 工具的规定。