来源:https://leetcode.com/problems/valid-sudoku/
题目:验证数独
验证一个9×9的数独是否合法。只需要根据以下的规定来验证已经填好的格子:
- 每行必须包含1-9的数字,不能重复。
- 每列必须包含1-9的数字,不能重复。
- 每个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
本题属于哈希表类题目,想了解更多关于哈希表的题目,可以参看哈希表专题。