力扣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了。