友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
815. 公交路线
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
-
例如，路线
routes[0] = [1, 5, 7]表示第0辆公交车会一直按序列1 → 5 → 7 → 1 → 5 → 7 → 1 → …这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -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
提示：
-
1 <= routes.length <= 500. -
1 <= routes[i].length <= 105 -
routes[i]中的所有值 互不相同 -
sum(routes[i].length) <= 105 -
0 <= routes[i][j] < 106 -
0 <= source, target < 106
思路分析
-
一刷
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-07-09 21:20:17
*/
public int numBusesToDestination(int[][] routes, int source, int target) {
// 记录经过车站 x 的公交车编号
Map<Integer, List<Integer>> stopToBuses = new HashMap<>();
for (int i = 0; i < routes.length; i++) {
for (int x : routes[i]) {
stopToBuses.computeIfAbsent(x, _ -> new ArrayList<>()).add(i);
}
}
// 小优化：如果没有公交车经过起点或终点，直接返回
if (!stopToBuses.containsKey(source) || !stopToBuses.containsKey(target)) {
return source != target ? -1 : 0;
}
// BFS
Map<Integer, Integer> dis = new HashMap<>();
dis.put(source, 0);
Queue<Integer> queue = new ArrayDeque<>();
queue.add(source);
while (!queue.isEmpty()) {
Integer x = queue.poll();
Integer disX = dis.get(x);
for (Integer i : stopToBuses.get(x)) {
if (routes[i] != null) {
for (int y : routes[i]) {
if (!dis.containsKey(y)) {
dis.put(y, disX + 1);
queue.add(y);
}
}
routes[i] = null;
}
}
}
return dis.getOrDefault(target, -1);
}