LeetCode 815. 公交路线

2021-03-07 HGNULB 约 11 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 815. 公交路线

题意分析

给一批公交线路，routes[i] 是第 $i$ 条线路依次经过的站点列表，而且这条线路是环形往复运行的——只要上了这辆车，就能到达它经过的任意一个站点，不必关心方向和先后。给定起点站 source 和终点站 target，问最少乘坐几辆公交车能从起点到终点，不可达返回 $-1$。

「环形往复」这一条把问题大大简化了：一条线路内部的站点两两互达，代价为零。因此一条线路可以被整体看成一个超级节点，站点只是线路之间的连接凭证。

要求的是「乘坐的公交车数量」，不是「换乘次数」，也不是「经过的站点数」。这三者互不相同：坐一辆车直达是 1 而不是 0；两条线路之间的换乘次数比车辆数少 1。这个口径直接决定了计数变量的初值。

起点等于终点时答案是 $0$，因为一辆车都不用坐。这是必须最先挡住的边界，否则后面的流程至少会返回 1。

规模信号很有意思：线路条数 routes.length 不超过 500，但所有线路的站点总数可以达到 $10^5$，站点编号最大到 $10^6$。线路少而站点多，说明以「线路」为图节点是合算的（最多 500 个节点），但两条线路是否相邻不能靠两两求交集去判断，那样代价是线路数平方乘以线路长度。站点编号大而稀疏，说明必须用哈希表而不是定长数组来索引站点。

边界上还要考虑：target 可能压根不出现在任何线路里，此时无解；source 同理。

解法：按线路 BFS

核心思路

第一个念头往往是「以站点为图节点」：站点之间如果同属一条线路就连边，然后跑最短路。这个建模的致命问题是边数爆炸——一条有 $L$ 个站的线路会产生 $L^2$ 条边，站点总数 $10^5$ 时边数完全不可控。更麻烦的是，站点图上的最短路统计的是「经过几个站」，而题目要的是「坐了几辆车」，两者根本不是一回事。

换个视角：既然同一条线路内部移动是免费的，那真正需要付代价的动作只有「上一辆新车」。把线路当作图的节点，两条线路只要共享至少一个站点就连一条边（表示可以在那个站点换乘），那么「最少坐几辆车」就等价于「从任意一条含 source 的线路出发，走到任意一条含 target 的线路，最少经过几个节点」。节点数只有 500，规模瞬间可控。

但直接建这张线路图仍有问题：判断两条线路是否相交需要求交集，$500^2$ 对线路乘上每次求交的代价，在站点总数 $10^5$ 时依然偏重。

瓶颈落在「如何快速找到某条线路的所有邻居」。观察到换乘一定发生在某个具体的站点上，于是反过来建索引：维护一张 stop -> 经过该站的线路编号列表 的哈希表。有了它，从线路 $r$ 出发找邻居就变成「遍历 $r$ 的每个站点，取出该站点上的所有线路」，完全不需要显式建出线路之间的边。这张反向索引的构建代价只有所有站点总数的线性倍。

于是搜索框架定下来：在线路构成的隐式图上做层序广度优先搜索。边权全为 1（每换一条线路就是多坐一辆车），所以广度优先搜索给出的层数就是最少车辆数。

维护的不变量有三条。其一，计数器 buses 恒等于「当前正在展开的这一层线路，需要坐几辆车才能上」——因为初始入队的是含 source 的线路，坐上它们就已经花了一辆车，所以 buses 从 1 起算。其二，visitedRoute 标记的是「已经入过队的线路」，保证每条线路最多被展开一次。其三，visitedStop 标记的是「已经被用来扩展过的站点」，保证同一个站点上的线路列表最多被遍历一次——这条是复杂度的关键，没有它，一个被很多线路共用的枢纽站会被反复展开。

解题步骤

先特判 source == target，直接返回 $0$。为什么必须最先做：后续流程的最小可能返回值是 1，不特判就会把「原地不动」算成坐了一辆车。

遍历所有线路的所有站点，建立 stop -> 线路编号列表 的哈希表。为什么用哈希表而不是数组：站点编号最大到 $10^6$ 而实际出现的站点最多 $10^5$ 个，定长数组既浪费又可能越界。

把所有包含 source 的线路全部入队并标记为已访问，buses 初始化为 1。为什么是多源入队：起点站可能同时被好几条线路覆盖，它们都是「花一辆车就能上」的候选，必须同层处理。为什么 buses 从 1 起：队列里这些线路本身就已经消耗了一辆车。

按层展开。每一层开始前先记住当前队列长度作为本层的元素个数，然后恰好弹出这么多次。为什么要固定层大小：展开过程中会往队尾追加下一层的元素，如果在循环条件里实时取队列长度，层与层就会混在一起，buses 的计数失去意义。

对弹出的每条线路，遍历它的所有站点。一旦某个站点等于 target，立即返回当前的 buses。为什么在这里判定而不是入队时判定：初始入队的线路本身就可能已经覆盖了 target，在遍历站点时统一判定可以让这种情况自然落进第一层，不需要额外的特殊处理。

站点若已经在 visitedStop 里就跳过，否则标记后取出该站点上的所有线路，未访问过的标记并入队。为什么要对站点去重：枢纽站可能被上百条线路共用，每条线路展开时都重新遍历一次它的线路列表会让复杂度退化；一个站点一旦被展开过，它能引出的线路就都已经入过队了，再展开没有任何新信息。

一层处理完后 buses 自增，继续下一层；队列耗尽仍未命中则返回 $-1$。

以 routes = [[1,2,7],[3,6,7]]、source = 1、target = 6 走一遍：起点不等于终点，继续。建反向索引得到 1 -> [0]、2 -> [0]、7 -> [0, 1]、3 -> [1]、6 -> [1]。含 source = 1 的线路只有 0，入队并标记，buses = 1。

第一层，本层大小为 1，弹出线路 0，它的站点是 [1, 2, 7]。站点 1 不等于 6，未访问过，标记；它对应的线路只有 0，已访问，不入队。站点 2 同理，标记后引出线路 0，已访问。站点 7 不等于 6，未访问，标记；它对应的线路是 [0, 1]，线路 0 已访问跳过，线路 1 未访问，标记并入队。本层结束，buses 变成 2。

第二层，本层大小为 1，弹出线路 1，它的站点是 [3, 6, 7]。站点 3 不等于 6，标记后引出线路 1，已访问。站点 6 等于 target，立即返回 buses = 2。答案是 2，对应先坐线路 0 从站 1 到站 7，再换线路 1 从站 7 到站 6。

代码实现

// 从包含 source 的线路出发，广度优先搜索 到包含 target 的线路。
class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if (source == target) {
            return 0;
        }

        Map<Integer, List<Integer>> stopToRoutes = new HashMap<>();
        for (int i = 0; i < routes.length; i++) {
            for (int stop : routes[i]) {
                stopToRoutes.computeIfAbsent(stop, k -> new ArrayList<>()).add(i);
            }
        }

        Deque<Integer> queue = new ArrayDeque<>();
        boolean[] visitedRoute = new boolean[routes.length];
        Set<Integer> visitedStop = new HashSet<>();

        for (int route : stopToRoutes.getOrDefault(source, List.of())) {
            queue.offer(route);
            visitedRoute[route] = true;
        }

        int buses = 1;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int route = queue.poll();
                for (int stop : routes[route]) {
                    if (stop == target) {
                        return buses;
                    }

                    if (!visitedStop.add(stop)) {
                        continue;
                    }

                    for (int next : stopToRoutes.getOrDefault(stop, List.of())) {
                        if (!visitedRoute[next]) {
                            visitedRoute[next] = true;
                            queue.offer(next);
                        }
                    }
                }
            }
            buses++;
        }

        return -1;
    }
}

// 从包含 source 的线路出发，广度优先搜索 到包含 target 的线路。
func numBusesToDestination(routes [][]int, source int, target int) int {
    if source == target {
        return 0
    }

    stopToRoutes := make(map[int][]int)
    for i := 0; i < len(routes); i++ {
        for _, stop := range routes[i] {
            stopToRoutes[stop] = append(stopToRoutes[stop], i)
        }
    }

    queue := make([]int, 0)
    visitedRoute := make([]bool, len(routes))
    visitedStop := make(map[int]bool)

    for _, route := range stopToRoutes[source] {
        queue = append(queue, route)
        visitedRoute[route] = true
    }

    buses := 1
    head := 0
    for head < len(queue) {
        size := len(queue) - head
        for i := 0; i < size; i++ {
            route := queue[head]
            head++
            for _, stop := range routes[route] {
                if stop == target {
                    return buses
                }

                if visitedStop[stop] {
                    continue
                }
                visitedStop[stop] = true

                for _, next := range stopToRoutes[stop] {
                    if !visitedRoute[next] {
                        visitedRoute[next] = true
                        queue = append(queue, next)
                    }
                }
            }
        }
        buses++
    }

    return -1
}

复杂度分析

时间复杂度：$O(S)$，其中 $S$ 是所有线路的站点数之和。建反向索引扫一遍所有站点是 $O(S)$；搜索阶段每条线路最多出队一次，出队时遍历它自己的站点，合计仍是 $O(S)$；每个站点最多被展开一次，展开时遍历它的线路列表，而所有站点的线路列表长度之和恰好也是 $S$。两个「每个元素最多处理一次」的去重标记是把复杂度压到线性的关键。

空间复杂度：$O(S)$。反向索引里存了 $S$ 个线路编号，站点访问集合最多装下所有不同站点，线路访问标记和队列都是 $O(n)$（$n$ 为线路条数），主项是反向索引。

关键点总结

建模的第一步是问「什么动作要付代价」。这题里同线路内移动免费、换乘收费，所以图的节点应该是线路而不是站点。选错节点不只是慢，连要求的量都对不上。

当「节点之间是否相邻」需要靠共享某种元素来判定时，不要两两求交集去显式建边，而是建一张「元素 -> 拥有它的节点」的反向索引，在搜索时按需展开。这个技巧在单词接龙、相似字符串组等题里反复出现。

反向索引展开时必须对「元素」本身也做去重。枢纽站被上百条线路共用，不去重会让同一份线路列表被反复遍历，复杂度从线性退化成平方。

层序广度优先搜索要在进入本层前固定层大小。边遍历边追加的队列，如果用实时长度作循环条件，层的边界会消失。

计数变量的初值由题目口径决定。这题问的是「坐几辆车」而不是「换乘几次」，所以第一层就已经是 1；起点等于终点则是唯一能返回 0 的情形，必须单独挡在最前面。

面试视角：先说出「以站点建图会产生 $L^2$ 条边」这个坏消息，再给出「以线路建图 + 站点反向索引」的方案，最后补上两处去重的必要性，这条叙述链最能体现建模能力。这题在字节、阿里的图论轮里出现频率相当高。

易错点总结

错误写法：不特判 source == target。用例 routes = [[1,2,7]]、source = 1、target = 1 的正确答案是 0，流程走完会返回 1。

错误写法：buses 从 0 开始计数。初始入队的线路本身就要花一辆车，用例 routes = [[1,2,7],[3,6,7]]、source = 1、target = 6 会返回 1，正确答案是 2。

错误写法：以站点为节点做广度优先搜索，层数当答案。这样统计的是「经过几个站」，用例里从站 1 到站 7 再到站 6 是 2 个站间跳跃，看似巧合正确，但只要一条线路上多几个站，答案立刻偏大。

错误写法：预先两两枚举线路求交集来建显式邻接表。线路 500 条、站点总数 $10^5$ 时，$500^2$ 次交集判断的总代价过高，大用例上会超时。

错误写法：只标记线路已访问，不标记站点已访问。一个被大量线路共用的枢纽站会在每条线路展开时被重新遍历，复杂度退化，站点总数大的用例会超时。

错误写法：只标记站点已访问，不标记线路已访问。同一条线路会被不同站点重复入队，队列膨胀且层数统计失真。

错误写法：层循环写成 while (!queue.isEmpty()) 里直接取 queue.size() 作为实时条件，或者在内层循环条件里重新调用 queue.size()。本层还没处理完，下一层的元素已经被追加进来，两层混成一层，buses 的含义彻底失效。

错误写法：查询 stopToRoutes 时不处理键不存在的情况。target 或 source 可能不在任何线路上，直接对 null 遍历会抛空指针；Go 里对不存在的键取值会得到 nil 切片，遍历是安全的，但两种语言的行为差异容易让人误判。

错误写法：站点访问集合用定长布尔数组按站点编号索引。站点编号最大到 $10^6$，虽然勉强能开，但换成编号更大的变体就会越界，用哈希集合才是稳妥写法。

错误写法：忘记在队列耗尽后返回 $-1$。target 不在任何线路上时函数会走到末尾，缺少返回语句要么编译不过，要么返回上一次的 buses 值。

相似题目

题目	难度	考察点
127. 单词接龙	困难	同样用「共享元素」的反向索引避免显式建边，索引的键是把某一位换成通配符后的模式串，而不是站点编号
752. 打开转盘锁	中等	邻接关系由规则直接生成（每一位加减一），不需要反向索引，难点在于把死亡列表预置进访问标记
1129. 颜色交替的最短路径	中等	节点就是原始节点，但状态里要多带一维「上一条边的颜色」，考察的是状态扩维而非建模换视角