LeetCode 图解 | 36.有效的数独
LeetCode 图解 | 36.有效的数独
以下文章来源于算法无遗策 ，作者我脱下短袖
今天分享一个LeetCode题，题号是36，标题是：有效的数独，题目标签是散列表，散列表也称哈希表。此题解题思路用到了少量的空间换取时间的方法，降低时间上的消耗。
题目描述
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
数独
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例 1:
输入:
[
["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:
输入:
[
["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 存在, 因此这个数独是无效的。说明:
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 '.' 。
给定数独永远是 9x9 形式的。解题
此题没有要求数独是可解的，只要求满足以下规则，验证已经填入的数字是否有效即可：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。行的下标设为i，列的下标设为j，宫格的下标设为k，默认为0，如下图：
行、列和宫格
随着下标i和下标j的移动，i和j可以直接从下标中获取数字，但k如何获取对应的数字呢？看上面图，k随着i变化和k随着j变化都有规律的，不多说，直接给公式：k = (int)(i / 3) * 3 + (int)(j / 3)。
根据规则，某数字的三个下标都只能出现一次，例如8：[0，0，0]，往后这个数组里就不能再出现0了，有0出现就不符合有效数独的规则了；再例如3：[0，1，0]，i下标和k下标不能再出现0了，j下标不能再出现1了。
但怎么判断某数字的三个下标是否是只出现了一次呢？
题目标签只有散列表，那正合我意，我就是要用散列表去解决此题。而且数组里的值最小是0，最大值是8，数组的长度都固定为3，可以用少量的空间换取时间的方法，如下图8：[0，0，0]的表示：
空间换时间
这样就减少了两个数组比较的烦恼，通过空间换取时间的方法，就减少了不必要的比较计算。因为行i、列j和宫格k的长度都是9，将二维数组摊开作为一维数组，下标i、下标j+9和下标k+18分别控制一维数组的下标，存放的值都是布尔类型，默认为false。
保存某数字的时候，一维数组的下标i、下标j+9和下标k+18的值都变为true。保存某数字之前，需要判断三个下标的值是否存在true，如果不存在，则将三个下标对应的值都变为true；如果存在，说明某下标已经出现一次了，再出现一次则意味着这个数独已经无效，直接返回false。如下图数字8的下标k已经出现一次了。
失效的数独
动画：使用散列表
Code：使用散列表
public boolean isValidSudoku(char[][] board) {
// 创建散列表
Map<Integer, boolean[]> map = new HashMap<>();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
// 字符的ASCII码 十进制
int index = board[i][j];
// 创建宫格标记
int k = i / 3 * 3 + j / 3;
// 空间换取时间
if (!map.containsKey(index)) {
map.put(index, new boolean[27]); // 27个空间默认放false
}
// 获取散列表的值
boolean[] booleans = map.get(index);
if (booleans[i] == true || booleans[j + 9] == true || booleans[k + 18] == true) {
return false;
} else {
booleans[i] = true;
booleans[j + 9] = true;
booleans[k + 18] = true;
}
}
}
}
return true;
}
public static void main(String[] args) {
char[][] 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'}
};
boolean validSudoku = new Solution().isValidSudoku(board);
System.out.println(validSudoku);
}时间复杂度
时间复杂度是O(n)，但实际上比O(n)要快。
腾讯云开发者
