有效的数独(leetcode36)

Vincent-yuan

发布于 2021-04-09 07:14:24

39800

代码可运行

文章被收录于专栏：Vincent-yuanVincent-yuan

运行总次数：0

代码可运行

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

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

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

示例 1:

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

解析：

最简单的思路，是遍历9x9的数独三次，确保：

行中没有重复的数字
列中没有重复的数字
3x3 子数独没有重复数字

但是，实际上，它们都可以放到一次迭代。

我们只需要记录对应的三种情况中数字出现的次数，如果次数大于1，说明数独无效，返回false。

即：遍历数独，检查每个单元格中的值是否已经在当前的行 / 列 / 子数独中出现过。

public class Leetcode36 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        char[][] board = new char[9][9];
        board[0]=new char[]{'5','3','.','.','7','.','.','.','.'};
        board[1]=new char[]{'6','.','.','1','9','5','.','.','.'};
        board[2]=new char[]{'.','9','8','.','.','.','.','6','.'};
        board[3]=new char[]{'8','.','.','.','6','.','.','.','3'};
        board[4]=new char[]{'4','.','.','8','.','3','.','.','1'};
        board[5]=new char[]{'7','.','.','.','2','.','.','.','6'};
        board[6]=new char[]{'.','6','.','.','.','.','2','8','.'};
        board[7]=new char[]{'.','.','.','4','1','9','.','.','5'};
        board[8]=new char[]{'.','.','.','.','8','.','.','7','9'};
        
        boolean result = isValidSudoku(board);
        System.out.println(result);
    }

    public static boolean isValidSudoku(char[][] board) {
        //初始化数据
        HashMap<Integer,Integer>[] rows = new HashMap[9];
        HashMap<Integer,Integer>[] columns = new HashMap[9];
        HashMap<Integer,Integer>[] boxs = new HashMap[9];
        
        for(int i=0;i<9;i++){
            rows[i] = new HashMap<Integer,Integer>();
            columns[i] = new HashMap<Integer,Integer>();
            boxs[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);
                    boxs[box_index].put(n, boxs[box_index].getOrDefault(n, 0)+1);
                    
                    //检查是否有值之前已经出现过
                    if(rows[i].get(n)>1||columns[j].get(n)>1||boxs[box_index].get(n)>1){
                        return false;
                    }
                }
            }
        }
        
        return true;
    }
}