LeetCode题练习与总结：省份数量--547

标签：-- 城市 isConnected int 相连 547 数组 visited LeetCode

一、题目描述

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

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

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

返回矩阵中省份的数量。

示例 1：

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

示例 2：

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

提示：

1 <= n <= 200
n == isConnected.length
n == isConnected[i].length
isConnected[i][j] 为 1 或 0
isConnected[i][i] == 1
isConnected[i][j] == isConnected[j][i]

二、解题思路

这个问题可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。我们可以将每个城市视为图中的一个节点，如果两个城市相连，则这两个节点之间存在一条边。问题转化为了求解图中连通分量的数量。

以下是使用DFS的解题步骤：

初始化一个标记数组，用来记录每个城市是否被访问过。
遍历所有城市，对于每个城市，如果它没有被访问过，则从该城市开始进行深度优先搜索，并将所有与它直接或间接相连的城市标记为已访问。
每次开始一个新的深度优先搜索时，意味着找到了一个新的省份。
最终，遍历完所有城市后，省份的数量即为深度优先搜索的次数。

三、具体代码

class Solution {
    public int findCircleNum(int[][] isConnected) {
        int provinces = 0;
        boolean[] visited = new boolean[isConnected.length];
        
        for (int i = 0; i < isConnected.length; i++) {
            if (!visited[i]) {
                dfs(isConnected, visited, i);
                provinces++; // 找到一个新的省份
            }
        }
        return provinces;
    }
    
    private void dfs(int[][] isConnected, boolean[] visited, int i) {
        for (int j = 0; j < isConnected.length; j++) {
            if (isConnected[i][j] == 1 && !visited[j]) {
                visited[j] = true;
                dfs(isConnected, visited, j); // 继续搜索与城市j相连的其他城市
            }
        }
    }
}

在这个代码中，findCircleNum 方法负责遍历所有城市并统计省份的数量，而 dfs 方法则实现了深度优先搜索的逻辑。当找到一个未访问的城市时，dfs 方法会被调用，并将所有与之相连的城市标记为已访问。

四、时间复杂度和空间复杂度

1. 时间复杂度

我们有一个双层循环，外层循环遍历所有城市，内层循环遍历与当前城市相连的其他城市。
外层循环执行 n 次，其中 n 是城市的数量。
对于每个城市，内层循环可能最多执行 n 次（在最坏的情况下，每个城市都与所有其他城市相连）。
因此，总的时间复杂度是 O(n^2)，因为对于每个城市，我们可能需要检查所有其他城市。

2. 空间复杂度

我们使用了一个布尔数组 visited 来记录每个城市是否被访问过，这个数组的大小是 n，其中 n 是城市的数量。
除了这个数组之外，我们没有使用额外的空间，递归调用栈的深度在最坏的情况下是 n（当所有城市都相连时）。
因此，总的空间复杂度是 O(n)，这是因为我们需要存储访问状态，并且在递归调用过程中可能会占用 O(n) 的栈空间。

五、总结知识点

类定义：
- class Solution：定义了一个名为 Solution 的类。
方法定义：
- public int findCircleNum(int[][] isConnected)：定义了一个公共方法 findCircleNum，它接受一个二维整数数组 isConnected 作为参数，并返回一个整数。
- private void dfs(int[][] isConnected, boolean[] visited, int i)：定义了一个私有辅助方法 dfs，它接受一个二维整数数组、一个布尔数组和一个整数作为参数，没有返回值。
数组：
- int[][] isConnected：一个二维数组，表示城市之间的连接关系。
- boolean[] visited：一个布尔数组，用于记录城市是否已被访问。
循环：
- for 循环：用于遍历数组的元素。
条件语句：
- if 语句：用于检查条件是否满足，并根据条件执行不同的代码块。
递归：
- dfs 方法中的递归调用：dfs(isConnected, visited, j)，这是深度优先搜索（DFS）算法的核心，递归地访问所有相连的城市。
成员变量和局部变量：
- int provinces：findCircleNum 方法中的局部变量，用于计数省份的数量。
- boolean[] visited：findCircleNum 方法中的局部变量，用于跟踪访问状态。
基本操作：
- 数组元素访问：isConnected[i][j] 和 visited[j]。
- 数组元素赋值：visited[j] = true。
算法思想：
- 深度优先搜索（DFS）：用于遍历图中的节点，并找出所有连通分量。
逻辑运算符：
- &&：逻辑与运算符，用于组合多个条件。
- !：逻辑非运算符，用于取反。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。

标签：--,城市,isConnected,int,相连,547,数组,visited,LeetCode
From： https://blog.csdn.net/weixin_62860386/article/details/145149873