LeetCode 第36题 Valid Sudoku

来源：https://leetcode.com/problems/valid-sudoku/

题目：验证数独

验证一个9×9的数独是否合法。只需要根据以下的规定来验证已经填好的格子：

1. 每行必须包含1-9的数字，不能重复。
2. 每列必须包含1-9的数字，不能重复。
3. 每个3×3的小盒子必须包含1-9的全部数字，不能有重复。

数据可以是不完全填满的，每个空的格子用字符’.’表示。

例 1:

Input:
[
  ["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"]
]
Output: true

例 2:

Input:
[
  ["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"]
]
Output: false
Explanation: 左上角的3x3格子有两个8。

注意:

• 数独可以是合法的，但是不一定可解。
• 只需要考虑哪些被填写好的了格子。
• 给定的数独只包含1-9的数字和字符’.’。
• 数独的尺寸总是9×9。

我们的解法可以很简单，就是严格的按照三条规定来计算。首先我们检查每一行看看有没有重复的数字，然后看每一列有没有重复的数字，然后我们看每个3×3的小盒子里面有没有重复的数字。

这道题分类为哈希表，所以，我们可以检查的时候构建一些哈希表，把数字加进去，如果某个数字在某个情况下的出现次数超过了1，那么即为不合法。但是这道题只有10个数字，我觉得可以更简单的解决，就是每次我们创建一个9个元素的数组，来统计这些数字出现的频率即可。

只要数组里面任何一个数字大于1，那么数独就不合法：

然后，我们需要检查行

检查列

检查3×3的小盒子

然后把这三种规则组合起来即可：

Github：https://github.com/tinyfool/leetcode/tree/master/src/p0036

本题属于哈希表类题目，想了解更多关于哈希表的题目，可以参看哈希表专题。

打赏

微信扫一扫，打赏作者吧～