36. 无效的数独
题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/valid-sudoku
题目
判断一个 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 宫内只能呈现一次。
那么咱们能够依据这个规定，遍历给定的数独三次，别离去判断每行，每列，每个 3x3 宫内是否有反复的数字。如果有反复的数字，能够间接返回 False；否则，直至遍历完结，返回 True。
然而在这里，能够思考遍历一次，同时去判断每行，每列，每个 3x3 宫内是否有反复的数字。
在这里，咱们应用哈希表去存储每个数字呈现的次数（包含每行，每列，每个 3x3 宫）。在这里次要的问题是：因为数独是 9x9 的，每行每列很容易枚举，然而枚举每个 3x3 宫格会有一些麻烦。
在这里，枚举每个 3x3 宫，应用以下的式子：
box_index = (row // 3) * 3 + col // 3
依据下面的图示，咱们略微阐明一下，如何失去下面的式子。
先以列的角度看，标记为 0, 1, 2 的 3 个 3x3 宫格。能够看出这里每个 3x3 宫格的索引更多取决于列索引。
先看标记为 0 的 3x3 宫格，这里的列索引别离为 [0, 1, 2]， 1 的 3x3 宫格，这里的列索引别离为 [3, 4, 5]， 2 的 3x3 宫格，这里的列索引别离为 [6, 7, 8]，也就是 col // 3。
再以行的角度去看，标记为 0, 3, 6 的 3 个 3x3 宫格的索引跨度为 3，也就是说标记索引为 0 宫格如这样失去的，0 * 3 + col // 3，标记为 3 的宫格为：1 * 3 + col // 3。
在这里，下面公式的 [0, 1] 求得的公式与后面的相似，就是由 row // 3 取得。那么最终的式子为：
(row // 3) * 3 + col // 3
这里略微提一下，题目中阐明，无效数独并不一定可解，这里不思考是否可解，要求验证的是曾经填入的数字是否无效。
具体的算法思路：
遍历数独，查看数字在每行，每列，每个 3x3 宫格中是否有反复：
- 如果反复，返回 False
- 否则，记录该数字，往下持续遍历
- 最终遍历完结，返回 True。
以示例 2 为例，上面图示示意算法实现搜寻的过程：
具体的代码实现如下。
代码实现
class Solution: def isValidSudoku(self, board: List[List[str]]) -> bool: # 定义哈希表存储数字呈现在每行，每列，每个 3x3 的宫格的次数 # 题目中阐明，给定的数独肯定是 9x9 的 rows = [{} for _ in range(9)] cols = [{} for _ in range(9)] boxes = [{} for _ in range(9)] for i in range(9): for j in range(9): # 题目中要验证是曾经填入的数字，如果呈现 '.' 示意留空，不作解决 if board[i][j] != '.': # 取出数字，存入哈希表中（须要转换，给定的二维数组数字是字符串格局） num = int(board[i][j]) rows[i][num] = rows[i].get(num, 0) + 1 cols[j][num] = cols[j].get(num, 0) + 1 # 代入枚举 3x3 宫格的公式 boxes[(i // 3) * 3 + j // 3][num] = boxes[(i // 3) * 3 + j // 3].get(num, 0) + 1 # 行，列，3x3 宫格，任意一个如果呈现数字反复，则返回 False if rows[i][num] > 1 or cols[j][num] > 1 or boxes[(i // 3) * 3 + j // 3][num] > 1: return False return True实现后果
欢送关注
公众号 【书所集录】