LeetCode 36中等矩阵 · 哈希查重
有效的数独 图解题解
数独合法性验证，难点不是规则复杂，而是行、列、宫三个维度得同时查——一趟遍历搞定。
监考老师检查答题卡有没有填错：每格数字要同时过三关——这一行没重复、这一列没重复、这个小九宫没重复。老师备三本点名册（行/列/宫各一本），逐格核对，见到数字就查三本册子，没重复才记上去，有重复立刻判无效。一次遍历所有 81 格，三维同时查，完全不需要分三次扫。
这道题到底在问什么
判断一个 9×9 数独棋盘是否有效，只需要检查已填数字。
- board
- 含 5、3、7 等已填数字
- 输出
- true
最优解：一步一步想明白
- 3一个格子 (r,c) 的宫编号是 (r//3, c//3)，也可以压成 (r//3)*3 + c//3。
- 4放入 row0/col0/box0遇到数字 5，检查行、列、宫都没见过，再记录进去。
- 5row0 加 3同一行已有 5，但没有 3，所以合法。
- 6"." 不检查空格还没填，不影响合法性。
- 7box1 加 1每个数字同时检查三个维度。
- 8col1 已有 3，不冲突同列不同数字没问题。
- 9左上宫有 5/3/6/9/8宫的范围由 r//3 和 c//3 决定。
- 10同一行再出现 5如果 row0 已有 5，再遇到 5 就直接 false。
- 11同一列重复也 false负例·列重复：把 (8,0) 填成 5，但第 0 列已有 (0,0)=5 → 同列重复，直接 false。
- 12没有重复则 true整个棋盘扫描结束都没冲突，返回 True。
- 15把约束拆成三个哈希集合，冲突就会非常直观。
⚠️ 容易写错的地方
✗ 错：把 "." 也放进集合
✓ 对：空格必须跳过
多个空格不是重复数字
✗ 错：宫编号算错
✓ 对：b=(r//3)*3+c//3
同一个 3×3 宫必须落到同一个编号
完整代码（Python / C++ / Java）
Python
class Solution:
def isValidSudoku(self, board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
x = board[r][c]
if x == ".": continue
b = (r // 3) * 3 + c // 3 # 宫编号
if x in rows[r] or x in cols[c] or x in boxes[b]:
return False
rows[r].add(x); cols[c].add(x); boxes[b].add(x)
return TrueC++
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<set<char>> rows(9), cols(9), boxes(9);
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
char x = board[r][c];
if (x == '.') continue;
int b = (r / 3) * 3 + c / 3; // 宫编号
if (rows[r].count(x) || cols[c].count(x) || boxes[b].count(x)) return false;
rows[r].insert(x); cols[c].insert(x); boxes[b].insert(x);
}
return true;
}
};Java
class Solution {
public boolean isValidSudoku(char[][] board) {
Set<Character>[] rows = new HashSet[9], cols = new HashSet[9], boxes = new HashSet[9];
for (int i = 0; i < 9; i++) { rows[i]=new HashSet<>(); cols[i]=new HashSet<>(); boxes[i]=new HashSet<>(); }
for (int r = 0; r < 9; r++)
for (int c = 0; c < 9; c++) {
char x = board[r][c];
if (x == '.') continue;
int b = (r / 3) * 3 + c / 3; // 宫编号
if (!rows[r].add(x) || !cols[c].add(x) || !boxes[b].add(x)) return false;
}
return true;
}
}套路模板 · 多维约束查重
class Solution:
def valid(self, grid):
seen_a = set()
seen_b = set()
seen_c = set()
for item in items:
key1, key2, key3 = make_keys(item)
if key1 in seen_a or key2 in seen_b or key3 in seen_c:
return False
seen_a.add(key1)
seen_b.add(key2)
seen_c.add(key3)
return True复杂度
时间复杂度
O(1)
固定 9×9=81 格，每格 O(1) 检查
空间复杂度
O(1)
三组常数大小的集合
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 有效的数独 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
核心思路是什么？+
遍历每个已填数字，检查它在所在行、列、3×3 宫是否已出现；用三组哈希集合记录，任一处重复即 false。
3×3 宫怎么定位？+
宫编号 b=(r//3)*3+c//3，把 (r,c) 映射到 0~8；同一个宫的格子算出同一个 b。
复杂度？+
固定 81 格、每格 O(1) 检查 → 时间 O(1)、空间 O(1)（常数大小集合）。也可用 9 个 int 位掩码代替集合更省。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。