哈希算法题目：有效的数独 题目描述 请你判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可： 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。 数独部分空格内已填入了数字，空白格用 '.' 表示。 解题过程 这个问题的核心是检查三个维度（行、列、3x3宫）上是否存在重复的数字。哈希表是解决此类“存在性”和“唯一性”问题的理想工具。 第一步：明确检查目标 我们需要遍历整个 9x9 的棋盘。对于每一个非空格子（即数字字符），我们都要检查这个数字是否在其所在的行、列和 3x3 宫中已经出现过。 第二步：设计哈希策略 我们可以为每一行、每一列、每一个 3x3 宫都分别维护一个哈希集合。这样，总共有： 9个行的哈希集合 9个列的哈希集合 9个 3x3 宫的哈希集合 每个集合用来记录该行/列/宫中已经出现过的数字。 第三步：建立索引映射关系 行和列的索引是直观的。 board[i][j] 就在第 i 行，第 j 列。 关键在于，如何确定一个格子 (i, j) 属于哪一个 3x3 宫呢？ 我们可以将 9x9 的棋盘从上到下、从左到右，划分为 9 个 3x3 的宫，并给它们编号 0 到 8。 行的索引 i 的范围是 0 到 8。将 i 除以 3（整数除法），可以确定这个格子位于 第几大行 的宫（0, 1, 2）。 列的索引 j 的范围是 0 到 8。将 j 除以 3（整数除法），可以确定这个格子位于 第几大列 的宫（0, 1, 2）。 那么，宫的编号 box_index 可以通过一个简单的公式计算： box_index = (i // 3) * 3 + (j // 3) 例如，格子 (4, 5)： i // 3 = 4 // 3 = 1 (第1大行) j // 3 = 5 // 3 = 1 (第1大列) box_index = 1 * 3 + 1 = 4 (属于编号为4的宫) 第四步：遍历与检查 现在我们可以开始遍历棋盘了： 初始化数据结构：创建 3 个长度为 9 的数组，每个元素都是一个空的哈希集合（在代码中通常用字典或集合实现）。 rows = [set() for _ in range(9)] cols = [set() for _ in range(9)] boxes = [set() for _ in range(9)] 使用双重循环遍历每个格子 (i, j) 。 如果当前格子的值 num 是 '.'，则跳过，检查下一个格子。 如果 num 是数字，则进行以下检查： a. 计算它所在的宫索引： box_index = (i // 3) * 3 + (j // 3) b. 检查 num 是否已经存在于 rows[i] 集合中？或者存在于 cols[j] 集合中？或者存在于 boxes[box_index] 集合中？ 如果 存在 于任何一个集合中，说明违反了数独规则，立即返回 False 。 如果 不存在 于任何一个集合中，说明到目前为止是有效的。那么我们需要将 num 分别添加到这三个集合中（ rows[i].add(num) , cols[j].add(num) , boxes[box_index].add(num) ），以记录它已经出现过了。 如果成功遍历完所有的格子，都没有发现重复，那么我们就返回 True 。 总结 这个方法的核心思想是 空间换时间 。我们通过维护 27 个（9行+9列+9宫）哈希集合，使得我们可以在遍历棋盘的过程中，对每个数字进行常数时间 O(1) 的重复性检查。整个算法的时间复杂度是 O(1)，因为棋盘大小是固定的 9x9=81 个格子。如果棋盘大小是 NxN，那么时间复杂度是 O(N²)。