省份数量
难度:
标签:
题目描述
有 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 <= 200n == isConnected.lengthn == isConnected[i].lengthisConnected[i][j]为1或0isConnected[i][i] == 1isConnected[i][j] == isConnected[j][i]
代码结果
运行时间: 27 ms, 内存: 17.6 MB
// Problem: Find the number of provinces using Java Streams.
// Approach: Use streams to filter and count unvisited cities, and utilize a helper method to mark connected cities.
import java.util.stream.IntStream;
public class Solution {
public int findCircleNum(int[][] isConnected) {
int n = isConnected.length;
boolean[] visited = new boolean[n];
return (int) IntStream.range(0, n).filter(i -> !visited[i]).peek(i -> dfs(isConnected, visited, i)).count();
}
private void dfs(int[][] isConnected, boolean[] visited, int i) {
IntStream.range(0, isConnected.length)
.filter(j -> isConnected[i][j] == 1 && !visited[j])
.forEach(j -> {
visited[j] = true;
dfs(isConnected, visited, j);
});
}
}
解释
方法:
这个题解使用了深度优先搜索（DFS）的方法来找出省份的数量。主要思路是：从每个未访问过的城市开始，使用 DFS 遍历所有与其直接或间接相连的城市，并将其标记为已访问。每次启动一次新的 DFS 遍历，省份数量就加 1。当所有城市都被访问过后，得到的省份数量即为最终结果。
时间复杂度:
O(n^2)
空间复杂度:
O(n)
代码细节讲解
🦆
如何确保在使用DFS遍历时不会重复访问已经检查过的城市？
▷🦆
在DFS实现中，为什么选择从每个未访问的城市开始新的DFS遍历？是否有其他策略可以识别省份？
▷🦆
给定的isConnected矩阵是否总是方阵，即行数和列数相等？如果不是，将如何影响算法的实现？
▷🦆
在该题解中，如果遇到一个完全不相连的城市，算法是如何处理的？
▷相关问题
机器人能否返回原点
在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。
移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。
如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。
注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。
示例 1:
输入: moves = "UD" 输出: true 解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。
示例 2:
输入: moves = "LL" 输出: false 解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。
提示:
1 <= moves.length <= 2 * 104moves只包含字符'U','D','L'和'R'