LeetCode 36. 有效的数独（哈希）
LeetCode 36. 有效的数独（哈希）
Michael阿明
发布于 2021-02-20 11:03:12
发布于 2021-02-20 11:03:12
1. 题目信息
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/valid-sudoku 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
2.1 暴力3次遍历查找
对每行，每列，每个小块分别进行hash查重即可。
class Solution
{
public:
bool isValidSudoku(vector<vector<char>>& board)
{
int i, j, x, y;
unordered_map<int, int> m;
for(i = 0; i < 9; ++i)
{
m.clear();
for(j = 0; j < 9; ++j)
{
if(board[i][j] != '.')
{
if(m.find(board[i][j]-'0') != m.end())
return false;
else
m[board[i][j]-'0'] = 1;
}
}
}
for(j = 0; j < 9; ++j)
{
m.clear();
for(i = 0; i < 9; ++i)
{
if(board[i][j] != '.')
{
if(m.find(board[i][j]-'0') != m.end())
return false;
else
m[board[i][j]-'0'] = 1;
}
}
}
for(i = 0; i < 9; i += 3)
{
for(j = 0; j < 9; j += 3)
{
m.clear();
for(x = i; x < i+3; ++x)
{
for(y = j; y < j+3; ++y)
{
if(board[x][y] != '.')
{
if(m.find(board[x][y]-'0') != m.end())
return false;
else
m[board[x][y]-'0'] = 1;
}
}
}
}
}
return true;
}
};2.2 一次遍历查找
9个小9宫格的序号 idx = (i/3)*3+j/3 分别为行和列和宫格建立27个hash表，进行查重
class Solution {
public:
bool isValidSudoku(vector<vector<char>> &board) {
unordered_map<int, int> row[9];
unordered_map<int, int> column[9];
unordered_map<int, int> box[9];
int i, j, box_idx, num;
for(i = 0; i < 9; ++i)
{
for(j = 0; j < 9; ++j)
{
box_idx = (i/3)*3 + j/3;
num = board[i][j] - '0';
if(board[i][j] != '.')
{
if(row[i].find(num) != row[i].end() ||
column[j].find(num) != column[j].end() ||
box[box_idx].find(num) != box[box_idx].end())
return false;
else
{
row[i][num] = 1;
column[j][num] = 1;
box[box_idx][num] = 1;
}
}
}
}
return true;
}
};本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/08/20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
