[LeetCode]36. 有效的数独(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 形式的。

解题思路

哈希表。精髓为通过当前的行索引和列索引计算出所处的 box 位置:$box = (i // 3) * 3 + j // 3$

代码

Python 3.6

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
class Solution:
def isValidSudoku(self, board: List[List[str]]) -> bool:
if not board or not board[0]:
return False
rows, cols = len(board), len(board[0])
boxs_hash = [{} for _ in range(rows * cols)]

cols_hash = [{} for _ in range(cols)]
i = 0
while i < rows:
row_hash = {}
j = 0
while j < cols:
cur = board[i][j]
if cur != ".":
box_idx = (i // 3) * 3 + j // 3 # 当前字符的 box 位置可以通过该公式酸楚!
if (cur in row_hash) or (cur in cols_hash[j]) or (cur in boxs_hash[box_idx]):
# 若该字符在三个 hash 中的任何一个,直接返回 False
return False
row_hash[cur] = 1
cols_hash[j][cur] = 1
boxs_hash[box_idx][cur] = 1
j += 1
i += 1
return True

执行用时 : 144 ms
内存消耗 : 13.9 MB

文章目录
  1. 1. 题目描述
  2. 2. 解题思路
  3. 3. 代码
|

载入天数...载入时分秒...