【Leetcode】36. 有效的数独

36.有效的数独

解题思路

第一想到的是哈希表，所以给每一行每一列每个九宫格设置一个哈希表，出现数字则标记，如果查询到被标记过的数字，则数独不成立。
每行每列比较简单，设置一个9*10的数组就可以解决，9是数独的行和列，10是数独里面所填的值。比较数独里九宫格里的数就比较复杂，我们可以利用int做除法只能取整的特性求解。
比如第一第二个九宫格
(0,0) -> 0
(0,1) -> 0
(0,2) -> 0
(1,0) -> 0
(1,1) -> 0
(1,2) -> 0
(2,0) -> 0
(2,1) -> 0
(2,2) -> 0

(0,3) -> 3
(0,4) -> 3
(0,5) -> 3
(1,3) -> 3
(1,4) -> 3
(1,5) -> 3
(2,3) -> 3
(2,4) -> 3
(2,5) -> 3

可以看出九个九宫格可以填入9*10的哈希表

代码

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] row = new int[9][10]; // 记录行
        int[][] col = new int[9][10]; // 记录列
        int[][] box = new int[9][10]; // 记录九宫格
        init(row);
        init(col);
        init(box);

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') continue;
                int compare = board[i][j] - '0';
                if (row[i][compare] != 0) return false;
                if (col[j][compare] != 0) return false;
                if(box[i/3+(j/3)*3][compare] != 0) return false; //利用int特性分离九宫格

                row[i][compare]++; // 标记查询过的行
                col[j][compare]++; // 标记查询过的列
                box[i/3+(j/3)*3][compare]++;


            }
        }
        return true;
    }

    // 初始化
    private int[][] init(int[][] matrix) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 10; j++) {
                matrix[i][j] = 0;
            }
        }
        return matrix;
    }
}