LeetCode 815. 公交路线 题目描述 我们有一个数组 routes ，其中 routes[i] 表示第 i 辆公交车的行驶路线，即该公交车会按顺序停靠的站台。再给你一个起点站 source 和一个终点站 target 。如果我们可以从起点站 source 出发，仅通过公交车（可以换乘）到达终点站 target ，则返回最少的乘坐公交车数量；否则返回 -1 。 示例 输入：routes = [ [ 1,2,7],[ 3,6,7] ], source = 1, target = 6 输出：2 解释：先乘坐第一辆公交车（路线 [ 1,2,7]）从站台 1 到站台 7，然后换乘第二辆公交车（路线 [ 3,6,7 ]）从站台 7 到站台 6。 解题思路 这个问题的核心在于“换乘”。直接以公交站为节点进行广度优先搜索（BFS）可能会因为站台数量庞大而超时。更高效的方法是 以公交车为节点 构建图，然后通过 BFS 找出从包含起点的公交车到包含终点的公交车的最短路径。 详细步骤 建立“站台→公交车”映射 创建一个哈希表 stopToBuses ，键是公交站台，值是一个列表，记录经过该站台的所有公交车的索引。 例如，对于 routes = [ [ 1,2,7],[ 3,6,7] ]： 站台 1：经过的公交车索引为 [ 0 ] 站台 2：经过的公交车索引为 [ 0 ] 站台 7：经过的公交车索引为 [ 0, 1 ] 站台 3：经过的公交车索引为 [ 1 ] 站台 6：经过的公交车索引为 [ 1 ] BFS 初始化 使用一个队列 queue ，存放当前乘坐的公交车索引。 使用一个集合 visited ，记录已经乘坐过的公交车，避免重复乘坐。 首先，通过 stopToBuses[source] 找到所有经过起点站的公交车，将这些公交车加入队列，并标记为已访问。 初始化乘坐公交车数量 busCount = 1 （因为起点站已经算作一次乘车）。 BFS 过程 遍历当前队列中的所有公交车（表示当前层级的所有公交车）。 对于每辆公交车，检查其路线是否包含目标站台 target 。如果包含，直接返回 busCount 。 如果不包含，则遍历该公交车路线上的所有站台，再通过 stopToBuses 找到从这些站台可以换乘的、且未被访问过的公交车，加入队列，并标记为已访问。 完成当前层级的所有公交车处理后， busCount++ ，表示进行了一次换乘。 终止条件 如果队列为空仍未找到目标站台，返回 -1 。 注意：如果起点和终点相同，且不为空，应返回 0（但题目通常保证起点 ≠ 终点）。 为什么这样高效？ 公交车数量通常远少于站台数量，以公交车为节点构建图可以显著减少 BFS 的宽度。 通过“站台→公交车”映射，快速找到换乘可能性，避免遍历所有站台。 复杂度分析 时间复杂度：O(B * S)，其中 B 是公交车数量，S 是每辆公交车平均站台数。 空间复杂度：O(B * S) 存储映射关系和 BFS 队列。 通过这种“公交车为节点”的 BFS 策略，我们可以高效解决公交路线的最少换乘问题。