• leetcode 36. 有效的数独(模拟题)



    作者简介:C/C++ 、Golang 领域耕耘者,创作者
    个人主页:作者主页
    活动地址:CSDN21天学习挑战赛
    题目来源: leetcode官网
    如果感觉博主的文章还不错的话,还请关注➕ 、点赞👍 、收藏🧡三连支持一下博主哦~~~

    💜 题目描述

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

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

    注意:

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

    示例1:

    输入:board =
    [[“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:

    输入:board =
    [[“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 存在, 因此这个数独是无效的。

    🧡 算法分析

    此题方法是模拟题

    直接模拟就行了

    💚 代码实现

    class Solution {
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
            // 模拟题
    
            // 判断行
            bool st[9];
            for(int i =0; i < 9; i ++)
            {
                memset(st, 0, sizeof st);
                 for(int j = 0; j < 9; j ++)
                    if(board[i][j] != '.')
                    {
                        int t = board[i][j] - '1'; // 因为只开了0-8的数组空间,这里映射一下
                        if(st[t]) return false;
                        st[t] = true;
                    }
            }
               
            // 判断列
            for(int i =0; i < 9; i ++)
            {
                memset(st, 0, sizeof st);
                for(int j = 0; j < 9; j ++)
                    if(board[j][i] != '.')
                    {
                        int t = board[j][i] - '1';
                        if(st[t]) return false;
                        st[t] = true;
                    }
            }
               
            // 判断小方格
            for(int i = 0; i < 9; i += 3)
                for(int j =0; j < 9; j +=3)
                {
                    memset(st, 0, sizeof st);
                    for(int x = 0; x < 3; x ++)
                        for(int y = 0; y < 3; y ++)
                            if(board[x + i][y + j] != '.')
                            {
                                int t= board[i + x][j + y] - '1';
                                if(st[t]) return false;
                                st[t] = true;
                            }
                }
                  
    
            return true;
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    执行结果:
    在这里插入图片描述

    💙 时间复杂度分析

    如果觉得对你有帮助的话:
    👍 点赞,你的认可是我创作的动力!
    🧡 收藏,你的青睐是我努力的方向!
    ✏️ 评论,你的意见是我进步的财富!

  • 相关阅读:
    AIGC做题能力谁家强呢?
    WKWebview加载SVG显示不全
    简单易学,让你拥有个性化的二维码
    什么是final修饰 使用final修饰类、方法、变量的区别?
    redis配制redis-static-server
    AIGC实战——深度学习 (Deep Learning, DL)
    c++ 图的重构识别
    科兴未来 | 第十届中国(泰州)国际大健康产业高层次人才创新创业大赛公告
    抬升市场投资情绪,若羽臣是否还需“自身硬”?
    Vue研习录(09)——Axios网络请求知识详解及示例分析
  • 原文地址:https://blog.csdn.net/qq_39486027/article/details/126239660