企业官网建设流程全解析

刷题的朋友对LeetCode 36这道“有效数独”（Valid Sudoku）应该都不陌生。题目看起来就是判断一个9×9棋盘合不合法，但真上手你会发现，难点不在算法，而在把“有效”理解到位。这篇就围绕LeetCode 36，把解法思路、代码实现、常见坑和扩展变体一次讲透。不管是刚刷题的新手，还是准备面试想快速过一遍经典题的老手，都能在里面找到能直接用的东西。

1. 先搞清楚题目在问什么

1.1 题面逐句翻译

LeetCode 36的原题描述很简洁：给你一个9×9的二维字符数组，里面已经填入一部分数字，空白位置用.表示。要求判断这个数独是否"有效"。

什么叫有效？官方给了三条规则：

• 每一行里，数字1-9只能出现一次。
• 每一列里，数字1-9只能出现一次。
• 每一个3×3的小宫格里，数字1-9只能出现一次。

换句话说，只需要判断已经填进去的那些格子有没有违规，至于数独是不是能继续解下去、会不会有唯一解，完全不在本题范围内。理解了这一点，整道题的锁定方向就非常清晰了：判重，而且只判重。

1.2 最容易踩的三个认知误区

第一个误区是"我觉得它既然是数独，就一定要把所有空格都填完才能判断"。不需要，也别这么干。题目只要求验证已填入的数字是否符合规则，空格是待填空位，不参与任何冲突判断。

第二个误区是"有效数独是不是要求每个格子都合法，包括将来填什么也要考虑"。同样不需要。这道题不涉及推理，你不需要去尝试填任何格子，也不需要检查这个局面是否有解。所有需要的信息都在当前棋盘里。

第三个误区更隐蔽：有人会理解成"每一行必须同时包含1到9这九个数字，少一个都不合法"。这是把"数独完整答案"和"数独当前局面是否有效"混为一谈了。一个全空的棋盘，每一行都没有任何数字，按题目定义它是有效的；一个只有几个数字且不重复的棋盘，也是有效的。我见过不少人在这一点上卡住，写了个"必须凑齐九个数字"的版本，结果样例都过不了。

1.3 这道题真正在训练什么

从算法训练的角度看，LeetCode 36是典型的"集合查重"题。它的核心操作就一个：遍历棋盘，遇到数字就检查它是否已经在某个集合里出现过。这个集合可以是哈希表、布尔数组，甚至是整型变量的二进制位。

它真正考察的是两件事。一是你会不会把三组判断条件（行、列、宫格）组织得干净利落，二是你对固定规模问题的复杂度有没有直觉。棋盘只有81个格子，理论上无论怎么遍历都是常数时间，但写出来的代码却有高下之分。后面我会把三种不同层次的解法都过一遍，从最直白的扫描到面试官眼前一亮的位运算版。

2. 从暴力到优雅：三种解法层层递进

2.1 解法一：三次独立扫描，最直白的思路

最直观的做法是分三次遍历：第一次检查每一行，第二次检查每一列，第三次检查每一个3×3宫格。每次检查都新建一个去重集合，遇到数字就查集合里有没有它，没有就放进去，有就直接返回False。

先看行检查：

def is_valid_row(board): for i in range(9): seen = set() for j in range(9): ch = board[i][j] if ch == '.': continue if ch in seen: return False seen.add(ch) return True

列检查就是把行列下标互换，宫格检查则需要用双重循环去遍历九个宫格，每个宫格内再用两层循环扫内部的3×3区域。逻辑上没有难点，代码也不容易写错，就是看起来有点长。

这个方案最大的问题不是性能，而是"重复代码多"。三个函数长得几乎一样，只是下标映射方式不同。面试时写三遍，容易让面试官觉得你对代码的组织能力一般。而且一旦后续要扩展，比如把棋盘改成16×16，三处都要改，维护成本明显上升。所以这个思路适合用来理解题意，但不适合作为最终提交版本。

2.2 解法二：一次遍历，三个方向的判重表同时维护

更常见的写法是只遍历一次棋盘，同时维护三组集合：行集合、列集合、宫格集合。每个格子只需要做三件事：

• 检查数字是否出现在当前行集合里。
• 检查数字是否出现在当前列集合里。
• 检查数字是否出现在当前宫格集合里。

都没出现过，就分别加入这三个集合。这里最关键的是宫格编号怎么算。数独棋盘有9个宫格，按从左到右、从上到下的顺序，可以编号为0到8。对于位置(i, j)，它所在的宫格编号是：

box_index = (i // 3) * 3 + j // 3

我来解释一下这个公式为什么会成立。i // 3表示当前行在第几个"宫格行"里，取值0、1、2；乘以3之后，得到的是当前宫格行的起始编号；j // 3表示当前列在第几个"宫格列"里，也是0、1、2。两者相加，正好是0到8的宫格编号。比如第5行第4列，i // 3是1，j // 3是1，宫格编号就是4，也就是中间那个大宫格，完全正确。

这个方案比三次遍历干净很多，时间和空间也更省。一次遍历直接扫完81个格子，每个格子做常数次集合操作，代码量也控制得很好。我平时刷题，默认就用这个版本。

2.3 解法三：位掩码，把三个哈希表压缩成三个整数

熟悉位运算的人还会写出一个更"炫"的版本。因为每个格子只可能是1-9九个数字，完全可以用一个整型变量的9个二进制位来表示哪些数字出现过。

数字n（1到9）对应掩码就是1 << (n - 1)。检查时，用当前值rows[i]和掩码做按位与，如果结果不为0，说明这个数字已经出现过；如果为0，就用按位或把它写进去。行、列、宫格各用一个长度为9的整型数组，一共27个整数就搞定了。

这个版本的好处是空间利用率极高，在C++或Java里尤其明显。Python的整数虽然也是对象，但这里因为只涉及位运算，性能也不差。缺点是位运算的可读性对初学者不太友好，面试时需要边写边解释清楚。我自己在面试中一般不会主动先写位运算版，而是先写集合版，讲完思路后再说一句"其实还可以用位掩码优化"，然后看面试官反应决定要不要写第二版。

3. 代码落地与核心细节

3.1 推荐实现（Python / C++ 可直接抄）

Python里推荐用set，代码最自然。我平时提交就是下面这个版本：

from typing import List class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: 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): ch = board[i][j] if ch == '.': continue if ch in rows[i]: return False rows[i].add(ch) if ch in cols[j]: return False cols[j].add(ch) box_idx = (i // 3) * 3 + j // 3 if ch in boxes[box_idx]: return False boxes[box_idx].add(ch) return True

这里有个小细节：ch in rows[i]相当于一次哈希查找，如果不存在再执行add。你可能会想，能不能直接用add然后判断返回值？在Python里set.add没有返回值，所以不能那么写。如果用的是dict，倒是可以用setdefault，但没必要绕。

C++版本通常会换成布尔数组，因为数字范围固定是1到9，布尔数组比unordered_set更快、更省内存：

class Solution { public: bool isValidSudoku(vector<vector<char>>& board) { bool rows[9][9] = {false}; bool cols[9][9] = {false}; bool boxes[9][9] = {false}; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { if (board[i][j] == '.') continue; int num = board[i][j] - '1'; int box_idx = (i / 3) * 3 + j / 3; if (rows[i][num] || cols[j][num] || boxes[box_idx][num]) { return false; } rows[i][num] = true; cols[j][num] = true; boxes[box_idx][num] = true; } } return true; } };

这个版本的num = board[i][j] - '1'把字符'1'到'9'映射成数字0到8，刚好可以作为数组下标，比直接用字符本身更规范。

3.2 宫格编号公式：从走到哪一步算哪步到为什么必须这样写

我见过好几个小伙伴在宫格索引上翻车。有人把公式写成(i / 3) + (j / 3) * 3，有人写成j / 3 + i / 3 * 3，还有人直接这样写：(i * 3) / 3 + j / 3，这种就完全是错的。

我建议用一个朴素的记法来帮自己验证：画一个9×9棋盘，把宫格编号按从左到右、从上到下标记成0到8。然后随便选三个点验证公式，比如第2行第2列（棋盘正中间），它的i // 3 = 0、j // 3 = 0，宫格编号是0，对，因为第2行第2列在左上角的宫格里。再看第5行第5列，i // 3 = 1、j // 3 = 1，宫格编号4，也就是正中间那个宫格。如果公式写反，这两个点就会算出错值。

注意：i // 3用的是整除。Python的//和C++的/对于正整数没有区别，都是向下取整，结果只会是0、1、2。如果哪个语言里整除符号写错了，整个宫格索引都会错位。

3.3 复杂度为什么是O(1)而不是O(N²)

LeetCode 36的棋盘尺寸固定为9×9，总共81个格子。无论用解法一、解法二还是位运算版，每个格子最多只处理常数次，所以时间复杂度和空间复杂度都可以说是O(1)。这也是面试时一个潜在的考察点：很多人张口就说O(N²)，其实在固定输入下这么表述不够准确。

但换个角度，如果把问题抽象成N×N的数独，其中N是边长，那么一次遍历扫描所有N²个格子，时间是O(N²)，空间是O(N)。两种说法都对，关键取决于你是把N定义为棋盘边长，还是把固定规模当成常数。我建议面试时这么讲："因为题目固定是9×9，所以我的代码运行时间和额外空间都是常数级；如果想推广到N×N，那时间复杂度是O(N²)。"这样既严谨，又能显示出你真的理解了复杂度的含义。

4. 实测排坑：常见错误与测试用例

4.1 提交记录里最常出现的四类错误

第一类是忘记跳过.。如果没有continue，遇到空格也会去查集合，程序立刻返回False。这个错误最基础，但特别容易在从纸上写代码转到IDE时犯。

第二类是宫格索引写错。尤其是解法二里，box_idx一旦算错，就会出现两个不同的格子被分到了同一个集合，一个明明合法的数独被判成非法，或者反过来。我建议如果提交后报错，优先检查这一行。

第三类是使用了错误的数据结构。有人会把rows初始化成一个长度为9的list，里面放list而不是set，然后判断时用if ch in rows[i]，实际上list的成员判断是线性扫描，虽然这题只有9个元素看不出性能问题，但代码意图不够清晰，也不够通用。

第四类是边界问题。比如把字符和数字搞混，'1'和1在类型上完全不同；还有人在位运算版本里写1 << int(ch)，没有先减去'1'，导致数字9的位移过大。正常情况下只用9个位，减'1'后变成0到8，才是正确范围。

4.2 一组可以直接跑的手写测试用例

我习惯在本地写完代码后，用下面这几个用例快速验证。第一个是题里给出的经典有效数独，第二个构造一个行冲突，第三个构造一个宫格冲突。

valid_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"] ] invalid_row = [row[:] for row in valid_board] invalid_row[0][2] = "5" # 第1行出现两个5 invalid_box = [row[:] for row in valid_board] invalid_box[0][2] = "6" # 左上角宫格内出现两个6

invalid_row里，board[0][0]已经是"5"，再把board[0][2]改成"5"，整个棋盘就违法了。invalid_box里，左上角宫格原本包含"5"、"3"、"6"、"9"、"8"等，把第三格改成"6"之后，和board[1][0]的"6"冲突。这两个改动都很小，打印出来容易一眼看出问题。

还有一个不能忘的边界用例：全空棋盘。全填.时，三组判断都不会触发，应该返回True。写代码的时候我经常用这个用例来测试初始化逻辑有没有低级错误。

4.3 面试时怎么把这题讲清楚

如果是在面试里碰到这道题，我不建议直接闷头写最优解。我会先花三十秒把题目要求复述一遍，特别强调"只判断已填入数字是否重复，不判断是否可解"，让面试官确认我们的理解一致。然后我会先说集合版方案，因为它最容易让人听懂。

写代码时，我会刻意把"行、列、宫格"三个部分使用同一种结构维护，这样代码读起来非常整齐。写完以后，如果面试官有追问，我再说可以优化成位掩码版，并解释"因为数字只有1-9九个可能，一个int的二进制位足够表示"。

还有一个实用的小技巧：我讲复杂度的措辞是"由于棋盘固定为9×9，总体是O(1)，但我写的循环结构也可以自然扩展到N×N场景"。这个回答既展示了代码的通用性，又显示了边界意识，算是一个加分点。

5. 升级与变体：从判重到解数独

5.1 变体一：可解数独（回溯+剪枝）

如果面试官接着问"那你怎么判断这个数独是不是有解"，题目就升级成更经典的解数独问题。大体思路是：找到第一个空格，尝试填入1-9中的每个数字，每填一个就调用一个类似LeetCode 36的校验函数，看是否合法；合法就递归处理下一个空格，不合法就回溯。

这时候LeetCode 36的判重函数可以直接复用。你可以把校验逻辑单独抽出来，作为回溯过程中的剪枝条件。很多人的回溯写得不顺，主要原因就是没有先想清楚约束条件，LeetCode 36恰好提供了这个基础。

不过要注意，可解数独的判重函数调用次数很多，每次都遍历81个格子有点浪费。优化方法是在回溯过程中只检查当前行、当前列、当前宫格和刚填入数字的关系，而不用扫描全盘。这是另一个层次的话题，但思路源头仍然是"如何高效判重"。

5.2 变体二：16×16数独与字符范围变化

如果把棋盘从9×9改成16×16，数字范围也变成1-16，那判重逻辑基本不变，只是宫格变成4×4，宫格编号公式要相应调整：box_index = (i // 4) * 4 + j // 4。字符处理也会变，可能不再是'9'封顶，而要用到'A'到'F'之类的字符。

这种变体考察的是你能不能从具体题目里提炼出通用模式。固定9个数字时，用布尔数组或位掩码很舒服；一旦范围变大，用set反而更灵活。所以在真实场景里，我会先写集合版本，因为它对输入规模变化的适应性更好。

5.3 变体三：只统计重复次数 / 子数独有效性

还有一类变体是"统计每个数字在所有区域中出现的次数"，比如返回每个数字的分布，或者判断某个子区域是否合法。这类问题基本就是LeetCode 36的查重逻辑加一个计数器，属于组合变形，核心思想仍然是"通过行列索引计算区域编号，再维护一个映射"。

我遇到过一道类似题目，要求判断多个3×3子矩阵是否各自包含重复元素。用LeetCode 36里的box_idx公式，加一个外层循环枚举所有子矩阵，代码很快就能组织出来。可以说，只要你能熟练计算区域编号，很多棋盘类题目都能套用同一套模板。

回到LeetCode 36本身，我个人实际操作中的体会是：千万别小看这题，它代码短、逻辑直观，但越是这类题，越容易在细节上翻车。宫格索引、空格跳过、字符转数字，每一个小坑都真实存在。我建议你至少把集合版和位运算版各写一遍，再用我上面准备的那组用例本地跑一跑。等你真正把判重逻辑内化成"看到棋盘就自动想到行、列、宫格三组集合"的思维习惯，再遇到任何棋盘类变体，都能秒破。