乐趣区

关于leetcode:LeetCode-36-有效的数独-Python

36. 无效的数独


题目起源:力扣(LeetCode)https://leetcode-cn.com/problems/valid-sudoku

题目


判断一个 9×9 的数独是否无效。只须要依据以下规定,验证曾经填入的数字是否无效即可。

数字 1-9 在每一行只能呈现一次。
数字 1-9 在每一列只能呈现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能呈现一次。

上图是一个局部填充的无效的数独。

数独局部空格内已填入了数字,空白格用 ‘.’ 示意。

示例 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 和字符 ‘.’。
  • 给定数独永远是 9×9 模式的。

解题思路


思路:迭代,哈希表

先看数独无效的规定:

  • 数字 1-9 在每一行只能呈现一次。
  • 数字 1-9 在每一列只能呈现一次。
  • 数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能呈现一次。

那么咱们能够依据这个规定,遍历给定的数独三次,别离去判断每行,每列,每个 3×3 宫内是否有反复的数字。如果有反复的数字,能够间接返回 False;否则,直至遍历完结,返回 True。

然而在这里,能够思考遍历一次,同时去判断每行,每列,每个 3×3 宫内是否有反复的数字。

在这里,咱们应用哈希表去存储每个数字呈现的次数(包含每行,每列,每个 3×3 宫)。在这里次要的问题是:因为数独是 9×9 的,每行每列很容易枚举,然而枚举每个 3×3 宫格会有一些麻烦。

在这里,枚举每个 3×3 宫,应用以下的式子:

box_index = (row // 3) * 3 + col // 3

依据下面的图示,咱们略微阐明一下,如何失去下面的式子。

先以列的角度看,标记为 0, 1, 2 的 3 个 3×3 宫格。能够看出这里每个 3×3 宫格的索引更多取决于列索引。

先看标记为 0 的 3×3 宫格,这里的列索引别离为 [0, 1, 2]1 的 3×3 宫格,这里的列索引别离为 [3, 4, 5]2 的 3×3 宫格,这里的列索引别离为 [6, 7, 8],也就是 col // 3

再以行的角度去看,标记为 0, 3, 6 的 3 个 3×3 宫格的索引跨度为 3,也就是说标记索引为 0 宫格如这样失去的,0 * 3 + col // 3,标记为 3 的宫格为:1 * 3 + col // 3

在这里,下面公式的 [0, 1] 求得的公式与后面的相似,就是由 row // 3 取得。那么最终的式子为:

(row // 3) * 3 + col // 3

这里略微提一下,题目中阐明,无效数独并不一定可解,这里不思考是否可解,要求验证的是曾经填入的数字是否无效。

具体的算法思路:

  • 遍历数独,查看数字在每行,每列,每个 3×3 宫格中是否有反复:

    • 如果反复,返回 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

实现后果


欢送关注


公众号【书所集录】

退出移动版