力扣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 代码：
class Solution {
public boolean isValidSudoku(char[][] board) {
int[][] rows = new int[9][9];
int[][] columns = new int[9][9];
int[][][] arr = new int[3][3][9];
for(int i=0;i<9;i++){
for(int j=0;j<9;j++){
char c = board[i][j];
if(c == '.'){
continue;
}else{
int index = 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)
return false;
}
}
}
return true;
}
}大佬的代码：
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int row[9][10] = {0};// 哈希表存储每一行的每个数是否出现过，默认初始情况下，每一行每一个数都没有出现过
// 整个board有9行，第二维的维数10是为了让下标有9，和数独中的数字9对应。
int col[9][10] = {0};// 存储每一列的每个数是否出现过，默认初始情况下，每一列的每一个数都没有出现过
int box[9][10] = {0};// 存储每一个box的每个数是否出现过，默认初始情况下，在每个box中，每个数都没有出现过。整个board有9个box。
for(int i=0; i<9; i++){
for(int j = 0; j<9; j++){
// 遍历到第i行第j列的那个数,我们要判断这个数在其所在的行有没有出现过，
// 同时判断这个数在其所在的列有没有出现过
// 同时判断这个数在其所在的box中有没有出现过
if(board[i][j] == '.') continue;
int curNumber = board[i][j]-'0';
if(row[i][curNumber]) return false;
if(col[j][curNumber]) return false;
if(box[j/3 + (i/3)*3][curNumber]) return false;
row[i][curNumber] = 1;// 之前都没出现过，现在出现了，就给它置为1，下次再遇见就能够直接返回false了。
col[j][curNumber] = 1;
box[j/3 + (i/3)*3][curNumber] = 1;
}
}
return true;
}
};四、总结：
这道题目本质来说就是寻找数学规律，然后理解高维数组的使用即可轻松AC了。
