有效的数独
在 LeetCode 上查看 ↗语音讲解
开车或通勤时可听，跟着思路走一遍
题目描述
请你判断一个 9×9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字
1-9在每一行只能出现一次。 - 数字
1-9在每一列只能出现一次。 - 数字
1-9在每一个以粗实线分隔的3×3宫内只能出现一次。
注意：一个有效的数独（部分已被填充）不一定是可解的；只需验证已填数字是否违反规则；空白格用 '.' 表示。
示例 1
示例 2
3×3 宫内有两个 8，违反宫格规则。模拟答题者思考
1. 我先想暴力：对每个已填数字，分别检查它所在行、列、3×3 宫有没有重复——每格要扫最多 9 个邻居，整体约 O(81×9)，虽能过但重复劳动多。
2. 重复在哪里？每往右/往下扫一格，其实只是在问：「这个数字在我已经看过的同行/同列/同宫里出现过吗？」——本质是集合查重，不必每次重新遍历整行整列。
3. 关键转化：开 9 个行集合、9 个列集合、9 个宫集合；扫到 (i,j) 的数字 c 时，算宫号 b=(i//3)*3+j//3，若 c 已在 rows[i]/cols[j]/boxes[b] 任一集合中则立即 false，否则三处都加入 c。
4. 例 2 左上角宫：先记入 8,3，再扫到第二个 8 时 boxes[0] 已有 8，直接判无效——不必解完整数独。
5. 棋盘固定 9×9，最多 81 格、每格 O(1) 查集合，总复杂度 O(1)；空间也是 27 个小集合的常数级。
变量语义（先读这三句再编码）
| 变量 | 类型 | 语义（三句法） |
|---|---|---|
rows[i] | set<char> × 9 | 定义：第 i 行已出现过的数字集合维护：扫描到 (i,j) 时，rows[i] 恰好包含该行 j 左侧及当前格的所有非空数字更新：遇到数字 c 时，若 c in rows[i] 则非法，否则 rows[i].add(c) |
cols[j] | set<char> × 9 | 定义：第 j 列已出现过的数字集合维护：与行对称，保证列内 1-9 不重复更新：同上，重复则返回 false，否则加入集合 |
boxes[b] | set<char> × 9 | 定义：第 b 个 3×3 宫格已出现过的数字集合，b = (i//3)*3 + j//3维护：每个宫格独立维护，与行、列约束并行检查 更新：若 c in boxes[b] 则非法，否则 boxes[b].add(c) |
c = board[i][j] | char | 定义：当前格字符，'.' 表示空白维护：仅对 '1'..'9' 执行去重检查，空白格直接跳过更新：双重循环逐格推进，每遇到一个数字同时查行、列、宫三套集合 |
落码步骤
1. 初始化 rows, cols, boxes 为 9 个空集合
2. 双重循环遍历每个格子 (i, j)
3. 若 board[i][j] == '.' 跳过；否则令 c = board[i][j]，b = (i//3)*3 + j//3
4. 若 c 已在 rows[i]、cols[j] 或 boxes[b] 中，返回 false
5. 否则将 c 同时加入三个集合；全部扫完返回 true
代码实现
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):
c = board[i][j]
if c == '.':
continue
b = (i // 3) * 3 + j // 3
if c in rows[i] or c in cols[j] or c in boxes[b]:
return False
rows[i].add(c)
cols[j].add(c)
boxes[b].add(c)
return Trueclass Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
vector<unordered_set<char>> rows(9), cols(9), boxes(9);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c == '.') continue;
int b = (i / 3) * 3 + j / 3;
if (rows[i].count(c) || cols[j].count(c) || boxes[b].count(c))
return false;
rows[i].insert(c);
cols[j].insert(c);
boxes[b].insert(c);
}
}
return true;
}
};
// 时间 O(1)，空间 O(1)（棋盘规模固定）复杂度分析
O(1)
O(1)
常见坑
宫格编号公式写错：应是 (i//3)*3 + j//3，不是 i//3 + j//3 或 (i%3)*3 + j%3 的误用。
本题只验证合法性，不要求可解；看到矛盾直接 false，不要尝试回溯填数。
字符类型是 '1'..'9' 和 '.'，不要当成 int；空白格必须跳过，否则会把 '.' 当数字处理。
必测边界 Case
board 全是 '.' → true（无冲突可判）
同一行两个 '5' → false
左上角 3×3 宫两个 '8' → false
同一列两个 '7' → false
已填数字互不冲突即可返回 true，不要求能填满全盘