[力扣_36] 有效的数独

题目入口：点击进入

相关算法：

• 暴力迭代(DFS)——
• 时间复杂度：O(1)，因为我们只对 81 个单元格进行了一次迭代。
• 空间复杂度：O(1)

题目描述：

这道题如果做过八皇后的话，就一下子就能想到用DFS，而这题还用不到DFS，只需要去迭代每一个单元格，如果是 '.' 的话，直接跳过，如果是数字的话，就去检查它是否合法即可。

而对于每个单元格内数字的要求，如上图所示，由于数据是有限的，我们可以用数组做Hash表来检查每一个数字的合法性。

我们可以初始化 三个 二维数组：

• row[所在行][对应数字]
• col[所在列][对应数字]
• SamllSudu[所在小数独编号][对应数字]

什么意思呢？我们将 每个 3*3格子的小数独编号，如下所示：

暴力迭代

我们首先将三个二维数组全部初始化为true，然后从 [0,0] 这个格子去迭代检查是否合法即可。

若对应的数字在三个对应的数组中均未出现，则将其标记为false，然后检查下一单元格，如下演示：

代码如下所示：

bool isValidSudoku(char** board, int boardSize, int* boardColSize){
    bool row[9][10];
    bool col[9][10];
    bool Sudoku[9][10];
    for(int i=0;i<9;i++){
        for(int j=1;j<=9;j++){
            row[i][j]=true;
            col[i][j]=true;
            Sudoku[i][j]=true;
        }
    }
    int flag;
    for(int i=0;i<boardSize;i++){
        for(int j=0;j<*boardColSize;j++){
            if(board[i][j]!='.'){
                if(i>=0&&i<3&&j>=0&&j<3) flag=0;
                if(i>=0&&i<3&&j>=3&&j<6) flag=1;
                if(i>=0&&i<3&&j>=6&&j<9) flag=2;

                if(i>=3&&i<6&&j>=0&&j<3) flag=3;
                if(i>=3&&i<6&&j>=3&&j<6) flag=4;
                if(i>=3&&i<6&&j>=6&&j<9) flag=5;

                if(i>=6&&i<9&&j>=0&&j<3) flag=6;
                if(i>=6&&i<9&&j>=3&&j<6) flag=7;
                if(i>=6&&i<9&&j>=6&&j<9) flag=8;

                int sign=board[i][j]-'0';
                 if(row[i][(board[i][j]-'0')]==true && col[j][(board[i][j]-'0')]==true && Sudoku[flag][(board[i][j]-'0')]==true){
                    row[i][board[i][j]-'0']=false;
                    col[j][board[i][j]-'0']=false;
                    Sudoku[flag][(board[i][j]-'0')]=false;

                 }
                 else{
                     return false;
                 }
            }
        }
    }
    return true;
}

炫耀下第一个提交的百分百~

本文链接：