同一屋檐下连更四集狂喜 LeetCode 547. 省份数量

写在前面

晚上睡的有点晚，昨晚一直在搞排版和封面的事，在B站找了个视频跟着学做封面，感觉还不错，如何套路关注者，让他们更加感兴趣惦记你的文章。其实也是没学的太明白，只记得了封面要吸引人一点，不要简单的描述事实。晚上睡不着，一直在想怎么运营公众号，以及各个平台的联动，其实感觉自己有点想多了，这才开始，并且最初并不是这么一个想法，最初想的是来记录自己刷题，生活，读书的一些日常感悟吧。我打算不想那么多了，安心做就完事了。记录自己某一段时间的生活，以后会不会有更多的地方可以回味，能吸引人就更好，哈哈哈！！！🤪

今天看了个综艺，同一屋檐下，吼吼，这综艺不得了，我刚开始其实是不太能看得下去的，因为我想着肯定又是那种很多滤镜的场景，一群人在一个地方谈恋爱。然后看了之后发现并没有滤镜，每个人性格都特别鲜明，而且经历也都特别丰富吧，职业不同，环境不同，所处的年龄段不同，一群人思想的碰撞💥，还是挺有趣的，虽说还是免不了的谈恋爱🤣，而且评论室里的那群人也可以给我们很丰富的一个看问题的观点，就仿佛在和一群人一起看着综艺，一起吐槽，交流。还不错，整体上来看。朋友们可以看起来哦。

题目详情

题目描述

有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。

省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

返回矩阵中 省份 的数量。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-provinces
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例 1：

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

示例 2：

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

示例 3:

输入：isConnected = [[1,1,0],[1,1,1],[0,1,1]]
输出：1

题解

思路

我在思考这个问题的时候，第一时间是想到了并查集，但是在后续实现的时候，发现到一个点，就是会不会存在A的父节点是B，已经更新过了，B的父节点是C，那么在计算省份的数量时，需要什么方式才能更加合适地计算出来。其实是我多虑了，以为只要当前的城市她的父节点不是自己，就证明有人和他相连，他就一定不是最上层的父节点，就可以不用记录他，只需要找到最上层的父节点来记录即可。不需要知道当前这个城市她的顶级父节点是谁，这个不重要。

步骤

第一步，处理数据。先建立父节点数组，并且初始化自己为自己的父节点。在按照已知数据进行处理，每一对连接的城市都需要进行合并父节点，这样两者就相通了。

第二步，求解。现在是已知父节点数组，求有多少个独立路径，只需要找到父节点是自己的那些节点，然后求和即可。

注意

代码

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int[] res = new int[n];
        for(int i=0;i<n;i++){
            res[i] = i;
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(isConnected[i][j]==1){
                    union(i,j,res);
                }
            }
        }
        int num =0;
        for(int i=0;i<n;i++){
            if(res[i]==i){
                num++;
            }
        }
        return num;
    }
    private int find(int x,int[] f){
        if(f[x]!=x){
            f[x] = find(f[x],f);
        }
        return f[x];
    }

    private void union(int x,int y,int[] f){
        int fx = find(x,f);
        int fy = find(y,f);
        f[fx] = fy;
    }
}

总结

自己还是要提前理清楚思路，不能以上来看到熟悉的题目，还没有思考明白，就直接下笔，写到一半才发现自己卡壳了，那就很难受，有可能这个思路一开始就行不通，却浪费了时间。现在的我其实对于一般的题目都可以确定是用什么方法去完成它，需要真正思考的是实现的细节是否合理，有没有别扭的地方，加油加油。🤔

欢迎关注我的公众号：方头狮的新世界

欢迎关注我的知乎专栏：方头狮的新世界