36.有效的数独

模拟

题目只要求判断当前数独是否合法，不要求真的解出数独。因此只需要按规则检查每个已经填入的数字是否重复出现即可。

数独的合法性有三条约束：同一行不能重复，同一列不能重复，同一个 $3 \times 3$ 宫内也不能重复。遍历棋盘时，遇到数字就分别检查它在对应的行、列、宫中是否已经出现过，如果出现过则直接返回 false；否则标记为已出现。

其中第几个宫可以通过公式 $k = (i / 3) \times 3 + j / 3$ 计算得到。

时间复杂度 $O(1)$

空间复杂度 $O(1)$

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][][] map = new int[3][10][10];// 行 列 块 - 第k个 - 数字是否出现
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] == '.') {
                    continue;
                }
                int num = board[i][j] - '0';
                int k = (i / 3) * 3 + j / 3; // or (i - i % 3) + j / 3
                if (map[0][i][num] > 0 || map[1][j][num] > 0 || map[2][k][num] > 0) {
                    return false;
                }
                map[0][i][num]++;
                map[1][j][num]++;
                map[2][k][num]++;
            }
        }
        return true;
    }
}