leetcode题集: 36. Valid Sudoku
程序员文章站
2022-07-15 12:28:50
...
第15题:36. Valid Sudoku
题目大意:检查数独是否有效; 即每行,每列和每个3x3小格子是否存在重复的数字。
注意要点:
1. 数独有效并不等同于有解(开始以为是要解出数独,还以为难度有点大)
2. 只有提到的单元需要进行规则检测,也即是row,col和3x3 box需要做这些检测
3. 所给字符只会有数组1-9和 '.'
4. 边界大小9x9
题目分析:题目这么读下来,既然只是检测简单的当前是否有效,而不是数独是否有解,那么思路倒是很清晰的。总共是三个部分需要检测,行,列和3x3格子;既然是检测数字是否重复,我首先想到的就是填表,1-9的数字,由于有多行多列,所以肯定是二维表。那就三个部分分别检测就好了,三个二维表填表;数独边界大小也都固定成了9x9,这意味着行,列,box大小都是9个。直接上代码:
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int row[9][9] = {0};
int col[9][9] = {0};
int box[9][9] = {0}; // 三个二维数组
int tem = 0;
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]=='.') continue;
tem = board[i][j] - '1'; // 将数字字符 1-9 转化成 0-8
row[tem][i]--;
col[tem][j]--;
box[tem][(i/3)*3 + j/3]--; // 二维数组行表示数字,列表示第几行,第几列等
if(row[tem][i]<-1 || col[tem][j]<-1 || box[tem][(i/3)*3 + j/3]<-1)
return false;
}
}
return true;
}
};