LeetCode

20200330

题目 ：有效的数独

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

1. 数字1-9在每一行只能出现一次
2. 数字1-9在每一列只能出现一次
3. 数字1-9在每一个以粗实线分隔的3*3宫内只能出现一次

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例：

输入:
[
  ["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

枚举子数独 ：box_index = (row / 3)*3+columns / 3；

code

class Solution{
    public boolean isValidSudoku(char[][] board){
        //记录
        HashMap<Integer, Integer>[] rows = new HashMap[9];
        HashMap<Integer,Integer>[] columns = new HashMap[9];
        HashMap<Integer,Integer> [] boxes = new HashMap[9];
        
        for(int i=0;i<9;i++){
            rows[i] = new HashMap<Integer,Integer>();
            columns[i] = new HashMap<Integer, Integer>();
            boxes[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 != '.'){
                    int n = (int)num;
                    int box_index = (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);
                    boxes[box_index].put(n,boxes[box_index].getOrDefault(n,0)+1);
                    
                    //判断当前值之前是否出现过
                    if(rows[i].get(n)>1 || columns[j].get(n) > 1 || boxes[box_index].get(n) > 1){
                        return false;
                }
            }
        }
        return true;
    }
}