LeetCode 36这道题几乎是每个刷题人都会路过的一站。题目要求很简单判断一个9x9的数独棋盘当前是否“有效数独”。但有意思的是很多人一看到“数独”两个字就开始脑补完整求解算法下意识把问题想复杂了另一些人则相反觉得“不就是检查重复吗”然后栽在3x3小宫格的处理上。我做算法题有个习惯先想清楚这题到底在考什么再动手写代码。这种“多维度判重”的思维后来在我的日常编码里反复用到所以我一直觉得LeetCode 36不是那种刷完就忘的题。这篇文章我想从题目拆解、思路演进、三种实现方式、容易踩的坑以及判重逻辑在工程里的迁移这几个角度把这道题完整聊透希望对正在准备算法面试的你有所帮助。1. 有效数独判定到底在考什么1.1 题目要求中的三个关键维度先看题目描述。输入是一个board二维字符数组尺寸固定是9行9列。每个格子要么是.表示空位要么是数字字符1到9。所谓有效数独只需要满足三个条件每一行里数字1~9至多出现一次每一列里数字1~9至多出现一次每一格3x3小宫格里数字1~9至多出现一次。换言之就是在三个维度上做“查重”。只要发现任意一个维度上有重复立刻返回False全部遍历完没有重复才返回True。这里有一个关键细节题目不要求这个数独最终有没有解也不要求解是否唯一。你只需要判断“已经填进去的数字”之间有没有冲突。换句话说一个棋盘即使完全没法继续填下去只要已填的数字没有在行、列、宫格中重复它仍然是一个“有效数独”。很多人在这里会走偏思考半天回溯求解结果浪费了大量时间。1.2 “判重”与“求解”的边界以及固定9x9的意义完整求解数独是一个经典的回溯问题最坏情况下的搜索空间非常大而判断数独是否有效本质上只是一个“校验”问题不涉及任何搜索。两者完全不在一个量级。而且因为棋盘被固定为9x9每一个维度的检查范围都是常数大小。这意味着即使你的代码写成三层循环嵌套理论上也不会超出81个格子太多。很多面试题会在复杂度分析上设置小陷阱这道题也经常被用来考察候选人能否区分“固定规模”和“输入规模”。如果你能清晰说出“因为棋盘恒定为9x9所以无论怎么写整体操作次数是有上限的复杂度可以看作O(1)”那么往往比直接背诵解法更让面试官满意。不过固定大小也带来一个反直觉的后果由于 n 很小不同解法之间的实际性能差距在 LeetCode 这种评测环境里几乎体现不出来。真正拉开差距的是代码是否简洁、是否容易说明思路、是否能顺手答出变体题目。这也是我接下来要聊的重点思路演进和写法选择。2. 从“找重复”到“高效找重复”思路演进2.1 最直觉的暴力思路三次独立扫描如果第一次接触这道题最自然的想法是分三次扫描先扫描每一行再扫描每一列最后扫描每一个3x3宫格。每次扫描都用一个标记结构记录数字是否出现过。用伪代码表示大概是第一次遍历所有行 对每一行用一个标记数组遇到数字就检查是否重复并标记 第二次遍历所有列 对每一列重复同样的检查 第三次遍历所有宫格 对每个3x3宫格重复同样的检查这个解法最大的优点是不会错。三个维度的逻辑完全独立理解成本低写完后也很难出现“宫格编号算错”这种问题。我第一次按这个思路写的时候几乎是零思考地通过了。但它的缺点也很明显代码重复度高行、列、宫格各写一段几乎一样的逻辑维护起来比较啰嗦。而且在面试场景下面试官通常会追问一句“能不能只用一次遍历完成” 这时候如果只给出三次扫描的方案就显得少了点思考深度。2.2 一次遍历的结构化思考每个格子同时属于行、列、宫一次遍历的核心洞察是遍历棋盘的过程中每遇到一个格子board[r][c]它同时属于第r行、第c列、以及某一个3x3小宫格。所以我们可以同时做三个维度的查重而不是先把行检查完再去检查列。关键问题来了怎么确定当前格子属于哪个宫格假设小宫格用编号0到8表示顺序是从左上到右下。对于格子(r, c)宫格编号 (r // 3) * 3 (c // 3)其中r // 3表示当前行处在哪个“宫格行区间”取值是0、1、2c // 3表示当前列处在哪个“宫格列区间”同样取值0、1、2。把“宫格行区间”乘以3加上“宫格列区间”就得到一个唯一的宫格编号。举个例子格子(4, 7)4 // 3 17 // 3 2所以宫格编号是1 * 3 2 5。这意味着它位于第二行宫格区域、第三列宫格区域也就是中间靠右的那个宫格。这个公式是整道题最容易写错的地方也是很多最优解法的心脏。理解了它后面的代码基本就是顺水推舟。3. 三种主流实现方式与我的选型建议3.1 HashSet字符串法代码最短但开销最大网上很多题解喜欢用一个HashSet把每个数字在哪个维度出现过编码成字符串然后统一存到一个集合里。代码很短def isValidSudoku(board): seen set() for r in range(9): for c in range(9): ch board[r][c] if ch .: continue if f{r}({ch}) in seen or f{c}[{ch}] in seen or f{(r // 3) * 3 c // 3}-{ch} in seen: return False seen.add(f{r}({ch})) seen.add(f{c}[{ch}]) seen.add(f{(r // 3) * 3 c // 3}-{ch}) return True比如r(ch)表示字符ch在第r行出现过c[ch]表示在第c列出现过box-ch表示在某个宫格出现过。只要三个拼出来的字符串中有一个已经在集合里就说明重复。这种方式最大的优点是代码量少、可读性高不用维护三个数组。缺点也同样明显它把字符串拼接和哈希计算的额外开销带进了循环。虽然9x9规模下这点开销完全不是问题但在面试中如果你只写这一种解面试官可能会觉得你只是会调库而不是真正理解多维度判重的本质。我自己刷题时会写这版作为“最直观”的说明但不会停在它上面。3.2 二维布尔数组法面试首选我真正推荐作为面试主答案的方案是三个9x9的布尔数组。这里的逻辑很直接rows[r][num]表示数字num是否已经在第r行出现过cols[c][num]表示数字num是否已经在第c列出现过boxes[box][num]表示数字num是否已经在第box个宫格出现过。def isValidSudoku(board): rows [[False] * 9 for _ in range(9)] cols [[False] * 9 for _ in range(9)] boxes [[False] * 9 for _ in range(9)] for r in range(9): for c in range(9): ch board[r][c] if ch .: continue num ord(ch) - ord(1) box_idx (r // 3) * 3 c // 3 if rows[r][num] or cols[c][num] or boxes[box_idx][num]: return False rows[r][num] True cols[c][num] True boxes[box_idx][num] True return True为什么说它最推荐因为它把“三个维度的查重”用三个数组直白地表达出来每一个操作都有明确的语义。面试官追问细节的时候你很容易解释rows管行、cols管列、boxes管宫格三个条件同时检查只要有一个命中就说明重复。代码不需要魔法技巧也不容易写错。如果你熟悉 Java写法几乎一样public boolean isValidSudoku(char[][] board) { boolean[][] rows new boolean[9][9]; boolean[][] cols new boolean[9][9]; boolean[][] boxes new boolean[9][9]; for (int r 0; r 9; r) { for (int c 0; c 9; c) { char ch board[r][c]; if (ch .) continue; int num ch - 1; int box (r / 3) * 3 c / 3; if (rows[r][num] || cols[c][num] || boxes[box][num]) { return false; } rows[r][num] true; cols[c][num] true; boxes[box][num] true; } } return true; }这里有一个细节值得留意num ch - 1而不是ch - 0。因为字符1的 ASCII 值是490是48。如果减0数字9会得到9数组下标就数到9了但我们的数组长度只有9合法下标是0到8。减1之后1映射到09映射到8正好覆盖9个下标。这个细节非常多的人栽过后文我会专门展开。3.3 位运算压缩法空间和速度的进阶选择如果想把代码写得更有“高端感”可以用位运算把标记数组压缩成一个整数。基本思路是用一个整数的低9位分别表示数字1到9是否出现过。比如最低位表示数字1第二位表示数字2以此类推。def isValidSudoku(board): rows [0] * 9 cols [0] * 9 boxes [0] * 9 for r in range(9): for c in range(9): ch board[r][c] if ch .: continue bit 1 (ord(ch) - ord(1)) box_idx (r // 3) * 3 c // 3 if rows[r] bit or cols[c] bit or boxes[box_idx] bit: return False rows[r] | bit cols[c] | bit boxes[box_idx] | bit return True这里bit 1 (数字映射值)的含义是如果当前数字是5ord(5) - ord(1) 4那么bit就是1 4也就是二进制的10000表示第5位被置1。判断重复时用rows[r] bit如果这一位上已经有过1结果非零说明重复。标记时用rows[r] | bit把这一位置为1。位运算的优势在于空间非常紧凑只用9个整数就行且位运算本身很快。缺点是对新手不太友好容易在和|、的优先级上犯迷糊。我个人的建议是如果你面试时已经顺利写出了布尔数组版时间又充裕可以提一句“其实还可以用位运算压缩空间”然后简单画出思路不必强行写完所有代码。这往往能成为一个加分项但如果一开始就写位运算一旦面试官追问细节你可能会解释得很费劲。3.4 三种方案对比与选型建议方案代码量可读性空间开销时间开销适用场景HashSet字符串法最少较好需存储大量字符串对象常数较大字符串拼接与哈希计算较多快速刷题、思路验证二维布尔数组法中等最好27个长度为9的布尔数组极小数组访问开销低面试讲解、工程校验位运算法短较难27个整数最小位运算最快竞赛写法、资源受限场景如果按“性价比”排序二维布尔数组法毫无疑问是第一选择。它有清晰的语义、极低的出错概率又不会像 HashSet 那样产生不必要的字符串对象。位运算版适合作为补充知识让你对底层的压缩思想有感觉。HashSet 版则可以帮你快速验证思路但不建议作为唯一的面试解。4. 实现细节与容易踩的坑4.1 字符与数字转换的边界这是我见过出错率最高的一处。题目给的是字符数组但你在做标记时希望拿到的是“数字0到8”这样的整数下标。常见的错误是把字符1和整数1混为一谈。正确做法有两种用num ord(ch) - ord(1)得到0到8配合长度为9的数组使用用num ord(ch) - ord(0)得到1到9配合长度为10的数组使用数组下标0的位置空着不用。我推荐第一种因为下标从0开始是程序员最自然的心智模型。第二种也不是不行只是每次都要记得第0个位置是“占位符”代码里多出一些隐含约定。另外要注意这里的ch是字符不是字符串。Python 里ord(ch) - ord(1)返回一个整数Java 里char本身就是整型ch - 1也直接得到整数。一些新手会写出int(ch)这种错误代码试图把字符转成数字。实际上int(5)在 Python 里会抛异常正确姿势是用ord计算字符编码差值。4.2 宫格编号计算的原理与手误案例宫格编号公式(r // 3) * 3 c // 3我已经在前文推导过。但这里有一个很容易手误的细节有些人会写成(r // 3) (c // 3) * 3以为反正都是加和乘顺序无所谓。但实际上两种写法得到的结果完全不同。以(r1, c5)为例正确写法(1 // 3) * 3 (5 // 3) 0 * 3 1 1错误写法(1 // 3) (5 // 3) * 3 0 1 * 3 3一个是第1个宫格一个是第3个宫格显然不对。之所以正确写法要先乘以3再加列偏移是因为我们先把行区间映射到“宫格行编号”再乘以每行的宫格数量3最后再加上列区间偏移。如果调换乘法位置行偏移和列偏移就反了。为帮助记忆可以画一张宫格编号表行区间列区间0-2列区间3-5列区间6-8行区间0-2宫格0宫格1宫格2行区间3-5宫格3宫格4宫格5行区间6-8宫格6宫格7宫格8观察一下第2行的宫格编号从3开始第3行从6开始。这正好对应(r // 3) * 3的效果行区间是0、1、2乘以3后就得到0、3、6。再加上列区间0、1、2就得到每个宫格的唯一编号。4.3 空格、非法字符和输入防御题目约定用.表示空格所以循环里第一步就是if ch .: continue这一点本身不难但很多人会在连续多个判断里漏掉continue导致把.也当成数字处理然后因为ord(.) - ord(1)算出负数而下标越界。代码里务必保证一旦判断为空格就立即跳过后续所有逻辑。关于非法字符比如输入中混入0或者XLeetCode 的原始测试用例里不会出现但这不代表你在真正工程场景中可以忽略。如果这是一段要给别人使用的校验函数我会建议在开头先做一轮正则或者显式字符集合判断if ch ! . and not (1 ch 9): return False这个防御性写法不会影响性能还能避免非法输入导致数组越界。面试时主动写出它也是一种加分表现说明你不只会解“假设输入永远合法”的题目。4.4 一次遍历的边界情况推演为了保险起见可以手动推演一个容易出错的边界情况棋盘第一行前三个格子分别是1、2、3第一列的第四行格子也是1。这时格子(0,0)是1标记rows[0][0]、cols[0][0]、boxes[0][0]为True格子(0,1)是2标记rows[0][1]、cols[1][1]、boxes[0][1]为True格子(0,2)是3标记rows[0][2]、cols[2][2]、boxes[0][2]为True格子(3,0)是1此时rows[3][0]是False不会出问题cols[0][0]已经被格子(0,0)标记为True于是返回False。这个推演过程说明了“一次遍历”如何同时感知多个维度的冲突看似两个数字相隔很远但它们共享同一列所以在cols数组上撞车了。面试时如果你能现场画出类似过程面试官会相信你是真的理解了代码而不只是背答案。类似地如果两个冲突发生在同一个宫格内比如(0,0)和(1,2)都是9它们在boxes数组上的下标都是0同样会被发现。5. 复杂度分析固定9x9的“常数时间”是怎么来的5.1 时间复杂度的双重表达这道题的复杂度分析有一个很有趣的地方标准答案是O(1)但如果你想严谨一点应该先说通用结论再说本题结论。如果把棋盘推广到n x n那么每个格子都要遍历一遍并且每次操作都是O(1)的数组访问或位运算所以时间复杂度是O(n^2)。但题目里的n被固定为9所以代入n 9后O(n^2)的常数上界就是81次操作。在这个意义上整段代码的时间复杂度是O(1)。面试时建议这样回答通用形式下时间复杂度是O(n^2)因为要遍历整个棋盘但在本题中棋盘固定为9x9所以实际复杂度可以看作O(1)。直接上来就说O(1)容易被追问“为什么”只说O(n^2)又忽略了棋盘固定大小这个重要前提。两种说法结合才是完整的答案。5.2 空间复杂度的常数因子差异三种方案的空间复杂度在理论上都是O(1)因为它们都只用了固定数量的辅助结构。但“常数大小”和“常数大小”之间也有差异布尔数组方案3个9x9布尔数组共27个布尔值极小位运算方案3个长度9的整数数组共27个整数极小且比布尔数组更紧凑HashSet 字符串方案最多可能存243个字符串对象。每个字符串拼接会产生临时对象字符串对象本身还有头部元数据、哈希值等实际内存占用可能是数组方案的几十倍。所谓的O(1)只是说明内存占用不随输入规模增长但常数因子在一个9x9的棋盘上可以被拉得很大。如果你在面试中能主动点出这一点比单纯背出“空间复杂度O(1)”要亮眼得多。时间上也有类似的常数差异。布尔数组方案主要做下标访问位运算方案做移位与按位与HashSet方案做字符串拼接和哈希计算。三者在大数据量下会有明显差别但在81个格子的规模里差别微乎其微。因此我的观点是不要为了那点性能差异而牺牲代码清晰度尤其是在面试白板代码的场景里。6. 从算法题到工程实践判重逻辑可以怎么用6.1 数独生成器里的边填边验LeetCode 36 的解题思路最直接的工程应用就是数独生成器。实现数独生成器时你不可能等整个棋盘填充完毕再从头检查。更高效的做法是每填入一个数字就同步验证它是否与当前行、当前列、当前宫格冲突。如果冲突立刻回退并换一个数字。这个“边填边验”的过程用的数据结构与 LeetCode 36 几乎一模一样——三个标记数组每填一格就更新对应维度的标记。我实际写过一个简易数独生成器最初版本就是先随机填完再整体校验结果在冲突严重时大量回溯效率很差。后来改成在每一步都维护“行-列-宫”的判重状态递归回溯时只需要看三个标记数组速度提升非常明显。可以说LeetCode 36 这道题练熟之后数独生成器里最核心的“冲突探测”部分你已经会了。6.2 多维度唯一性约束与幂等判断“多维度判重”是一个比“数独”本身更通用的需求。举个简单的业务场景一个任务调度系统同一台执行器在同一时刻只能运行同一个任务。要判断一条新任务请求是否合法你需要同时检查执行器维度、时刻维度、任务维度。当请求到来时用三个维度拼接出一个唯一标识查一下当前调度表里是否已存在。这和用rows、cols、boxes三组标记做检查本质上是同一个模式。再比如一条日志记录不能在同一批次里出现相同的流水号。单独查“流水号”当然很容易但如果你想表达的是“同一来源、同一接口、同一批次不能重复”就需要把多个维度当成一个联合主键来看待。把这些维度哈希到一个集合中然后逐个判断正是 LeetCode 36 的 Hash Set 解法在真实世界中的映射。6.3 一次遍历思维对日常编码的启发最后我想聊聊“一次遍历”这个思想本身。在 LeetCode 36 里一次遍历之所以可行是因为每个元素同时归属多个集合而我们的任务是检查多个集合内的重复。这种“每个元素都属于多个维度”的结构在计算机系统里太常见了一条数据库记录同时属于某个用户、某个时间分区、某个状态一个网络请求同时属于某个客户端、某个路由、某个协议版本一个文件同时属于某个目录、某个文件类型、某个修改批次。当你习惯用“同时更新所有维度标记”的方式去设计系统你会发现很多原本要写多重循环、多段校验的代码可以被压缩成一层遍历加几个集合/数组。这不是刻意的技巧而是一种结构化的建模方式。LeetCode 36 只是恰好提供了一个最小、最清晰的载体让你练习这种建模。这也是为什么我建议你不要只停留在“背过这个题”而是真的去体会它背后的模式。最后再分享一点我的个人经验刷完这道题后我每次遇到“检查数据是否重复”的需求都会下意识问自己三个问题。第一有多少个维度需要同时检查第二每个维度能否用一个哈希或数组独立表达第三能不能在一次遍历中完成所有维度的更新和判断这三个问题想清楚代码结构往往自己就浮出来了。LeetCode 36 虽然只是算法练习清单里的一道“简单题”但它带来的这种思考方式远比题目本身更有长期价值。 
长河君 · 2026/10/20 22:16:22 · 阅读 1.2k LeetCode 36有效数独：一次遍历的多维判重算法详解
LeetCode 36这道题几乎是每个刷题人都会路过的一站。题目要求很简单判断一个9x9的数独棋盘当前是否“有效数独”。但有意思的是很多人一看到“数独”两个字就开始脑补完整求解算法下意识把问题想复杂了另一些人则相反觉得“不就是检查重复吗”然后栽在3x3小宫格的处理上。我做算法题有个习惯先想清楚这题到底在考什么再动手写代码。这种“多维度判重”的思维后来在我的日常编码里反复用到所以我一直觉得LeetCode 36不是那种刷完就忘的题。这篇文章我想从题目拆解、思路演进、三种实现方式、容易踩的坑以及判重逻辑在工程里的迁移这几个角度把这道题完整聊透希望对正在准备算法面试的你有所帮助。1. 有效数独判定到底在考什么1.1 题目要求中的三个关键维度先看题目描述。输入是一个board二维字符数组尺寸固定是9行9列。每个格子要么是.表示空位要么是数字字符1到9。所谓有效数独只需要满足三个条件每一行里数字1~9至多出现一次每一列里数字1~9至多出现一次每一格3x3小宫格里数字1~9至多出现一次。换言之就是在三个维度上做“查重”。只要发现任意一个维度上有重复立刻返回False全部遍历完没有重复才返回True。这里有一个关键细节题目不要求这个数独最终有没有解也不要求解是否唯一。你只需要判断“已经填进去的数字”之间有没有冲突。换句话说一个棋盘即使完全没法继续填下去只要已填的数字没有在行、列、宫格中重复它仍然是一个“有效数独”。很多人在这里会走偏思考半天回溯求解结果浪费了大量时间。1.2 “判重”与“求解”的边界以及固定9x9的意义完整求解数独是一个经典的回溯问题最坏情况下的搜索空间非常大而判断数独是否有效本质上只是一个“校验”问题不涉及任何搜索。两者完全不在一个量级。而且因为棋盘被固定为9x9每一个维度的检查范围都是常数大小。这意味着即使你的代码写成三层循环嵌套理论上也不会超出81个格子太多。很多面试题会在复杂度分析上设置小陷阱这道题也经常被用来考察候选人能否区分“固定规模”和“输入规模”。如果你能清晰说出“因为棋盘恒定为9x9所以无论怎么写整体操作次数是有上限的复杂度可以看作O(1)”那么往往比直接背诵解法更让面试官满意。不过固定大小也带来一个反直觉的后果由于 n 很小不同解法之间的实际性能差距在 LeetCode 这种评测环境里几乎体现不出来。真正拉开差距的是代码是否简洁、是否容易说明思路、是否能顺手答出变体题目。这也是我接下来要聊的重点思路演进和写法选择。2. 从“找重复”到“高效找重复”思路演进2.1 最直觉的暴力思路三次独立扫描如果第一次接触这道题最自然的想法是分三次扫描先扫描每一行再扫描每一列最后扫描每一个3x3宫格。每次扫描都用一个标记结构记录数字是否出现过。用伪代码表示大概是第一次遍历所有行 对每一行用一个标记数组遇到数字就检查是否重复并标记 第二次遍历所有列 对每一列重复同样的检查 第三次遍历所有宫格 对每个3x3宫格重复同样的检查这个解法最大的优点是不会错。三个维度的逻辑完全独立理解成本低写完后也很难出现“宫格编号算错”这种问题。我第一次按这个思路写的时候几乎是零思考地通过了。但它的缺点也很明显代码重复度高行、列、宫格各写一段几乎一样的逻辑维护起来比较啰嗦。而且在面试场景下面试官通常会追问一句“能不能只用一次遍历完成” 这时候如果只给出三次扫描的方案就显得少了点思考深度。2.2 一次遍历的结构化思考每个格子同时属于行、列、宫一次遍历的核心洞察是遍历棋盘的过程中每遇到一个格子board[r][c]它同时属于第r行、第c列、以及某一个3x3小宫格。所以我们可以同时做三个维度的查重而不是先把行检查完再去检查列。关键问题来了怎么确定当前格子属于哪个宫格假设小宫格用编号0到8表示顺序是从左上到右下。对于格子(r, c)宫格编号 (r // 3) * 3 (c // 3)其中r // 3表示当前行处在哪个“宫格行区间”取值是0、1、2c // 3表示当前列处在哪个“宫格列区间”同样取值0、1、2。把“宫格行区间”乘以3加上“宫格列区间”就得到一个唯一的宫格编号。举个例子格子(4, 7)4 // 3 17 // 3 2所以宫格编号是1 * 3 2 5。这意味着它位于第二行宫格区域、第三列宫格区域也就是中间靠右的那个宫格。这个公式是整道题最容易写错的地方也是很多最优解法的心脏。理解了它后面的代码基本就是顺水推舟。3. 三种主流实现方式与我的选型建议3.1 HashSet字符串法代码最短但开销最大网上很多题解喜欢用一个HashSet把每个数字在哪个维度出现过编码成字符串然后统一存到一个集合里。代码很短def isValidSudoku(board): seen set() for r in range(9): for c in range(9): ch board[r][c] if ch .: continue if f{r}({ch}) in seen or f{c}[{ch}] in seen or f{(r // 3) * 3 c // 3}-{ch} in seen: return False seen.add(f{r}({ch})) seen.add(f{c}[{ch}]) seen.add(f{(r // 3) * 3 c // 3}-{ch}) return True比如r(ch)表示字符ch在第r行出现过c[ch]表示在第c列出现过box-ch表示在某个宫格出现过。只要三个拼出来的字符串中有一个已经在集合里就说明重复。这种方式最大的优点是代码量少、可读性高不用维护三个数组。缺点也同样明显它把字符串拼接和哈希计算的额外开销带进了循环。虽然9x9规模下这点开销完全不是问题但在面试中如果你只写这一种解面试官可能会觉得你只是会调库而不是真正理解多维度判重的本质。我自己刷题时会写这版作为“最直观”的说明但不会停在它上面。3.2 二维布尔数组法面试首选我真正推荐作为面试主答案的方案是三个9x9的布尔数组。这里的逻辑很直接rows[r][num]表示数字num是否已经在第r行出现过cols[c][num]表示数字num是否已经在第c列出现过boxes[box][num]表示数字num是否已经在第box个宫格出现过。def isValidSudoku(board): rows [[False] * 9 for _ in range(9)] cols [[False] * 9 for _ in range(9)] boxes [[False] * 9 for _ in range(9)] for r in range(9): for c in range(9): ch board[r][c] if ch .: continue num ord(ch) - ord(1) box_idx (r // 3) * 3 c // 3 if rows[r][num] or cols[c][num] or boxes[box_idx][num]: return False rows[r][num] True cols[c][num] True boxes[box_idx][num] True return True为什么说它最推荐因为它把“三个维度的查重”用三个数组直白地表达出来每一个操作都有明确的语义。面试官追问细节的时候你很容易解释rows管行、cols管列、boxes管宫格三个条件同时检查只要有一个命中就说明重复。代码不需要魔法技巧也不容易写错。如果你熟悉 Java写法几乎一样public boolean isValidSudoku(char[][] board) { boolean[][] rows new boolean[9][9]; boolean[][] cols new boolean[9][9]; boolean[][] boxes new boolean[9][9]; for (int r 0; r 9; r) { for (int c 0; c 9; c) { char ch board[r][c]; if (ch .) continue; int num ch - 1; int box (r / 3) * 3 c / 3; if (rows[r][num] || cols[c][num] || boxes[box][num]) { return false; } rows[r][num] true; cols[c][num] true; boxes[box][num] true; } } return true; }这里有一个细节值得留意num ch - 1而不是ch - 0。因为字符1的 ASCII 值是490是48。如果减0数字9会得到9数组下标就数到9了但我们的数组长度只有9合法下标是0到8。减1之后1映射到09映射到8正好覆盖9个下标。这个细节非常多的人栽过后文我会专门展开。3.3 位运算压缩法空间和速度的进阶选择如果想把代码写得更有“高端感”可以用位运算把标记数组压缩成一个整数。基本思路是用一个整数的低9位分别表示数字1到9是否出现过。比如最低位表示数字1第二位表示数字2以此类推。def isValidSudoku(board): rows [0] * 9 cols [0] * 9 boxes [0] * 9 for r in range(9): for c in range(9): ch board[r][c] if ch .: continue bit 1 (ord(ch) - ord(1)) box_idx (r // 3) * 3 c // 3 if rows[r] bit or cols[c] bit or boxes[box_idx] bit: return False rows[r] | bit cols[c] | bit boxes[box_idx] | bit return True这里bit 1 (数字映射值)的含义是如果当前数字是5ord(5) - ord(1) 4那么bit就是1 4也就是二进制的10000表示第5位被置1。判断重复时用rows[r] bit如果这一位上已经有过1结果非零说明重复。标记时用rows[r] | bit把这一位置为1。位运算的优势在于空间非常紧凑只用9个整数就行且位运算本身很快。缺点是对新手不太友好容易在和|、的优先级上犯迷糊。我个人的建议是如果你面试时已经顺利写出了布尔数组版时间又充裕可以提一句“其实还可以用位运算压缩空间”然后简单画出思路不必强行写完所有代码。这往往能成为一个加分项但如果一开始就写位运算一旦面试官追问细节你可能会解释得很费劲。3.4 三种方案对比与选型建议方案代码量可读性空间开销时间开销适用场景HashSet字符串法最少较好需存储大量字符串对象常数较大字符串拼接与哈希计算较多快速刷题、思路验证二维布尔数组法中等最好27个长度为9的布尔数组极小数组访问开销低面试讲解、工程校验位运算法短较难27个整数最小位运算最快竞赛写法、资源受限场景如果按“性价比”排序二维布尔数组法毫无疑问是第一选择。它有清晰的语义、极低的出错概率又不会像 HashSet 那样产生不必要的字符串对象。位运算版适合作为补充知识让你对底层的压缩思想有感觉。HashSet 版则可以帮你快速验证思路但不建议作为唯一的面试解。4. 实现细节与容易踩的坑4.1 字符与数字转换的边界这是我见过出错率最高的一处。题目给的是字符数组但你在做标记时希望拿到的是“数字0到8”这样的整数下标。常见的错误是把字符1和整数1混为一谈。正确做法有两种用num ord(ch) - ord(1)得到0到8配合长度为9的数组使用用num ord(ch) - ord(0)得到1到9配合长度为10的数组使用数组下标0的位置空着不用。我推荐第一种因为下标从0开始是程序员最自然的心智模型。第二种也不是不行只是每次都要记得第0个位置是“占位符”代码里多出一些隐含约定。另外要注意这里的ch是字符不是字符串。Python 里ord(ch) - ord(1)返回一个整数Java 里char本身就是整型ch - 1也直接得到整数。一些新手会写出int(ch)这种错误代码试图把字符转成数字。实际上int(5)在 Python 里会抛异常正确姿势是用ord计算字符编码差值。4.2 宫格编号计算的原理与手误案例宫格编号公式(r // 3) * 3 c // 3我已经在前文推导过。但这里有一个很容易手误的细节有些人会写成(r // 3) (c // 3) * 3以为反正都是加和乘顺序无所谓。但实际上两种写法得到的结果完全不同。以(r1, c5)为例正确写法(1 // 3) * 3 (5 // 3) 0 * 3 1 1错误写法(1 // 3) (5 // 3) * 3 0 1 * 3 3一个是第1个宫格一个是第3个宫格显然不对。之所以正确写法要先乘以3再加列偏移是因为我们先把行区间映射到“宫格行编号”再乘以每行的宫格数量3最后再加上列区间偏移。如果调换乘法位置行偏移和列偏移就反了。为帮助记忆可以画一张宫格编号表行区间列区间0-2列区间3-5列区间6-8行区间0-2宫格0宫格1宫格2行区间3-5宫格3宫格4宫格5行区间6-8宫格6宫格7宫格8观察一下第2行的宫格编号从3开始第3行从6开始。这正好对应(r // 3) * 3的效果行区间是0、1、2乘以3后就得到0、3、6。再加上列区间0、1、2就得到每个宫格的唯一编号。4.3 空格、非法字符和输入防御题目约定用.表示空格所以循环里第一步就是if ch .: continue这一点本身不难但很多人会在连续多个判断里漏掉continue导致把.也当成数字处理然后因为ord(.) - ord(1)算出负数而下标越界。代码里务必保证一旦判断为空格就立即跳过后续所有逻辑。关于非法字符比如输入中混入0或者XLeetCode 的原始测试用例里不会出现但这不代表你在真正工程场景中可以忽略。如果这是一段要给别人使用的校验函数我会建议在开头先做一轮正则或者显式字符集合判断if ch ! . and not (1 ch 9): return False这个防御性写法不会影响性能还能避免非法输入导致数组越界。面试时主动写出它也是一种加分表现说明你不只会解“假设输入永远合法”的题目。4.4 一次遍历的边界情况推演为了保险起见可以手动推演一个容易出错的边界情况棋盘第一行前三个格子分别是1、2、3第一列的第四行格子也是1。这时格子(0,0)是1标记rows[0][0]、cols[0][0]、boxes[0][0]为True格子(0,1)是2标记rows[0][1]、cols[1][1]、boxes[0][1]为True格子(0,2)是3标记rows[0][2]、cols[2][2]、boxes[0][2]为True格子(3,0)是1此时rows[3][0]是False不会出问题cols[0][0]已经被格子(0,0)标记为True于是返回False。这个推演过程说明了“一次遍历”如何同时感知多个维度的冲突看似两个数字相隔很远但它们共享同一列所以在cols数组上撞车了。面试时如果你能现场画出类似过程面试官会相信你是真的理解了代码而不只是背答案。类似地如果两个冲突发生在同一个宫格内比如(0,0)和(1,2)都是9它们在boxes数组上的下标都是0同样会被发现。5. 复杂度分析固定9x9的“常数时间”是怎么来的5.1 时间复杂度的双重表达这道题的复杂度分析有一个很有趣的地方标准答案是O(1)但如果你想严谨一点应该先说通用结论再说本题结论。如果把棋盘推广到n x n那么每个格子都要遍历一遍并且每次操作都是O(1)的数组访问或位运算所以时间复杂度是O(n^2)。但题目里的n被固定为9所以代入n 9后O(n^2)的常数上界就是81次操作。在这个意义上整段代码的时间复杂度是O(1)。面试时建议这样回答通用形式下时间复杂度是O(n^2)因为要遍历整个棋盘但在本题中棋盘固定为9x9所以实际复杂度可以看作O(1)。直接上来就说O(1)容易被追问“为什么”只说O(n^2)又忽略了棋盘固定大小这个重要前提。两种说法结合才是完整的答案。5.2 空间复杂度的常数因子差异三种方案的空间复杂度在理论上都是O(1)因为它们都只用了固定数量的辅助结构。但“常数大小”和“常数大小”之间也有差异布尔数组方案3个9x9布尔数组共27个布尔值极小位运算方案3个长度9的整数数组共27个整数极小且比布尔数组更紧凑HashSet 字符串方案最多可能存243个字符串对象。每个字符串拼接会产生临时对象字符串对象本身还有头部元数据、哈希值等实际内存占用可能是数组方案的几十倍。所谓的O(1)只是说明内存占用不随输入规模增长但常数因子在一个9x9的棋盘上可以被拉得很大。如果你在面试中能主动点出这一点比单纯背出“空间复杂度O(1)”要亮眼得多。时间上也有类似的常数差异。布尔数组方案主要做下标访问位运算方案做移位与按位与HashSet方案做字符串拼接和哈希计算。三者在大数据量下会有明显差别但在81个格子的规模里差别微乎其微。因此我的观点是不要为了那点性能差异而牺牲代码清晰度尤其是在面试白板代码的场景里。6. 从算法题到工程实践判重逻辑可以怎么用6.1 数独生成器里的边填边验LeetCode 36 的解题思路最直接的工程应用就是数独生成器。实现数独生成器时你不可能等整个棋盘填充完毕再从头检查。更高效的做法是每填入一个数字就同步验证它是否与当前行、当前列、当前宫格冲突。如果冲突立刻回退并换一个数字。这个“边填边验”的过程用的数据结构与 LeetCode 36 几乎一模一样——三个标记数组每填一格就更新对应维度的标记。我实际写过一个简易数独生成器最初版本就是先随机填完再整体校验结果在冲突严重时大量回溯效率很差。后来改成在每一步都维护“行-列-宫”的判重状态递归回溯时只需要看三个标记数组速度提升非常明显。可以说LeetCode 36 这道题练熟之后数独生成器里最核心的“冲突探测”部分你已经会了。6.2 多维度唯一性约束与幂等判断“多维度判重”是一个比“数独”本身更通用的需求。举个简单的业务场景一个任务调度系统同一台执行器在同一时刻只能运行同一个任务。要判断一条新任务请求是否合法你需要同时检查执行器维度、时刻维度、任务维度。当请求到来时用三个维度拼接出一个唯一标识查一下当前调度表里是否已存在。这和用rows、cols、boxes三组标记做检查本质上是同一个模式。再比如一条日志记录不能在同一批次里出现相同的流水号。单独查“流水号”当然很容易但如果你想表达的是“同一来源、同一接口、同一批次不能重复”就需要把多个维度当成一个联合主键来看待。把这些维度哈希到一个集合中然后逐个判断正是 LeetCode 36 的 Hash Set 解法在真实世界中的映射。6.3 一次遍历思维对日常编码的启发最后我想聊聊“一次遍历”这个思想本身。在 LeetCode 36 里一次遍历之所以可行是因为每个元素同时归属多个集合而我们的任务是检查多个集合内的重复。这种“每个元素都属于多个维度”的结构在计算机系统里太常见了一条数据库记录同时属于某个用户、某个时间分区、某个状态一个网络请求同时属于某个客户端、某个路由、某个协议版本一个文件同时属于某个目录、某个文件类型、某个修改批次。当你习惯用“同时更新所有维度标记”的方式去设计系统你会发现很多原本要写多重循环、多段校验的代码可以被压缩成一层遍历加几个集合/数组。这不是刻意的技巧而是一种结构化的建模方式。LeetCode 36 只是恰好提供了一个最小、最清晰的载体让你练习这种建模。这也是为什么我建议你不要只停留在“背过这个题”而是真的去体会它背后的模式。最后再分享一点我的个人经验刷完这道题后我每次遇到“检查数据是否重复”的需求都会下意识问自己三个问题。第一有多少个维度需要同时检查第二每个维度能否用一个哈希或数组独立表达第三能不能在一次遍历中完成所有维度的更新和判断这三个问题想清楚代码结构往往自己就浮出来了。LeetCode 36 虽然只是算法练习清单里的一道“简单题”但它带来的这种思考方式远比题目本身更有长期价值。