[力扣_36] 有效的数独

题目入口:点击进入

相关算法:

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

题目描述:

img

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

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

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

  • row所在行
  • col所在列
  • SamllSudu所在小数独编号

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

img

暴力迭代

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

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

img

代码如下所示:

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;
}

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

img

本文链接:

https://nullcode.fun/83.html
1 + 1 =
快来做第一个评论的人吧~