LeetCode 36. 有效的数独

约 5 分钟
文章信息 13 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 面试经典 150 题 字节 华为 微软 百度 快手 携程 虾皮
标签
数组 哈希表 矩阵

题目描述

✅ 36. 有效的数独

image-20260928221400525

image-20260928221400526

image-20260928221400527

题意分析

棋盘固定为 9 × 9，每个已填数字在所在行、所在列和所在 3 × 3 宫中都不能重复。字符 '.' 代表空格，不参与检查。

题目只验证当前已填数字是否冲突。即使这些数字无法补成完整数独，只要暂时不违反三类规则，也应返回 true，因此不需要搜索空格的填法。

解法：行、列、宫三组标记

核心思路

[!blue]

检查当前数字时，只需要知道它此前是否在同一行、列或宫中出现过，不需要保存出现次数或位置。数字只有 1 到 9，用布尔数组即可分别记录三类信息：rows[row][num] 表示第 row 行出现过数字 num + 1，cols 和 boxes 同理。

每个宫占连续三行、三列，所以 row / 3 和 col / 3 分别是宫的行、列编号，取值均为 0 到 2。把宫的二维坐标按行展开，就得到唯一编号 (row / 3) * 3 + col / 3，范围为 0 到 8。

扫描每个非空格子前，三组标记只包含已经处理的格子。若当前数字的任意对应标记为真，就存在另一个已填格与它违反同一规则，可以立即返回 false。否则将三处标记同时设为真，处理完当前格后，这个不变量仍然成立。

如果棋盘存在重复数字，它们中后扫描到的那个一定会读到先前留下的标记；如果扫描结束仍未发现冲突，就说明每行、每列、每宫都没有重复。这样一次遍历就完整检查了三类约束。

解题步骤

  1. 创建 rows[9][9]、cols[9][9]、boxes[9][9] 三组布尔标记。
  2. 逐格扫描棋盘，遇到 '.' 直接继续。
  3. 将字符转换为数字下标 num = board[row][col] - '1'。
  4. 计算宫编号 box = (row / 3) * 3 + col / 3。
  5. 若三组对应标记任一为真，立即返回 false；否则把三处都置为真。
  6. 全部扫描完没有冲突则返回 true。

减去 '1' 是为了把数字 1 到 9 映射到数组下标 0 到 8。必须先跳过空格，再做转换。全空棋盘没有任何已填数字冲突，会自然返回 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 个格子。
  • 空间复杂度：$O(1)$，三组标记表大小固定。

关键点总结

[!green]

  • 一个格子同时属于一行、一列、一个宫，因此三类约束可在一次遍历中完成。
  • 宫编号公式来自二维宫坐标到一维编号的映射。
  • 必须先检查再写标记，否则每个数字都会与自己冲突。
  • 题目只要求验证已填数字是否合法，不要求判断棋盘是否可解。

易错点总结

[!yellow]

  • 宫编号漏乘 3，例如写成 row / 3 + col / 3，会把不同宫错误合并。
  • 字符减 '0' 会让 '9' 映射到下标 9，正确写法是减 '1'。
  • 忘记跳过 '.'，空格字符减 '1' 后不是合法数字下标，会导致数组越界。
  • 三类冲突条件应使用逻辑或；任意一类重复都应立即失败。
  • 本题验证的是当前状态，不需要回溯补全空格，那是 37《解数独》的任务。

相似题目

题目 难度 关联与区别
37. 解数独 困难 本题只检查已有数字不冲突，原题还要填空并在回溯中维护同样的行列宫约束。
51. N 皇后 困难 同样用独立约束表判断位置能否使用，皇后题的约束是列及对角线。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/70892084
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！