36. Valid Sudoku
Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.
一道很有意思的题目，要求判断一个9阶矩阵是否是一个合法的数独，对于合法数独的判断规则，总结一下有三点:
- 每行必须由1~9组成，且不重复
- 每列必须由1~9组成，且不重复
- 每个3*3的九宫格必须由1~9组成，且不重复
所以这道题的主要思路就是对每行每列和每个九宫格进行检查，并判断是否符合数独的条件即可。
所以我们需要三个布尔数组用于标记行,列,九宫格是否合法，如果我们发现某一个元素在某行或某列中出现了不止一次，则应该返回false,否则我们继续判断，代码如下：
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
bool rowValid[9][9]={false},colValid[9][9]={false},subBoardValid[9][9]={false};
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
if(board[i][j]!='.'){
int num=board[i][j]-'0'-1;
int k=i/3*3+j/3;/*如果第一格九宫格的编号为0,board[i][j]这个元素存在于第(i/3*3+j/3)个九宫格内*/
if(rowValid[i][num]||colValid[j][num]||subBoardValid[k][num])/*如果在未赋值之前就为true,则说明发生了重复*/
return false;
rowValid[i][num]=colValid[j][num]=subBoardValid[k][num]=true;/*如果未重复，则将其赋值为true*/
}
}
}
return true;
}
};