【LeetCode 每日一题】36. 有效的数独

Problem: 36. 有效的数独

整体思路

这段代码的目的是验证一个 9x9 的数独棋盘是否有效。根据数独的规则，一个有效的棋盘（不一定是可解的）必须满足以下三个条件：

1. 每一行中的数字 1-9 都只能出现一次。
2. 每一列中的数字 1-9 都只能出现一次。
3. 每一个 3x3 的子宫格（九宫格）中的数字 1-9 都只能出现一次。

该算法采用了一种非常高效的 “一次遍历，同步检查” 的策略。它通过一次遍历整个棋盘，同时利用三个辅助的二维数组来记录每个数字在行、列和子区域中的出现情况，从而高效地检测重复。

其核心逻辑步骤如下：

1. 数据结构选择（状态记录）：

   • 算法创建了三个 9x9 的布尔二维数组：row, col, 和 area。
   • 这些数组充当了“哈希表”或“集合”的角色，用来记录数字的出现状态：
     • row[i][x] 为 true 表示数字 x+1 在第 i 行已经出现过。
     • col[j][x] 为 true 表示数字 x+1 在第 j 列已经出现过。
     • area[idx][x] 为 true 表示数字 x+1 在第 idx 个 3x3 子区域已经出现过。

2. 单次遍历：

   • 代码使用一个嵌套的 for 循环来遍历棋盘上的每一个单元格，从 (0,0) 到 (8,8)。

3. 单元格处理与检查：

   • 对于每个单元格 (i, j)：
     a. 跳过空格：如果单元格是 .，则直接跳过，继续检查下一个。
     b. 数字转换：将字符数字 '1' 到 '9' 转换为 0 到 8 的索引 x，方便在数组中使用。这是通过 int x = c - '1'; 实现的。
     c. 子区域索引计算：这是算法最巧妙的一步。它通过公式 int idx = i / 3 * 3 + j / 3; 将二维的 (i, j) 坐标映射到一个一维的、范围从 0 到 8 的子区域索引 idx。
     d. 重复性检查：在更新状态之前，进行核心的验证。检查 row[i][x]、col[j][x] 和 area[idx][x] 是否有任何一个已经是 true。如果有，说明当前数字在对应的行、列或子区域中已经出现过，违反了数独规则，因此立即返回 false。
     e. 更新状态：如果检查通过（即没有重复），则将 row[i][x], col[j][x], 和 area[idx][x] 都设置为 true，表示这个数字现在已经在这些位置上被“占用”了。

4. 最终结果：

   • 如果整个 for 循环能够顺利完成而没有触发任何 return false，则说明棋盘上所有已填写的数字都满足数独的三个规则。因此，函数最后返回 true。

完整代码

class Solution {
    /**
     * 验证一个 9x9 的数独棋盘是否有效。
     * @param board 一个 9x9 的字符二维数组，包含数字 '1'-'9' 和 '.'
     * @return 如果数独有效则返回 true，否则返回 false
     */
    public boolean isValidSudoku(char[][] board) {
        // row[i][x] = true 表示数字 x+1 在第 i 行已出现
        boolean[][] row = new boolean[9][9];
        // col[j][x] = true 表示数字 x+1 在第 j 列已出现
        boolean[][] col = new boolean[9][9];
        // area[idx][x] = true 表示数字 x+1 在第 idx 个 3x3 子区域已出现
        boolean[][] area = new boolean[9][9];
        
        // 遍历棋盘的每一个单元格
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                // 如果是空单元格，则跳过
                if (c == '.') {
                    continue;
                }
                
                // 将字符 '1'-'9' 转换为索引 0-8
                int x = c - '1';
                
                // 关键公式：计算当前单元格(i, j)所属的 3x3 子区域的索引(0-8)
                // (i/3) 确定了行的大区域 (0, 1, 2)
                // (j/3) 确定了列的大区域 (0, 1, 2)
                // 两者结合可以唯一确定一个 0-8 的子区域索引
                int idx = i / 3 * 3 + j / 3;
                
                // 核心检查：如果数字 x+1 在当前行、当前列或当前子区域中已存在，则数独无效
                if (row[i][x] || col[j][x] || area[idx][x]) {
                    return false;
                }
                
                // 如果检查通过，则将该数字在对应的行、列和子区域中标记为已出现
                row[i][x] = col[j][x] = area[idx][x] = true;
            }
        }
        
        // 如果成功遍历完整个棋盘，没有发现任何违反规则的地方，说明数独有效
        return true;
    }
}

时空复杂度

时间复杂度：O(1)

1. 循环：代码的主体是一个嵌套的 for 循环，外层循环执行 9 次，内层循环也执行 9 次。
2. 总操作数：循环总共执行 9 * 9 = 81 次。
3. 循环内部操作：在每次迭代中，执行的都是常数时间的操作（数组访问、算术运算、条件判断、赋值）。
4. 综合分析：
   • 由于数独棋盘的大小是固定的 9x9，算法的执行次数是一个常数（81），不随任何变量 N 的变化而变化。
   • 因此，严格来说，其时间复杂度为 O(1)。

空间复杂度：O(1)

1. 主要存储开销：算法创建了三个固定的二维布尔数组 row, col, 和 area。
2. 空间大小：
   • row 数组的大小是 9 * 9 = 81。
   • col 数组的大小是 9 * 9 = 81。
   • area 数组的大小是 9 * 9 = 81。
3. 综合分析：
   • 算法所需的额外空间是一个固定的常数（81 + 81 + 81 = 243 个布尔值），不随任何输入的变化而改变。
   • 因此，其额外辅助空间复杂度也为 O(1)。