友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
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 -
board[i][j]是一位数字（1-9）或者.
思路分析
根据题目要求，对行、列、块三部分分别判断是否含有重复数字即可。
看以前写的解答，也可以将数字抽象成 row(num)、 (num)column 和 row/3(num)column/3，放到一个 Set 集合中。
| 📢：只是判断是否合法即可，不需要去求解！ |
-
一刷
-
二刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Runtime: 5 ms, faster than 21.21% of Java online submissions for Valid Sudoku.
*
* Memory Usage: 43.2 MB, less than 95.65% of Java online submissions for Valid Sudoku.
*
* Copy from: https://leetcode.com/problems/valid-sudoku/discuss/15472/Short%2BSimple-Java-using-Strings[Short+Simple Java using Strings - LeetCode Discuss]
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-06 12:24
*/
public boolean isValidSudoku(char[][] board) {
Set<String> numbers = new HashSet<>(board.length * board.length);
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board[y].length; x++) {
if (!Objects.equals(board[y][x], '.')) {
String value = "(" + board[y][x] + ")";
if (!numbers.add(y + value)
|| !numbers.add(value + x)
|| !numbers.add(y / 3 + value + x / 3)) {
return false;
}
}
}
}
return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-21 21:07:23
*/
public boolean isValidSudoku(char[][] board) {
int length = board.length;
boolean[][] rows = new boolean[length][length];
boolean[][] cols = new boolean[length][length];
boolean[][][] blocks = new boolean[3][3][length];
for (int r = 0; r < length; r++) {
for (int c = 0; c < length; c++) {
char ac = board[r][c];
if (ac == '.') {
continue;
}
int idx = ac - '1';
if (rows[r][idx] || cols[c][idx] || blocks[r / 3][c / 3][idx]) {
return false;
}
rows[r][idx] = true;
cols[c][idx] = true;
blocks[r / 3][c / 3][idx] = true;
}
}
return true;
}