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

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

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据