企业官网建设流程全解析

LeetCode 36题“有效数独”是刷题日常里一道非常典型的“看着简单、写起来到处是坑”的题目。题目给你一个9×9的棋盘，里面有些格子填了数字、有些是点号，要求判断目前已经填进去的数字是否满足数独规则：每一行不能有重复数字，每一列不能有重复数字，每一个3×3小宫格里也不能有重复数字。它不要求你判断这个盘面能不能继续填下去，更不需要求出一个可行解——这两个概念很多人一开始会混淆，后面我会专门展开讲。这篇文章的价值在于：你不需要再去找五六篇题解来回对照，我会把HashSet标记法、数组计数法、位运算这三种主流打法一次性讲透，顺手把宫格索引计算、边界判断、面试话术这些“题外话”也一起聊完。如果你正好在准备算法面试，或者只是想把这道Easy题写得又快又漂亮，这篇应该能帮你省下不少时间。

需要先说明的是，这篇不是把官方题解抄一遍。我会站在“踩过坑的过来人”角度，把每个解法为什么这么写、复杂度差在哪、面试官追问时怎么说清楚。你会发现36题虽然只是难度为“简单”的入门题，但它后面藏着的面试考点比想象中要多。

1. 这道题到底在问什么：先别急着写代码

1.1 三个约束条件才是题目的灵魂

数独的经典规则大家从小玩桌游、看报纸都见过：1到9这九个数字，在每一行、每一列、每一个粗线框起来的3×3宫格里都只能出现一次。力扣36题把这套规则凝练成了三个可以编程化的约束条件。

第一个约束是行约束：同一行里不能出现两个相同的数字。第二个约束是列约束：同一列里不能出现两个相同的数字。第三个约束是宫格约束：以三行三列为单位划分出的9个小方格里，也不能出现两个相同的数字。这里的关键词是“冲突”——你只需要检查当前已填数字之间有没有互相撞车。空的格子用'.'表示，它既不属于任何数字，也不参与检查。

于是问题被翻译成一段非常简单的逻辑：遍历所有非空格子，对每个格子同时做三件事——检查它在这一行是否出现过；检查它在这一列是否出现过；检查它所属的3×3宫格里是否出现过。任何一个维度出现过，就说明棋盘无效，直接返回false。全部格子检查完没有冲突，返回true。

这就是这道题的全部核心。

判断“重复”只需要一个能记录状态的数据结构，HashSet、二维数组、位掩码都行。所以三种解法在思路上是完全统一的，只是实现手段不同。很多题解会把这三种方案分开讲，搞得像是三套思路，其实它们共享同一个骨架：一次遍历，同步维护三个维度的状态。

1.2 最容易踩的认知误区：不是叫你去解数独

我接触过不少准备算法面试的候选人，他们一看到“数独”两个字就开始回忆DFS回溯模板，准备写solve函数。实际上题目名称里明确写着“有效数独”，它只是校验盘面，不是求解。有效和可解是两个完全不同的概念。

一个盘面有效，只代表它目前不违反数独规则，不代表你后面能填完；一个盘面可解，则必然有效，因为求解过程中每一步都不能违反规则。举个例子：你可以构造一个填满数字的盘面，它满足每一行、每一列、每一宫都没有重复，但按照数独规则它可能根本推不出来，或者从空盘开始是不可能通过合法步骤到达这个状态的。力扣36题只关心前半句话：当前已填的数字有没有冲突。如果你去写回溯求解，不仅时间复杂度爆炸，而且完全答非所问。

真正的解数独问题，题目描述里会明确让你“填写完整棋盘”，或者明确要求输出一个可行解。36题没有这些字眼，它只问“是否有效”。所以拿到题先读题眼，这是刷题的基本功。那种一看是数独就开始背回溯模板的习惯，在面试里是很危险的。

2. 三种主流解法与完整代码实现

2.1 方案一：HashSet 标记法，最容易读懂

思路：用字符串当标记，把“数字 + 所在行”“数字 + 所在列”“数字 + 所在宫”三个身份拼成唯一的key，放进同一个HashSet里。每次遇到非空数字，就试着把三个key加进去，只要有一个加不进去，说明这个数字已经在对应维度出现过一次，直接返回false。

这种写法的好处是逻辑非常贴近自然语言，几乎不需要注释。你读代码的时候脑子里想的就是“这行有没有重复数字？这列有没有？这个宫有没有？”。坏处是字符串拼接和哈希计算有额外开销，性能上不如数组方案，但作为面试第一版答案完全合格。

class Solution { public boolean isValidSudoku(char[][] board) { Set<String> seen = new HashSet<>(); for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char c = board[i][j]; if (c != '.') { int boxIdx = (i / 3) * 3 + j / 3; if (!seen.add(c + " in row " + i) || !seen.add(c + " in col " + j) || !seen.add(c + " in box " + boxIdx)) { return false; } } } } return true; } }

关键点在于字符串key里必须同时包含“数字”和“维度编号”，否则无法区分不同数字，也无法区分同一数字在不同行、列、宫的归属。key的具体格式可以自己定，只要保证全局唯一。比如用"r" + i + "-" + c、"c" + j + "-" + c、"b" + boxIdx + "-" + c，作用完全一样。注意要避免格式太随意导致两个不同的含义拼成同一个字符串，所以分隔符不要省略。

如果你在本地IDE里直接跑这段代码，记得补import java.util.*;。力扣的代码环境已经默认导入了常用包，但本地不一定，这是我见过不少初学者在本地测试时报错的一个小原因。

2.2 方案二：二维数组计数，面试中最稳

思路：不再用字符串，而是用三个9×9的二维数组rows、cols、boxes，分别记录某个数字在对应行、对应列、对应宫格里已经出现过的次数。遇到数字时先把数组下标换算成0到8，然后检查它所在的行、列、宫三个位置上的计数器是否已经大于0，只要有一个大于0，说明重复，返回false；否则把这三个计数器都置为1。

数组下标换算是个容易踩坑的地方：棋盘里填的是字符'1'到'9'，ASCII码比数字字面量多48，所以c - '1'才能得到0到8。如果用c - '0'会得到1到9，数组越界，这是这个方案里最常见的报错来源。

class Solution { public boolean isValidSudoku(char[][] board) { int[][] rows = new int[9][9]; int[][] cols = new int[9][9]; int[][] boxes = new int[9][9]; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char c = board[i][j]; if (c == '.') continue; int val = c - '1'; int boxIdx = (i / 3) * 3 + j / 3; if (rows[i][val] != 0 || cols[j][val] != 0 || boxes[boxIdx][val] != 0) { return false; } rows[i][val] = 1; cols[j][val] = 1; boxes[boxIdx][val] = 1; } } return true; } }

有人习惯用自增写法，写成if (rows[i][val]++ > 0 || ...)，也可以，但可读性稍差，而且自增发生在短路判断里有副作用，容易让状态记录不完整。我更喜欢先判断再赋1的写法，因为这里只关心“是否出现过”，不是“统计出现次数”。

顺手贴一个Python版本，方便用Python刷题的朋友：

class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: rows = [[False] * 9 for _ in range(9)] cols = [[False] * 9 for _ in range(9)] boxes = [[False] * 9 for _ in range(9)] for i in range(9): for j in range(9): c = board[i][j] if c == '.': continue val = int(c) - 1 b = (i // 3) * 3 + j // 3 if rows[i][val] or cols[j][val] or boxes[b][val]: return False rows[i][val] = cols[j][val] = boxes[b][val] = True return True

Python里直接用布尔二维数组，本质跟Java版本一模一样。如果你平时用Python刷题，可以直接用这个版本。

2.3 方案三：位运算是加分项但不是必须

思路：既然每个数字只有“出现过/没出现过”两种状态，而Java里的int有32位，只用低9位就能代表数字1到9是否出现过。于是每一行只需要一个int，每一列一个int，每一个宫一个int，三个长度为9的int数组就能完成全部状态记录。

检查一个数字是否出现过：先计算它对应的位掩码bit = 1 << (c - '1')，然后看rows[i] & bit是不是0。为0说明没出现过，非0则说明这一行里已经有相同数字了。记录出现：rows[i] |= bit。

class Solution { public boolean isValidSudoku(char[][] board) { int[] rows = new int[9]; int[] cols = new int[9]; int[] boxes = new int[9]; for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { char c = board[i][j]; if (c == '.') continue; int bit = 1 << (c - '1'); int boxIdx = (i / 3) * 3 + j / 3; if ((rows[i] & bit) != 0 || (cols[j] & bit) != 0 || (boxes[boxIdx] & bit) != 0) { return false; } rows[i] |= bit; cols[j] |= bit; boxes[boxIdx] |= bit; } } return true; } }

这里解释一下为什么用1 << (c - '1')：数字'1'对应第0位，'2'对应第1位，……'9'对应第8位。比如遇到'5'，c - '1' = 4，1 << 4等于16，二进制就是10000，代表第4位为1。int总共32位，给9位用绰绰有余。

位运算方案在普通算法题里不算常见，但数独这种“状态只有0和1”的校验场景非常契合。面试时如果你能主动从数组方案演进到位运算，说明你对空间复杂度有意识，这是加分项。但也别为了炫技而用它，如果你自己解释不清楚位运算的原理，面试官追问两句就容易翻车。先把数组方案写对，再提“还可以进一步用位运算优化”，这是最稳妥的展示方式。

3. 复杂度分析与方案取舍：别只看大O

3.1 时间、空间复杂度对照

三种方案的代码都只有一个双层循环，遍历9×9共81个格子，每个格子做常数时间操作，所以时间复杂度都是O(81)。严格按n×n数独泛化就是O(n²)。差别主要藏在常数因子和空间占用上。

如果按通用的n×n数独来讨论，HashSet最坏情况要存大约3×n²个key，空间O(n²)；二维数组也是三个n×n的数组，O(n²)；位运算只需要三个长度为n的数组，O(n)。在面试中如果被问到“怎么扩展到12×12或者16×16的数独”，位运算的空间优势就会体现出来。

复杂度这里说“O(81)”听上去有点滑稽，因为输入规模是固定的，所以不少题解干脆说O(1)。不过面试时我更建议你直接说O(n²)/O(n)，并且补一句“本题n固定为9”。这样既体现抽象能力，也不会因为死板地说O(1)被面试官纠正。

3.2 什么时候用哪种方案更合适

我的判断是：第一轮写HashSet，第二轮主动优化成数组，如果面试官对空间敏感，再补位运算。别一上来就写位运算，除非你平时刷题就是这种风格，否则容易给人一种“背题”的印象。

HashSet方案最大的价值是“好讲”。你可以在写代码之前先用它把思路完整地说一遍：三个维度、一组key、一个set。讲清楚再动手，就算后面换成了别的实现，面试官也已经对你的思路有了好印象。

实际跑性能的话，这三种方案在力扣评测环境里都能在几毫秒内完成，差距几乎可以忽略不计，评测波动本身都经常超过这个范围。所以真正影响面试结果的不是快那1毫秒，而是你能不能把方案讲明白，以及能不能说出各自的取舍。

工程代码里我倾向用数组计数法，原因很简单：不依赖String对象创建和哈希桶，逻辑直白，后续维护的人不用查资料就能看懂。位运算适合作为内部状态封装在特定模块里，配合注释使用，但尽量不要裸写在业务代码里吓唬同事。

4. 宫格索引计算的完整拆解

4.1 为什么是 (i / 3) * 3 + j / 3

我见过不少人在这道题上唯一卡住的地方就是这个宫格编号。明明行和列都好理解，一到box就不知道当前格子属于第几个小方块。

把9×9棋盘想象成三层楼，每层三个房间。i / 3得到的是行方向上的“楼层”：0到2行属于第0层，3到5行属于第1层，6到8行属于第2层。j / 3得到的是列方向上的“房号”：0到2列是第0间，3到5列是第1间，6到8列是第2间。楼层乘3，代表每一层有三个房间，然后加上房号，就得到0到8的全局房间号。

举例：坐标(4, 7)。i = 4, i / 3 = 1，说明它在中间那一层；j = 7, j / 3 = 2，说明它是这层最右边的房间，所以boxIdx = 1×3 + 2 = 5。坐标(6, 1)。i / 3 = 2, j / 3 = 0，boxIdx = 2×3 + 0 = 6。坐标(0, 8)。i / 3 = 0, j / 3 = 2，boxIdx = 2。这几个例子手算一遍，基本就不会再错了。

我整理了一张对应关系表，方便自查：

把这张表背下来不如自己推导一遍。我强烈建议你在本地写一个三层循环打印i, j, boxIdx，然后人工确认每个boxIdx都出现了9次。这个过程花不了两分钟，但对理解帮助很大。

4.2 常见错误与自查方法

最常见的手误是写成i / 3 + j / 3。这个表达式的取值范围只有0到4，不是9个宫格，而且不同位置会算出同一个编号。比如(3,3)和(0,6)按这个公式都算成1，但它们分别是第3号宫和第2号宫，关键坐标一旦算错，重复校验就漏了。还有人会写成i * 3 + j / 3，取值能到24，更是错得离谱。

判断宫格编号是否正确，有一个很有效的自查方法：把所有格子遍历一遍，统计每个boxIdx出现次数。如果每个编号恰好9次，说明公式没问题；如果某些编号次数不对，立即检查公式。

另一个容易忽视的点：不管棋盘怎么填，宫内编号公式只依赖坐标，不依赖数字。所以在只有一个循环遍历所有格子的版本里，这个公式必须放在循环内部对每个格子都算一次，不能图省事提出来只算一次。

5. 边界情况与典型错误排查实录

5.1 高频翻车点清单

我结合自己带人、看题解、以及在社区看别人讨论的经验，把这道题最容易翻车的点整理成了一张清单：

这里面“三个维度分别遍历”是我见过最多的非报错型问题。它能跑通，时间上也能过，但代码要写三套循环，每套循环内部还得判断空位，啰嗦得很。我建议从一开始就养成“一次遍历，三个状态同步更新”的习惯，这也是这题最值得复习的价值点。

另外还有一个关于输入规模的默认前提：题目给定棋盘固定是9×9，代码里可以直接写死9。但如果实际工程中传入的棋盘不是9×9，这个代码就会越界。力扣的测试用例都保证了输入合法，所以刷题时不用处理这个问题，但如果你要把它沉淀成通用工具组件，就需要在入口处加一个尺寸校验。

5.2 现场排查思路演示

假设你写完了代码，提交之后发现某个用例返回true但预期是false。这时候不要瞎猜，按下面的思路走。

第一步，看那个用例里是否有明显的重复数字，手动扫一眼棋盘的某一行或某一列。第二步，如果是行或列有重复，直接在对应循环里打印那一行或列的数字序列，确认问题是不是出在判断逻辑。第三步，如果肉眼没看出来，大概率问题出在宫格编号。你可以在循环里加上一句System.out.println(i + "," + j + " -> box " + boxIdx);，把整个棋盘的坐标和box对应关系打印出来，和前面那张表对照，差一个都说明公式错了。

我举个例子：如果board里(0,2)和(2,0)都是'5'，它们实际上都属于第0号宫，所以应该判false。如果你算出来的boxIdx一个0一个2，那校验就会漏掉它。打印一次坐标映射，问题立刻现形。

还有一种隐蔽情况：数字在行、列、宫三个维度同时出现，比如一个'7'在第1宫，另一个'7'也在第1宫，但同时它们还处在同一行——这时候不管哪个判断先命中，都会返回false，结果还是对的。但如果宫格编号算错了，第一维命中了而第二维没命中，结果就可能变成true。所以排查时优先怀疑宫格，因为它最反直觉。

6. 面试中的沟通技巧与工程化扩展

6.1 怎么写代码才能让面试官眼前一亮

回到这道题在面试场景里的定位。它通常出现在第一轮很靠前的位置，充当热身题或者压力题。面试官真正想看的不是你会不会背题解，而是三件递进的东西：你有没有先澄清题意，你能不能把思路讲清楚，你能不能写出结构干净的代码。

我建议的答题节奏是：先问“棋盘一定是9×9吗？空位是不是用'.'表示？”这种澄清问题，哪怕你已经看过原题，问一下也不多余。然后一句话概括方案“我打算一次遍历，对每个格子同时检查它所在的行、列、宫，用哈希集合记录状态”。再开始写代码。写完后主动分析复杂度，并说“目前这个版本用HashSet，如果希望省空间，可以换成三个二维数组，甚至进一步用位运算”。

这一套下来，面试官对你的评价会是“思路清晰、基础扎实”。如果你一上来就憋着头写位运算，写的时候还在算1 << 7等于多少，反而显得不稳。

另外一个小技巧：代码里布尔返回值不要写得花里胡哨。我见过有人用return true;只在最后出现，中间全是return false;，这是标准模式，很好。但也有人为了少写几行硬把多个条件用位运算凑在一起，结果面试官一时没看懂，你还得额外解释半天。代码是写给面试官看的，简洁比炫技重要。

6.2 从这道题延伸到真实工程场景

一个完整数独功能的校验模块通常不只做全量校验，更多时候需要增量校验。比如用户在App里往某个格子填了一个数字，后端只需要判断这个数字跟它所在行、列、宫是否冲突，而不是重新扫描整个棋盘。在这个场景下，位运算方案的价值立刻体现出来：提前把每一行、每一列、每一宫的掩码存在缓存里，用户填数字时O(1)完成检查，填完再更新对应掩码。如果用HashSet方案，你至少要新建三个Set并遍历整行、整列、整宫，成本跟写一次全量校验差不多。

再比如把数独校验从9×9泛化成不规则的宫格布局。只要宫格是规整的矩形，你可以把固定数字3抽成两个参数：宫高和宫宽。遍历时用boxRow = i / boxHeight、boxCol = j / boxWidth、boxIdx = boxRow * (9 / boxWidth) + boxCol来动态计算。这类改动在工程里随处可见，面试时如果能主动提一句“如果宫格大小可变，公式需要参数化”，也说明你不是只会背模板。

还有一个常见的衍生题：给一个长度为81的字符串，代表逐行拼接的数独棋盘，要求判断是否有效。本质上就是在遍历时把一维下标换算成二维坐标：i = idx / 9、j = idx % 9。掌握了二维版本，这种变体基本是白送的。

我个人在实际写这道题时的习惯，是把三种方案都放在同一个文件里，用参数切换。不是为了炫技，而是方便自己对比测试各种输入。遇到真实项目里有校验需求，我大概率会直接抽一个基于位运算掩码的Validator接口，配合注释使用。这样既能保持性能，也让后来接手的人看得懂。