LeetCode 第36题 Valid Sudoku (Java)
来源： https://leetcode.com/problems/valid-sudoku/
题目：验证数独
验证一个9×9的数独是否合法。只需要根据以下的规定来验证已经填好的格子：
- 每行必须包含1-9的数字，不能重复。
- 每列必须包含1-9的数字，不能重复。
- 每个3×3的小盒子必须包含1-9的全部数字，不能有重复。
数据可以是不完全填满的，每个空的格子用字符’.’表示。
例 1:
<strong>Input:</strong> [ ["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"] ] <strong>Output:</strong> true
例 2:
<strong>Input:</strong> [ ["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"] ] <strong>Output:</strong> false <strong>Explanation:</strong> 左上角的3x3格子有两个8。
注意:
- 数独可以是合法的，但是不一定可解。
- 只需要考虑哪些被填写好的了格子。
- 给定的数独只包含1-9的数字和字符’.’。
- 数独的尺寸总是9×9。
我们的解法可以很简单，就是严格的按照三条规定来计算。首先我们检查每一行看看有没有重复的数字，然后看每一列有没有重复的数字，然后我们看每个3×3的小盒子里面有没有重复的数字。
这道题分类为哈希表，所以，我们可以检查的时候构建一些哈希表，把数字加进去，如果某个数字在某个情况下的出现次数超过了1，那么即为不合法。但是这道题只有10个数字，我觉得可以更简单的解决，就是每次我们创建一个9个元素的数组，来统计这些数字出现的频率即可。
只要数组里面任何一个数字大于1，那么数独就不合法：
然后，我们需要检查行
检查列
检查3×3的小盒子
然后把这三种规则组合起来即可：
Github： https://github.com/tinyfool/leetcode/tree/master/src/p0036
本题属于哈希表类题目，想了解更多关于哈希表的题目，可以参看哈希表专题。
正文到此结束
热门推荐
相关文章
近期评论
-
你这基本没有更新呀，最近文章显示还是2019年的文章。不符合要求哈
-
关键词：慕云博客 链接：https://www.lilun.me 描述：分享原创文字的个人博客
-
-
-
可以提供一下源码吗
-
不是商业站，鸡娃学习笔记
-
-
-
-
听他们说很厉害的样子
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
