【每日一题】LeetCode 815.公交路线（广度优先搜索、数组、哈希表）
题目描述
给定一个表示公交线路的数组 routes，其中每个 routes[i] 表示第 i 辆公交车的循环行驶路线。现在从 source 车站出发，要前往 target 车站，期间只能乘坐公交车。要求找出最少乘坐的公交车数量。如果无法到达目标车站，则返回 -1。
思路分析
这个问题可以通过图的广度优先搜索（BFS）来解决。我们可以将每个车站看作图中的一个节点，每辆公交车可以看作连接这些节点的边。具体步骤如下：
-
建立车站到公交车的映射：首先，我们需要建立一个映射，将每个车站映射到经过该车站的所有公交车。
-
判断起点和终点是否可达：如果起点或终点没有公交车经过，那么无法到达，直接返回
-1。 -
初始化队列和访问数组：使用一个队列来存储待访问的车站，以及一个数组来记录哪些公交车已经被访问过。
-
广度优先搜索：从起点开始，对每个经过起点的公交车进行搜索，找到所有可以到达的车站，并将这些车站加入队列。同时记录每个车站的最少乘坐公交车数量。
-
更新距离：对于队列中的每个车站，检查它是否是目标车站，如果是，则返回当前的乘坐公交车数量。如果不是，将其相邻的车站（即同一辆公交车上的其他车站）加入队列，并更新它们的乘坐公交车数量。
-
返回结果：如果队列被清空还没有找到目标车站，说明无法到达，返回
-1。
输入示例
示例 1：
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1
代码实现
import java.util.*;
class Solution {
public int numBusesToDestination(int[][] routes, int source, int target) {
int n = routes.length; // 公交车数量
if (source == target) return 0; // 如果起点和终点相同，不需要乘坐公交车
// 建立车站到公交车的映射
HashMap<Integer, List<Integer>> hm = new HashMap<>();
for (int i = 0; i < n; i++) {
for (int x : routes[i]) {
hm.computeIfAbsent(x, k -> new ArrayList<>()).add(i);
}
}
// 如果起点或终点没有公交车经过，无法到达
if (!hm.containsKey(source) || !hm.containsKey(target)) return -1;
// 初始化队列，用于广度优先搜索
Queue<Integer> que = new ArrayDeque<>();
boolean[] vis = new boolean[n]; // 记录公交车是否被访问过
HashMap<Integer, Integer> dis = new HashMap<>(); // 记录每个车站的最少乘坐公交车数量
dis.put(source, 0); // 起点的乘坐公交车数量为0
que.offer(source);
// 广度优先搜索
while (!que.isEmpty()) {
int x = que.poll();
int disX = dis.get(x);
for (int i : hm.get(x)) {
if (!vis[i]) {
vis[i] = true; // 标记公交车为已访问
for (int y : routes[i]) {
// 如果这个车站没有被访问过，加入队列并更新距离
if (!dis.containsKey(y)) {
dis.put(y, disX + 1);
que.offer(y);
}
}
}
}
}
// 返回目标车站的最少乘坐公交车数量，如果无法到达则返回-1
return dis.getOrDefault(target, -1);
}
}
