36. 有效的数独

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

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

注意：

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
输入：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：

1
2
3
4
5
6
7
8
9
10
11
12
输入：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）或者 '.'

解题思路：

  1. 分别建立行、列和所在的九宫格box的哈希表来记录元素
  2. 遍历到每个数字board[i][j]的时候，需要判断它是否满足一下三个条件：
    1. 是否在第i行出现过
    2. 是否在第j列出现过
    3. 是否在第index个box中出现过
  3. index的取值
  • 从图中可以看出，box是由i和j共同确定的，对于第一排的三个box，序号是可以通过纵坐标唯一确定的，即j/3,但是第二排就需要用到横坐标了
  • 据观察，同列不同行之间的box的index之间的差为3，第一排可以看做j / 3,则第二排需要在j / 3的基础上加上 3，第三排同理，所以得出 index = j / 3 + i / 3 * 3

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public boolean isValidSudoku(char[][] board) {

    //分别建立关于行、列、九宫格方块的哈希表
    Map<Integer, Set<Integer>> row = new HashMap<>(), col = new HashMap<>(), box = new HashMap<>();


    //存值
    //键为第几行，第几列，第几个，值为当前自己所管理的九个数字
    for (int i = 0; i < 9; i++) {
        row.put(i, new HashSet<>());
        col.put(i, new HashSet<>());
        box.put(i, new HashSet<>());
    }


    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char c = board[i][j];

            if (c == '.') {
                continue;
            }


            //通过字符c - 字符0得到c的int值
            //如'8'的ASCII码为56,'0'的ASCII码为'48','8' - '0' = 8,8为数字8的ASCII码
            int intC = c - '0';


            //由画图可得
            int index = j / 3 + i / 3 * 3;

            //如果已经存在于行列或者九宫格中，则返回false
            if (row.get(i).contains(intC) || col.get(j).contains(intC) || box.get(index).contains(intC)) {
                return false;
            }

            //如果都没有，则存入
            row.get(i).add(intC);
            col.get(j).add(intC);
            box.get(index).add(intC);

        }
    }


    return true;
}