34.有效的数独

题目

请你判断一个 9 x 9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意:

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

输出：true

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

输出：false 解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与示例1 相同。但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示:

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

思路

难点：如何高效记录「某数字在某行/列/宫已出现」？

我们需要三组记录:

每一行已经出现了哪些数字；
每一列已经出现了哪些数字；
每一宫已经出现了哪些数字。

数独有 9 行、9 列、9 个宫，每组各开 9 个集合即可。

最关键的技巧：3x3 宫的编号怎么算？

行、列的索引很直观（就是 i 和 j），但第 (i, j) 个格子属于哪个宫需要一个公式。

把 9 个宫按从左到右、从上到下编号 0~8：

 宫0 | 宫1 | 宫2
-----+-----+-----
 宫3 | 宫4 | 宫5
-----+-----+-----
 宫6 | 宫7 | 宫8

每个宫是 3x3 的，所以:

格子所在的宫行 = i / 3（0、1、2）
格子所在的宫列 = j / 3（0、1、2）
宫编号 = (i / 3) * 3 + (j / 3)

例如 (4, 5):

宫行 4/3=1
宫列 5/3=1
宫编号 1*3+1=4，即宫4。

这个公式是本题的灵魂，务必记住。

class Solution {
    fun isValidSudoku(board: Array<CharArray>): Boolean {
        // 9 行、9 列、9 宫，各开一组集合记录出现过的数字
        val rows = Array(9) { HashSet<Char>() }
        val cols = Array(9) { HashSet<Char>() }
        val boxes = Array(9) { HashSet<Char>() }

        for (i in 0 until 9) {
            for (j in 0 until 9) {
                val c = board[i][j]

                if (c == '.') {
                    // 空格跳过
                    continue
                }

                // 计算所属宫编号
                val boxIndex = (i / 3) * 3 + (j / 3)   

                // 只要在 行 / 列 / 宫 任一处已存在，就重复 → 无效
                if (c in rows[i] || c in cols[j] || c in boxes[boxIndex]) {
                    return false
                }

                // 记录这个数字
                rows[i].add(c)
                cols[j].add(c)
                boxes[boxIndex].add(c)
            }
        }
        return true
    }
}

时间复杂度： O(1)。数独固定是 9x9 = 81 个格子，遍历次数是常数。若推广到 n x n，则是 O(n²)。
空间复杂度： O(1)。记录用的集合/数组大小固定（最多 81 个元素），是常数。推广到 n x n 为 O(n)。
下一题

邮箱：charon.chui@gmail.com
Good Luck!