LeetCode 36. 有效的数独
目录
题目描述
题意分析
题目给一个 9×9 的棋盘，只要求判断当前已经填好的数字有没有违规，不要求这盘数独最终能不能填完。这是最容易读错的地方：一个合法的局面完全可能是死局，但本题照样返回 true。
违规的定义只有三条，且是并列关系：同一行里出现重复数字、同一列里出现重复数字、同一个 3×3 宫格里出现重复数字。三者任一发生就无效。
约束里的信号非常明确：棋盘尺寸固定是 9×9，格子里只可能是字符
'1'到'9'或者表示空位的'.'。规模固定意味着不需要任何优化技巧，重点在于把「行、列、宫」这三种约束不重不漏地表达出来；字符类型意味着要做一次字符到下标的转换。边界要注意：空位
'.'不参与任何判重，整盘全是'.'时答案是 true；棋盘可能只填了寥寥几个数；重复的两个数可能相隔很远，比如一个在第 0 行第 0 列、另一个在第 2 行第 2 列，行不同列也不同，只有宫相同。
解法：行、列、宫三组标记
核心思路
每个非空数字必须同时满足三条约束：所在行不重复、所在列不重复、所在
3 × 3宫不重复。一次遍历棋盘时，为这三类范围分别维护数字是否出现过即可。数字
'1'到'9'映射为下标 0 到 8。格子(row, col)所在宫的编号为(row / 3) * 3 + col / 3：row / 3是宫的行号，col / 3是宫的列号，再按每行 3 个宫展平成一维编号。扫描到数字时，先检查对应的行、列、宫标记。任一已经出现就说明冲突；否则同时写入三组标记。空格
'.'不参与约束，直接跳过。
解题步骤
- 创建
rows[9][9]、cols[9][9]、boxes[9][9]三组布尔标记。- 逐格扫描棋盘，遇到
'.'直接继续。- 将字符转换为数字下标
num = board[row][col] - '1'。- 计算宫编号
box = (row / 3) * 3 + col / 3。- 若三组对应标记任一为真，立即返回
false；否则把三处都置为真。- 全部扫描完没有冲突则返回
true。
代码实现
class Solution {
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 row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == '.') {
continue;
}
int num = board[row][col] - '1';
int box = (row / 3) * 3 + col / 3;
if (rows[row][num] || cols[col][num] || boxes[box][num]) {
return false;
}
rows[row][num] = true;
cols[col][num] = true;
boxes[box][num] = true;
}
}
return true;
}
}
func isValidSudoku(board [][]byte) bool {
var rows, cols, boxes [9][9]bool
for row := 0; row < 9; row++ {
for col := 0; col < 9; col++ {
if board[row][col] == '.' {
continue
}
num := board[row][col] - '1'
box := row/3*3 + col/3
if rows[row][num] || cols[col][num] || boxes[box][num] {
return false
}
rows[row][num] = true
cols[col][num] = true
boxes[box][num] = true
}
}
return true
}
复杂度分析
- 时间复杂度：$O(1)$，标准数独固定扫描 81 个格子；若棋盘边长记为 $N$，则为 $O(N^2)$。
- 空间复杂度：$O(1)$，三组标记大小固定；推广到边长 $N$ 时为 $O(N^2)$。
关键点总结
- 一个格子同时属于一行、一列、一个宫，因此三类约束可在一次遍历中完成。
- 宫编号公式来自二维宫坐标到一维编号的映射。
- 必须先检查再写标记，否则每个数字都会与自己冲突。
- 题目只要求验证已填数字是否合法，不要求判断棋盘是否可解。
易错点总结
- 宫编号漏乘 3，例如写成
row / 3 + col / 3，会把不同宫错误合并。- 字符减
'0'会让'9'映射到下标 9，正确写法是减'1'。- 忘记跳过
'.'，多个空格会被误判成重复数字。- 三类冲突条件应使用逻辑或；任意一类重复都应立即失败。
- 本题验证的是当前状态，不需要回溯补全空格，那是 37《解数独》的任务。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 37. 解数独 | 困难 | 在本题标记上做回溯填数 |
| 217. 存在重复元素 | 简单 | 一维判重的最简形式 |
| 73. 矩阵置零 | 中等 | 行列标记与原地压缩 |
| 48. 旋转图像 | 中等 | 矩阵下标映射推导 |
| 289. 生命游戏 | 中等 | 邻域约束与状态编码 |