[LeetCode] 36. 有效的数独

Author： mr小卓X
发布时间：May 10, 2020
784views
No comments
3694 words
Categories：算法

> 今天在 LeetCode 做到一道题：[有效的数独][1]，难度是中等。

### 题目

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

![数独题目][2]

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

### 代码

如果你只想通过程序，直接复制就行了(｡•ˇ‸ˇ•｡)

```cpp
// 个人代码先贴上。做法不一定好，但能通过！
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 个，所以可以直接把这个检测程序也放到横竖检查的遍历中。

```cpp
// 取得当前 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;
}
```
上面的代码可以取得对应宫的初始行和列（这段代码很水，我都不知道自己是怎么搞出来的）

遍历时便可根据取得的初始行列进行检查。中间检查是否存在的程序和横竖的检测是一样的。

```cpp
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 记录了当前所在的块（当一个块检测完毕，就进入下一个检测）
```

这道题写的很水，如果有大佬有改进意见请评论给我！万分感激！！

[1]: https://leetcode-cn.com/problems/valid-sudoku/
  [2]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png

Last modification：May 10th, 2020 at 09:44 pm

如果觉得我的文章对你有用，请随意赞赏

[LeetCode] 36. 有效的数独

mr小卓X • 2020 年 05 月 10 日

> 今天在 LeetCode 做到一道题：[有效的数独][1]，难度是中等。

### 题目

判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。

1. 数字 1-9 在每一行只能出现一次。
2. 数字 1-9 在每一列只能出现一次。
3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

![数独题目][2]

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字，空白格用 '.' 表示。

### 代码

如果你只想通过程序，直接复制就行了(｡•ˇ‸ˇ•｡)

```cpp
// 个人代码先贴上。做法不一定好，但能通过！
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;

// 检查块            
            int now_h,now_l;

if(now_l == -1){
                now_l = 0;
            }

}

return true;
    }
};
```
### 解题思路

在个人代码中创建了三个Map用于储存已被使用过的数据:

* sta_h: 储存行检测中出现过的值
* sta_l: 储存列检测中出现过的值
* sta_b: 储存块检测中出现过的值

每一次扫到非“.”的值时就检测是否存在，存在则直接 return false; 不存在则将map状态转为已存在。

在做这道题时很快就完成了横竖的检测。但 3 X 3 时却卡了很久（当时还以为这题贼简单）

#### 3 X 3 宫内检测

由于需要检测的宫正好也有 9 个，所以可以直接把这个检测程序也放到横竖检查的遍历中。

if(now_l == -1){
    now_l = 0;
}
```
上面的代码可以取得对应宫的初始行和列（这段代码很水，我都不知道自己是怎么搞出来的）

遍历时便可根据取得的初始行列进行检查。中间检查是否存在的程序和横竖的检测是一样的。

这道题写的很水，如果有大佬有改进意见请评论给我！万分感激！！

[1]: https://leetcode-cn.com/problems/valid-sudoku/
  [2]: https://upload.wikimedia.org/wikipedia/commons/thumb/f/ff/Sudoku-by-L2G-20050714.svg/250px-Sudoku-by-L2G-20050714.svg.png

[LeetCode] 36. 有效的数独

Leave a Comment Cancel reply

[JS] 关于回调函数（callback）

[洛谷] P1064 金明的预算方案

[二进制] 转换、原码、反码以及补码

我与编程的不解之缘

[洛谷] P1039 侦探推理

[Rust] 关于 Dorea Web 服务的设计

[二进制] 转换、原码、反码以及补码

[笔记] 逻辑学 - 命题逻辑 {1}

[LeetCode] 36. 有效的数独

[笔记] 二叉搜索树

[LeetCode] 36. 有效的数独