36.有效数独

题目

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

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

方法一

对于每一个遍历到的当前元素，需要知道该元素是否之前已在该行，该列，该小方阵里出现过，那么就用一个数据结构来存储这些信息。可以定义三个9*9矩阵RowFlag,ColFlag,CellFlag。RowFlag[i][k]表示第i行是否出现了数字k+1,ColFlag[j][k]表示第j列是否出现了数字k+1,CellFlag[l][k]表示第l个小方阵是否出现了数字k+1。

代码

class Solution {
    public boolean isValidSudoku(char[][] board) {
        int[][] RowFlag=new int[9][9];
        int[][] ColFlag=new int[9][9];
        int[][] CellFlag=new int[9][9];
        for(int i=0;i<9;++i)
            for(int j=0;j<9;++j){
                if(board[i][j]=='.') continue;
                int k=board[i][j]-'1';
                //若当前数字此前已在该行，该列或该单元格出现过，则该数独无效
                if(RowFlag[i][k]==1||ColFlag[j][k]==1||CellFlag[3*(i/3)+j/3][k]==1) return false;
                RowFlag[i][k]=1;
                ColFlag[j][k]=1;
                CellFlag[3*(i/3)+j/3][k]=1;
            }
        return true;
    }
}

方法二

简化存储信息的数据结构，方法一用了3个矩阵来存储这些信息，这里只用一个数据结构存储所有信息。这个数据结构同时存储了该行，该列和该小方阵是否之前就出现过当前数字。
将数字放在一个括号中，每行上的数字就将行号放在括号左边，每列上的数字就将列数放在括号右边，每个小区间内的数字就将在小区间内的行列数分别放在括号的左右两边，这样每个数字的状态都是独一无二的存在，就可以在 HashSet 中快速地查找是否有重复元素存在。

代码

class Solution {
    public boolean isValidSudoku(char[][] board) {
        HashSet<String> set=new HashSet<>();
        for(int i=0;i<9;++i)
            for(int j=0;j<9;++j){
                if(board[i][j]=='.') continue;
                String row=Integer.toString(i)+"("+board[i][j]+")";
                String col="("+board[i][j]+")"+Integer.toString(j);
                String cell=Integer.toString(3*(i/3))+"("+board[i][j]+")"+Integer.toString(j/3);
                if(set.contains(row)||set.contains(col)||set.contains(cell)) return false;
                set.add(row);
                set.add(col);
                set.add(cell);
            }
        return true;
    }
}

原题链接：https://leetcode-cn.com/problems/valid-sudoku
参考：https://www.cnblogs.com/grandyang/p/4421217.html