LeetCode 815. 公交路线 题目描述 我们有一个数组 routes ，其中 routes[i] 表示第 i 辆公交车会循环行驶的路线，例如 routes[0] = [1, 5, 7] 表示第 0 辆公交车会依次停靠站点 1、5、7。再给你一个起点站 source 和一个终点站 target ，如果两个站之间可以乘坐公交车到达（只能乘坐公交车，不能步行），请返回最少乘坐的公交车数量。如果无法到达，返回 -1。 示例 输入：routes = [ [ 1,2,7],[ 3,6,7] ], source = 1, target = 6 输出：2 解释：先从站点 1 乘坐公交车 0（路线 [ 1,2,7]）到达站点 7，然后换乘公交车 1（路线 [ 3,6,7 ]）到达站点 6。 解题过程 1. 问题分析 本题的关键在于“换乘”。我们不是直接计算站点到站点的距离，而是计算从起点到终点需要乘坐的公交车数量。 如果两个公交车路线有共同的站点，那么在这两条路线之间可以换乘。 因此，我们需要构建一个图，其中节点是公交车（即路线），边表示两条路线有公共站点，可以换乘。 2. 构建图模型 图的节点：每条公交车路线作为一个节点。 图的边：如果两条公交车路线有至少一个公共站点，那么它们之间有一条边。 但这样构建图后，我们还需要处理起点和终点：起点可能出现在多条路线上，终点也可能出现在多条路线上。 3. 具体步骤 (1) 预处理：记录每个站点属于哪些公交车路线 我们用一个哈希表 stopToBuses ，键是站点，值是一个列表，记录经过该站点的所有公交车（用路线索引表示）。 (2) 广度优先搜索（BFS） BFS 的节点是公交车路线（即路线索引）。 队列中存储 (bus, depth) ，其中 bus 是路线索引， depth 表示从起点到当前公交车需要乘坐的公交车数量。 我们还需要一个 visited 集合，记录已经访问过的公交车路线，避免重复访问。 (3) BFS 过程 初始化：找到所有包含起点站 source 的公交车路线，把这些路线加入队列，深度为 1。 如果某条公交车路线包含终点站 target ，那么立即返回当前深度。 否则，从当前公交车路线出发，找到所有可以换乘的公交车路线（即与当前路线有公共站点的其他路线），如果没访问过，就加入队列，深度加 1。 如果队列为空仍未找到，返回 -1。 (4) 优化换乘关系构建 如果直接两两比较路线是否有公共站点，复杂度较高。 我们可以利用 stopToBuses ：对于每个站点，经过它的所有公交车路线之间都是可以互相换乘的。这样我们可以快速构建邻接表。 4. 详细代码逻辑 构建 stopToBuses 。 构建邻接表 graph ， graph[i] 表示与公交车路线 i 有公共站点的所有其他路线。 BFS 初始化：将包含 source 的所有路线加入队列，深度为 1。 BFS 遍历：对于队列中的每个路线，如果它包含 target ，返回深度；否则，遍历它的所有邻居路线（即可以换乘的路线），若未访问则加入队列。 如果 BFS 结束未找到，返回 -1。 5. 复杂度分析 设公交车路线数量为 R，站点数量为 S。 构建 stopToBuses 和邻接表的时间复杂度为 O(R * L + S)，其中 L 是平均路线长度。 BFS 时间复杂度为 O(R + E)，E 是边数，最坏情况下 O(R^2)。 空间复杂度 O(R^2 + S)。 6. 边界情况 起点和终点相同：直接返回 0。 起点或终点不在任何路线中：返回 -1。 只有一条路线，且起点终点都在该路线上：返回 1。 这个算法将公交车换乘问题转化为图的最短路径问题，通过 BFS 高效求解最少乘坐的公交车数量。