当前位置:首页 » 《随便一记》 » 正文

✨【Code皮皮虾】多方法,全面注释解析,解决——>《36. 有效的数独》_Code皮皮虾的博客

29 人参与  2021年12月30日 13:08  分类 : 《随便一记》  评论

点击全文阅读


文章目录

    • 😉毛遂自荐
    • 🌈题目
    • 🔥思路讲解
    • 🌊三维数组
    • ⛄采用二维实现
      • 😁思路讲解
      • 😋代码实现
    • 💖最后

Code皮皮虾 一个沙雕而又有趣的憨憨少年,和大多数小伙伴们一样喜欢听歌、游戏,当然除此之外还有写作的兴趣,emm…,日子还很长,让我们一起加油努力叭🌈

👉话不多说,直达底部有粉丝专享福利!!!


😉毛遂自荐

毛遂自荐一下,给大家推荐一下自己的专栏😁,欢迎小伙伴们收藏关注😊

大厂面试题专栏

Java专栏

爬虫专栏

更多专栏尽在主页,点我😁!!!

🌈题目

👉力扣链接

image.png

注意

image.png



🔥思路讲解

因为题目给出的范围

board.length == 9
board[i].length == 9
board[i][j] 是一位数字或者 ‘.’

所以,以示例一为例,整个数组分为9个小数组每个小数组中不能出现重复数字可采用 / 3的方式确定在哪个小数组

image.png

所以,我们可以采用三维数组的方式来实现



🌊三维数组

class Solution {
    public boolean isValidSudoku(char[][] board) {
        
        //因为数字 1-9 在每一行只能出现一次。
        int[][] rows = new int[9][9];

        //因为数字 1-9 在每一列只能出现一次。
        int[][] cols = new int[9][9];

        //三维,数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
        int[][][] tmps = new int[3][3][9];
        

        //一次遍历
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];

                //如果当前字符不是 . 才进行判断
                if (c != '.') {
                    //将字符转化为int类型的索引
                    int index = c - '0' - 1;
                    //当前行,这个索引,即这个数字已经出现一次
                    rows[i][index]++;

                    //当前列,这个索引,即这个数字已经出现一次
                    cols[j][index]++;

                    //当前这个小数组,这个索引,即这个数字已经出现一次,通过 / 3来确定在哪个小数组
                    tmps[i / 3][j / 3][index]++;
                    
                    //条件判断,如果 > 1,说明重复,则return false;
                    if (rows[i][index] > 1 || cols[j][index] > 1 || tmps[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
}



⛄采用二维实现



😁思路讲解

想要从三维降到二维,就需要通过巧妙的方法来确定在哪个小数组,这是关键!!!


如何确定?

公式先告诉大家:(i / 3) * 3 + j / 3,通过这个公式就可以确定,不信我们来验证验证🔥

以示例一为例

  1. 比如说:第三个小数组中的6,它的坐标为(2,7),通过公式得出(2 / 3) * 3 + 7 / 3 = 2,也就是下标为2的小数组也就是第三个数组
  2. 再来,第七个小数组中的6,它的坐标为(6,1),通过公式得出(6 / 3) * 3 + 1 / 3 = 6,下标为6,也就是第七个小数组

image.png

😋代码实现

class Solution {
    public boolean isValidSudoku(char[][] board) {


        int[][] rows = new int[10][10];
        int[][] cols = new int[10][10];
        //三维降二维
        int[][] tmps = new int[10][10];

        char ch = ' ';
        int tmp = 0;


        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                ch = board[i][j];
                if (ch == '.') continue;
                tmp = ch - '0';

                //套公式计算在哪个小数组
                int idx = i / 3 * 3 + j / 3;
                rows[i][tmp] += 1;
                cols[j][tmp] += 1;
                tmps[idx][tmp] += 1;

                if (rows[i][tmp] > 1 || cols[j][tmp] > 1 || tmps[idx][tmp] > 1) return false;             
            }
        }
        return true;
    }
}

当然,也可以通过boolean数组来判断


💖最后

我是 Code皮皮虾,一个热爱分享知识的 皮皮虾爱好者,未来的日子里会不断更新出对大家有益的博文,期待大家的关注!!!

创作不易,如果这篇博文对各位有帮助,希望各位小伙伴可以一键三连哦!,感谢支持,我们下次再见~~~

公众号干货内容输出,囊括Java、Python爬虫、力扣题解、大厂面试题 四大系列,更有长时间总结的干货资源分享,后台回复:面试资料即可领取


最后,祝各位步步高升🚀🚀🚀

                                                   粉丝福利👇🏻👇🏻👇🏻


点击全文阅读


本文链接:http://zhangshiyu.com/post/32406.html

数组  数字  公式  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1