LeetCode 图解 | 36.有效的数独
- 2020 年 2 月 20 日
- 筆記
以下文章来源于算法无遗策 ，作者我脱下短袖
今天分享一个LeetCode题，题号是36，标题是：有效的数独，题目标签是散列表，散列表也称哈希表。此题解题思路用到了少量的空间换取时间的方法，降低时间上的消耗。
题目描述
判断一个 9×9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 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)要快。
