LeetCode 题解工作台
公交路线
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。 例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ..…
3
题型
6
代码语言
3
相关题
当前训练重点
困难 · 数组·哈希·扫描
答案摘要
我们首先判断 和 是否相同，如果相同则直接返回 。 然后我们使用一个哈希表 来构建站点到公交线路的映射。对于每一条公交线路，我们遍历其经过的所有站点，将每个站点映射到该公交线路，即 为经过站点 的所有公交线路。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个数组 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 <= 105routes[i]中的所有值 互不相同sum(routes[i].length) <= 1050 <= routes[i][j] < 1060 <= source, target < 106
解题思路
方法一：BFS
我们首先判断 和 是否相同，如果相同则直接返回 。
然后我们使用一个哈希表 来构建站点到公交线路的映射。对于每一条公交线路，我们遍历其经过的所有站点，将每个站点映射到该公交线路，即 为经过站点 的所有公交线路。
接着我们判断 和 是否在站点映射中，如果不在则返回 。
我们使用一个队列 来进行广度优先搜索，队列中的每个元素为一个二元组 ，表示当前站点 和到达当前站点所需的公交次数 。
我们初始化一个集合 来记录已经访问过的公交线路，一个集合 来记录已经访问过的站点。然后我们将 加入到 中，并将 加入到队列 中。
接下来我们开始广度优先搜索，当队列 不为空时，我们取出队列的第一个元素，即当前站点 和到达当前站点所需的公交次数 。
如果当前站点 是目标站点 ，我们返回到达目标站点所需的公交次数 。
否则，我们遍历经过当前站点的所有公交线路，对于每一条公交线路，我们遍历该线路上的所有站点，如果某个站点 没有被访问过，则将其加入到 中，并将 加入到队列 中。
最后，如果无法到达目标站点，则返回 。
时间复杂度 ，空间复杂度 ，其中 为所有公交线路上的站点总数。
class Solution:
def numBusesToDestination(
self, routes: List[List[int]], source: int, target: int
) -> int:
if source == target:
return 0
# 使用 defaultdict 构建站点到公交线路的映射
g = defaultdict(list)
for i, route in enumerate(routes):
for stop in route:
g[stop].append(i)
# 如果 source 或 target 不在站点映射中，返回 -1
if source not in g or target not in g:
return -1
# 初始化队列和访问集合
q = [(source, 0)]
vis_bus = set()
vis_stop = {source}
# 开始广度优先搜索
for stop, bus_count in q:
# 如果当前站点是目标站点，返回所需的公交次数
if stop == target:
return bus_count
# 遍历经过当前站点的所有公交线路
for bus in g[stop]:
if bus not in vis_bus:
vis_bus.add(bus)
# 遍历该线路上的所有站点
for next_stop in routes[bus]:
if next_stop not in vis_stop:
vis_stop.add(next_stop)
q.append((next_stop, bus_count + 1))
return -1 # 如果无法到达目标站点，返回 -1
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(M^2 * K + M * k * \log K) |
| 空间 | O(M^2 + \log K) |
面试官常问的追问
外企场景- question_mark
They want you to count buses taken, so BFS levels should represent boarded routes rather than raw stop distance.
- question_mark
They expect you to notice that shared stops create an implicit graph between routes and stops.
- question_mark
They are testing whether you can replace repeated array scanning with a stop-to-route hash lookup.
常见陷阱
外企场景- error
Using BFS on stops without tracking bus layers can return the fewest stops traveled instead of the fewest buses taken.
- error
Reprocessing the same route from multiple shared stops causes massive duplicate scanning and time waste.
- error
Forgetting the source equals target shortcut leads to returning 1 instead of 0 on a trivial case.
进阶变体
外企场景- arrow_right_alt
Model routes as graph nodes and connect two routes if they share at least one stop, then BFS across routes.
- arrow_right_alt
Run bidirectional BFS from source-reachable routes and target-reachable routes when overlap is dense.
- arrow_right_alt
Return an actual transfer path by storing parent route or parent stop information during BFS.