LeetCode题目36：有效的数独
原题描述
+
判断一个 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形式的。
原题链接：https://leetcode-cn.com/problems/valid-sudoku
思路解析
+
数独确实有一道难题，但不是这一道，此题反而属于一点就透的类型。
回到问题，要判断是否有重复的数组出现，也就是判断重复，根据之前的经验，选择hash table绝对错不了，对于规模固定为9*9的数独来说，这点存储空间的浪费不算什么。
先考虑行。要判断某一行是否有重复的数字，我们只需要遍历这一行，统计每个数字出现的次数即可。一共9行，那么就需要9个这样的hash table；如果开辟一个长度为9的hash table的数组，那么行号和数组index就可以一一对应起来了。
列也是如此，也需要一个长度为9的hash table数组。
3*3子数独也需要长度为9的hash table。那么给定一个二维坐标(x,y)，如何判断它属于第几个子数独？假设我们如下编号，那么(x, y)和子数独index的关系是：
index = (x / 3) * 3 + y / 3
我们可以一边扫描数独，一边将统计信息填入这三类hash table中，然后再检查是否有某个数字出现的次数多于1即可。最多扫描一遍，就可以判断出结果。
复杂度分析
+
- 时间复杂度：O(1)
- 空间复杂度：O(1)
C++参考代码
+
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
std::vector<std::unordered_map<char, int>> rows(9);
std::vector<std::unordered_map<char, int>> cols(9);
std::vector<std::unordered_map<char, int>> box(9);
for (int i = 0; i < board.size(); ++i) {
for (int j = 0; j < board[i].size(); ++j) {
if (board[i][j] != '.') {
int num = (int)board[i][j];
int bid = (i / 3) * 3 + j / 3;
rows[i][num] = rows[i].count(num) != 0 ? rows[i][num] + 1 : 1;
cols[j][num] = cols[j].count(num) != 0 ? cols[j][num] + 1 : 1;
box[bid][num] = box[bid].count(num) != 0 ? box[bid][num] + 1 : 1;
if (rows[i][num] > 1 || cols[j][num] > 1 || box[bid][num] > 1) {
return false;
}
}
}
}
return true;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2020-08-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
