Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules :
Each row must contain the digits 1-9 without repetition.
Each column must contain the digits 1-9 without repetition.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Copy Input: 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"]]
Output: true Example 2:
Copy Input: 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"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Constraints:
board[i][j] is a digit 1-9 or '.'.
Solution:
https://www.jiuzhang.com/problem/valid-sudoku/
解题思路
这题考查的是二维数组的遍历顺序。
判断每一行是否合法，外层循环枚举行，内层循环枚举列。
判断每一列是否合法，外层循环枚举列，内层循环枚举行。
判断每一块是否合法，每一块左上角的坐标都是(0, 0), (3, 0), (6, 0), (3, 0), (3, 3) ...，可以发现都是3的倍数，可以总结出规律，先枚举i = [0, 1, 2]，再枚举j = [0, 1, 2]，左上角坐标就是(i**3, j****3)。
代码思路
利用一个set来记录已经被用过的数，每次遍历一行，一列，一块，将访问过的元素加入set，冲突的话，返回false退出。最后返回true。
复杂度分析
假设这是一个N * N的数独，不止是9 * 9。
时间复杂度
空间复杂度
源代码
javac++python
Copy public class Solution {
/**
* @param board: the board
* @return: whether the Sudoku is valid
*/
public boolean isValidSudoku(char[][] board) {
Set<Character> used = new HashSet();
// 先枚举行，检查每行是否合法
for (int row = 0; row < 9; row++) {
used.clear();
for (int col = 0; col < 9; col++) {
if (! checkValid(board[row][col], used)) {
return false;
}
}
}
// 先枚举列，检查每列是否合法
for (int col = 0; col < 9; col++) {
used.clear();
for (int row = 0; row < 9; row++) {
if (! checkValid(board[row][col], used)) {
return false;
}
}
}
// 每个分块的左上角的坐标为(i * 3, j * 3)
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
used.clear();
for (int row = i * 3; row < i * 3 + 3; row++) {
for (int col = j * 3; col < j * 3 + 3; col++) {
if (! checkValid(board[row][col], used)) {
return false;
}
}
}
}
}
return true;
}
// 检查字符是否有冲突
boolean checkValid(char c, Set<Character> used) {
if (c == '.') {
return true;
}
if (used.contains(c)) {
return false;
}
used.add(c);
return true;
}
} 