36. 有效的数独
2023-05-06 本文已影响0人
红树_
真正的才智是刚毅的志向。 ——拿破仑。
参考36. 有效的数独。
题目
请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。
-
数字
1-9在每一行只能出现一次。 -
数字
1-9在每一列只能出现一次。 -
数字
1-9在每一个以粗实线分隔的3x3宫内只能出现一次。（请参考示例图）
注意：
-
一个有效的数独（部分已被填充）不一定是可解的。
-
只需要根据以上规则，验证已经填入的数字是否有效即可。
-
空白格用
'.'表示。
数独
解题思路
- 枚举：枚举数独时判断对应三条规则是否满足。
枚举
class Solution {
public boolean isValidSudoku(char[][] board) {
for(int i = 0; i < 9; i++) {
int[] count = new int[9];
int[] count2 = new int[9];
for(int j = 0; j < 9; j++) {
// 数字 1-9 在每一行只能出现一次。
if(board[i][j]!='.' && count[board[i][j]-'1']++ == 1) return false;
// 数字 1-9 在每一列只能出现一次。
if(board[j][i]!='.' && count2[board[j][i]-'1']++ == 1) return false;
//数字 1-9 在每一个 3x3 宫内只能出现一次。
if(i%3 == 0 && j%3 == 0) {
int[] count3 = new int[9];
for(int m = i;m < i+3;m++) {
for(int n = j;n < j+3;n++) {
if(board[m][n] == '.') continue;
if(count3[board[m][n]-'1']++ == 1) return false;
}
}
}
}
}
return true;
}
}
复杂度分析
- 时间复杂度：
O(1)，数独长度为9*9=81固定。 - 空间复杂度：
O(1)，使用空间为9固定。
2023.05.07
