Leetcode第三十六题(有效的数独)

简介: 这篇文章介绍了如何使用C++编写一个算法来验证一个9x9数独是否有效,遵循数独的规则,即数字1-9在每一行、每一列和每个3x3宫内只能出现一次。

题目描述:

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

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。(请参考示例图)

注意:

一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

分别遍历行, 列, 九宫格使用bool类型的数组存储, 如果为空白格则continue掉本次循环, 否则将当前遍历数作为下标将对应bool数组中的值置为true,当遍历后续数字时判断bool类型数组对应位置是否是true,如果是则不是一个有效的数独。否则将数组对应下标值置为true。如果行,列,九宫格均遍历完成则是一个有效的数独。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        bool exp[9];   //用来判断行列以及九宫格是否数字不重复
        //遍历行
        for (int i = 0; i < 9; i++){
            memset(exp,0,sizeof(exp));
            for(int j = 0;j < 9; j++){
                if(board[i][j] == '.') continue;
                int t = board[i][j] - '1';
                if(exp[t]) return false;
                exp[t] = true;
            }
        }
        //遍历列
        for(int i = 0; i < 9; i++){
            memset(exp,0,sizeof(exp));
            for(int j = 0; j < 9; j++){
                if(board[j][i] == '.') continue;
                int t = board[j][i] - '1';
                if(exp[t]) return false;
                exp[t] = true;
            }
        }
        //遍历九宫格
        for(int i = 0; i < 9; i += 3){
            for(int j = 0; j < 9; j += 3){
                memset(exp,0,sizeof(exp));
                for(int k = 0; k < 3; k++){
                    for(int l = 0; l < 3; l++){
                        if(board[i + k][j + l] == '.') continue;
                        int t = board[i + k][j + l] - '1';
                        if(exp[t]) return false;
                        exp[t] = true;
                    }
                }
            }
        }
        return true;
    }
};
相关文章
|
7月前
|
Java
leetcode-37:解数独
leetcode-37:解数独
48 0
|
4月前
|
存储 算法 索引
LeetCode第36题有效的数独
这篇文章介绍了LeetCode第36题"有效的数独"的解题方法,通过使用三个二维数组分别记录每一行、每一列以及每个3x3宫格内1-9数字出现的次数,来验证给定数独是否有效。
|
6月前
|
算法
力扣经典150题解析之三十四:有效的数独
力扣经典150题解析之三十四:有效的数独
45 0
|
6月前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
7月前
leetcode-36:有效的数独
leetcode-36:有效的数独
53 0
|
JavaScript 前端开发 算法
LeetCode 37.解数独(注释完整+JavaScript解题)
LeetCode 37.解数独(注释完整+JavaScript解题)
84 0
|
算法
LeetCode 37 解数独 循环+回溯算法
LeetCode 37 解数独 循环+回溯算法
61 0
|
算法 安全 Swift
LeetCode - #37 解数独
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
LeetCode - #37 解数独
|
算法 安全 Swift
LeetCode - #36 有效的数独
不积跬步,无以至千里;不积小流,无以成江海,Swift社区 伴你前行。如果大家有建议和意见欢迎在文末留言,我们会尽力满足大家的需求。
LeetCode - #36 有效的数独