力扣36. 有效的数独
一、题目描述：
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
注意：
一个有效的数独（部分已被填充）不一定是可解的。只需要根据以上规则，验证已经填入的数字是否有效即可。空白格用 '.' 表示。
示例 1：
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]输出：true示例 2：
输入：board = [["8","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]输出：false解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
提示：
board.length == 9
board[i].length == 9
boardi 是一位数字（1-9）或者 '.'
来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/valid-sudoku著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、思路分析：
这道题考察了什么思想？你的思路是什么？
- 这道题目考察的还是将数学问题建模的能力，另外对多维数组的理解。我们可以了解这个有效的数独需要满足3个条件：
- 数字 1-9 中每一个数字在每一行只能出现一次。
- 数字 1-9 中每一个数字在每一列只能出现一次。
- 数字 1-9 中每一个数字在每一个以粗实线分隔的 3x3 宫内只能出现一次。
- 我们可以用二维数组rows来存储数独中每一行的每个数字出现的次数，用二维数组columns来存储数独中每一列的每个数字出现的次数。那九宫格怎么办呢?这时候就需要用到三维数组了，我们分别使用[i/3]来判断九宫格的行号 ，用[j/3]来判断九宫格的列号。所以可以用三维数组arr[i/3] [j/3] [num] 来记录数字num在九宫格中出现的次数。一旦发现board[i] [j]不是'.'是数字num，就在rows[i] [num-1] columns[j] [num-1] arr[i/3] [j/3] [num-1]的值加一，如果它们值大于1，就返回false。如果遍历结束还未返回false，就返回true咯。
做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？
- 是一次通过的，只要分析清楚了，该题还是没有什么难度的。需要注意index与num之间的转换。数组的下标是从0开始的，而我们的数字是1-9。
有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？
- 我还看到了有位大佬有这样的解法：根据从左到右、从上到下的顺序遍历数组board，即可完成数独3个条件的检验。
三、AC 代码：
classSolution {
publicbooleanisValidSudoku(char[][] board) {
int[][] rows=newint[9][9];
int[][] columns=newint[9][9];
int[][][] arr=newint[3][3][9];
for(inti=0;i<9;i++){
for(intj=0;j<9;j++){
charc=board[i][j];
if(c=='.'){
continue;
}else{
intindex=c-'0'-1;
rows[i][index]++;
columns[j][index]++;
arr[i/3][j/3][index]++;
if(rows[i][index] >1||columns[j][index] >1||arr[i/3][j/3][index] >1)
returnfalse;
}
}
}
returntrue;
}
}
大佬的代码：
classSolution {
public:
boolisValidSudoku(vector<vector<char>>&board) {
introw[9][10] = {0};// 哈希表存储每一行的每个数是否出现过，默认初始情况下，每一行每一个数都没有出现过
// 整个board有9行，第二维的维数10是为了让下标有9，和数独中的数字9对应。
intcol[9][10] = {0};// 存储每一列的每个数是否出现过，默认初始情况下，每一列的每一个数都没有出现过
intbox[9][10] = {0};// 存储每一个box的每个数是否出现过，默认初始情况下，在每个box中，每个数都没有出现过。整个board有9个box。
for(inti=0; i<9; i++){
for(intj=0; j<9; j++){
// 遍历到第i行第j列的那个数,我们要判断这个数在其所在的行有没有出现过，
// 同时判断这个数在其所在的列有没有出现过
// 同时判断这个数在其所在的box中有没有出现过
if(board[i][j] =='.') continue;
intcurNumber=board[i][j]-'0';
if(row[i][curNumber]) returnfalse;
if(col[j][curNumber]) returnfalse;
if(box[j/3+ (i/3)*3][curNumber]) returnfalse;
row[i][curNumber] =1;// 之前都没出现过，现在出现了，就给它置为1，下次再遇见就能够直接返回false了。
col[j][curNumber] =1;
box[j/3+ (i/3)*3][curNumber] =1;
}
}
returntrue;
}
};
四、总结：
这道题目本质来说就是寻找数学规律，然后理解高维数组的使用即可轻松AC了。
