[力扣_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;
}
炫耀下第一个提交的百分百~