36.有效的数独

1.题目

去看示例的输入输出

2.解法

class Solution {
    public boolean isValidSudoku(char[][] board) {
        // 行列子数独创建HashMap
        HashMap<Integer, Integer>[] rows = new HashMap[9];
        HashMap<Integer, Integer>[] columns = new HashMap[9];
        HashMap<Integer, Integer>[] childs = new HashMap[9];

        // 每行也是HashMap，用来记录是否有重复的数
        for(int i = 0; i < board.length; i++) {
            rows[i] = new HashMap<Integer, Integer>();
            columns[i] = new HashMap<Integer, Integer>();
            childs[i] = new HashMap<Integer, Integer>();
        }

        // 开始遍历
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) {
                char num = board[i][j];
                // 不能等于空格
                if (num != '.') {
                    // acall码
                    int n = (int)num;
                    // 每3个为一个，所以看有几个3，列直接除就可
                    int k = (i / 3) * 3 + (j / 3);
                    rows[i].put(n, rows[i].getOrDefault(n, 0) + 1);
                    columns[j].put(n, columns[j].getOrDefault(n, 0) + 1);
                    childs[k].put(n, childs[k].getOrDefault(n, 0) + 1);  

                    // 查看之前是否见过
                    if (rows[i].get(n) > 1 || columns[j].get(n) > 1 || childs[k].get(n) > 1) {
                        return false;
                    }

                }
                
            }
            return true;
    }
}

时间复杂度O(1),空间复杂度O(1)
因为数字个数是确定的，都是常量级

3.思考

rows[i].getOrDefault(n, 0) + 1)
这里存入的是出现的次数，第一次出现为1，后面出现一次加1次