今天在 LeetCode 做到一道题：有效的数独，难度是中等。
题目
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
- 数字 1-9 在每一行只能出现一次。
- 数字 1-9 在每一列只能出现一次。
- 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字，空白格用 '.' 表示。
代码
如果你只想通过程序，直接复制就行了(｡•ˇ‸ˇ•｡)
// 个人代码先贴上。做法不一定好，但能通过！
class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
int bnl = 0; // 当前块位置（默认从0开始）
for(int i = 0; i < 9; i++){
map<char,int> sta_h;
map<char,int> sta_l;
map<char,int> sta_b;
// 检查行
for(int j = 0; j < 9; j++){
if(board[i][j] != '.'){
if(sta_h[board[i][j]] == 0){
sta_h[board[i][j]] = 1;
}else{
return false;
}
}
}
// 检查列
for(int j = 0; j < 9; j++){
if(board[j][i] != '.'){
if(sta_l[board[j][i]] == 0){
sta_l[board[j][i]] = 1;
}else{
return false;
}
}
}
// 检查块
int now_h,now_l;
// 取得当前 3X3 的初始行列
if((bnl / 3) < 1){
now_h = 0;
now_l = (bnl * 3);
}else if((bnl / 3) >= 1 && (bnl / 3) < 2){
now_h = 3;
now_l = ((bnl - 3) * 3);
}else{
now_h = 6;
now_l = ((bnl - 6) * 3);
}
if(now_l == -1){
now_l = 0;
}
for(int j = now_l; j < now_l + 3; j++){ // 开始时的列
for(int k = now_h; k < now_h + 3; k++){ // 开始时的行
if(board[k][j] != '.'){
if(sta_b[board[k][j]] == 0){
sta_b[board[k][j]] = 1;
}else{
return false;
}
}
}
}
bnl ++;
}
return true;
}
};解题思路
这道题的难点主要在: “数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。”
横竖不能重复是非常简单的，只需要进行遍历并记录每个出现过的信息即可。
在个人代码中创建了三个Map用于储存已被使用过的数据:
- sta_h: 储存行检测中出现过的值
- sta_l: 储存列检测中出现过的值
- sta_b: 储存块检测中出现过的值
每一次扫到非“.”的值时就检测是否存在，存在则直接 return false; 不存在则将map状态转为已存在。
在做这道题时很快就完成了横竖的检测。但 3 X 3 时却卡了很久（当时还以为这题贼简单）
3 X 3 宫内检测
首先我的思路是：在这个 9 X 9 的数独中正好有 9 个 3 X 3 的宫。可以使用一个变量来储存当前遍历到的宫是哪一个，然后可以通过简单的计算算出下一个需要检测的宫的开始位置。
由于需要检测的宫正好也有 9 个，所以可以直接把这个检测程序也放到横竖检查的遍历中。
// 取得当前 3X3 的初始行列
if((bnl / 3) < 1){
now_h = 0;
now_l = (bnl * 3);
}else if((bnl / 3) >= 1 && (bnl / 3) < 2){
now_h = 3;
now_l = ((bnl - 3) * 3);
}else{
now_h = 6;
now_l = ((bnl - 6) * 3);
}
if(now_l == -1){
now_l = 0;
}上面的代码可以取得对应宫的初始行和列（这段代码很水，我都不知道自己是怎么搞出来的）
遍历时便可根据取得的初始行列进行检查。中间检查是否存在的程序和横竖的检测是一样的。
for(int j = now_l; j < now_l + 3; j++){ // 开始时的列
for(int k = now_h; k < now_h + 3; k++){ // 开始时的行
if(board[k][j] != '.'){
if(sta_b[board[k][j]] == 0){
sta_b[board[k][j]] = 1;
}else{
return false; // 如果中途发现重复数据，直接返回 false
}
}
}
}
bnl ++; // bnl 记录了当前所在的块（当一个块检测完毕，就进入下一个检测）这道题写的很水，如果有大佬有改进意见请评论给我！万分感激！！
