刷题的朋友对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是1j // 3是1宫格编号就是4也就是中间那个大宫格完全正确。这个方案比三次遍历干净很多时间和空间也更省。一次遍历直接扫完81个格子每个格子做常数次集合操作代码量也控制得很好。我平时刷题默认就用这个版本。2.3 解法三位掩码把三个哈希表压缩成三个整数熟悉位运算的人还会写出一个更炫的版本。因为每个格子只可能是1-9九个数字完全可以用一个整型变量的9个二进制位来表示哪些数字出现过。数字n1到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(vectorvectorchar 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 # 左上角宫格内出现两个6invalid_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本身我个人实际操作中的体会是千万别小看这题它代码短、逻辑直观但越是这类题越容易在细节上翻车。宫格索引、空格跳过、字符转数字每一个小坑都真实存在。我建议你至少把集合版和位运算版各写一遍再用我上面准备的那组用例本地跑一跑。等你真正把判重逻辑内化成看到棋盘就自动想到行、列、宫格三组集合的思维习惯再遇到任何棋盘类变体都能秒破。