36.有效的数独

题目:有效的数独

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

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

注意：

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

• 示例 1：

输入：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

• 示例 2：

输入：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）或者 '.'

思路

由于只要我们判断是否为有效的数独。

所以我们只需要对 board 中出现的数进行判断，如果 board 中有数违反了数独的规则，返回 false，否则返回 true。

直观上，我们很容易想到使用 哈希表 来记录某行/某列/某个小方块出现过哪些数字，来帮助我们判断是否符合「有效数独」的定义。

这道题唯一的难点可能是在于如何确定某个数落在哪个小方块中，我们可以去小方块进行编号：

然后推导出小方块编号和行列的关系为： boxChar = board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3]
该实现通过三个哈希表来记录数独规则的每一部分是否被违反，确保数独的有效性。时间复杂度为 O(1)，因为我们始终处理固定大小的数独板。空间复杂度也是 O(1)，因为我们使用的辅助数组大小是固定的。

• 时间复杂度:O(1)
• 空间复杂度:O(1)

代码

public boolean isValidSudoku(char[][] board) {
    // 判断行是否有重复
    HashSet<Character> rowSet = new HashSet<>();
    // 判断列是否有重复
    HashSet<Character> lineSet = new HashSet<>();
    // 判断每一个小九宫格是否有重复
    HashSet<Character> boxSet = new HashSet<>();
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[0].length; j++) {
            Character rowChar = board[i][j];
            Character lineChar = board[j][i];
            // 难点
            Character boxChar = board[i / 3 * 3 + j / 3][i % 3 * 3 + j % 3];
            if (rowSet.contains(rowChar) || lineSet.contains(lineChar) || boxSet.contains(boxChar)) {
                return false;
            }
            if (rowChar != '.') {
                rowSet.add(rowChar);
            }
            if (lineChar != '.') {
                lineSet.add(lineChar);
            }
            if (boxChar != '.') {
                boxSet.add(boxChar);
            }
        }
        rowSet.clear();
        lineSet.clear();
        boxSet.clear();
    }
    return true;
}