LeetCode 815. 公交路线

约 6 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 困难 未解决 2-5 阿里
标签
数组 哈希表 广度优先搜索

题目描述

✅ 815. 公交路线

image-20260928225055957

image-20260928225055959

题意分析

每条公交线路循环运行，乘上某辆车后就能到达这条线路的任意站点。要求最少乘坐几辆公交车，因此沿同一线路经过多少站都不增加代价，换乘另一条线路才增加 1。

解法：按线路 BFS

核心思路

[!blue]

把每条线路看成一个搜索节点，两条线路只要有公共站点，就能用一次换乘连接。这样原问题变成：从包含 source 的任意线路出发，经过最少换乘，到达一条包含 target 的线路。每次换乘代价相同，适合按层 BFS。

无需两两比较线路来建边。先建立 stopToRoutes，记录每个站点属于哪些线路；展开某条线路时，遍历它的所有站点，再通过索引找到可换乘的线路。所有经过起点的线路都以车辆数 1 入队，因为第一次上车也要计数，而且起点可能有多种选择。

visitedRoute 在入队时标记线路，保证每条线路只展开一次。visitedStop 则标记已经展开过的换乘站：第一次到达该站时，经过它的所有线路都已加入搜索，之后再经过该站不可能用更少车辆，因此不必重复扫描相同的线路列表。这两个标记分别消除线路展开和换乘索引的重复工作。

第 buses 层的线路都能乘坐 buses 辆车到达。若其中某条线路包含终点，沿该车继续乘坐即可到达，直接返回 buses；BFS 已先检查过更少车辆的层，所以这就是最小值。队列耗尽仍未找到终点，则无法到达。

解题步骤

  1. 若 source == target，无需上车，返回 0。
  2. 建立站点到线路的反向索引，将所有经过起点的线路入队并标记，令 buses = 1。
  3. 固定当前层的队列长度，逐条检查线路。遇到终点就返回；遇到尚未展开的站点，就将该站的未访问线路加入下一层。
  4. 当前层全部处理完后，令 buses 加 1。队列为空时返回 -1；起点没有任何线路时也会自然走到这个分支。

代码实现

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;
    }
}

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)$，用于反向索引、两类访问标记和线路队列。

关键点总结

[!green]

  • 站点与线路的访问标记负责不同的重复开销。
  • 在同一线路继续乘坐不增加车辆数量。

易错点总结

[!yellow]

  • 只选一条起点线路，可能错过更少车辆的路线。
  • 从零开始给初始线路计数，会少算一辆。
  • 同一枢纽站重复展开，会反复扫描相同线路列表。

相似题目

题目 难度 关联与区别
1345. 跳跃游戏 IV 困难 同样按共享属性批量连接状态，展开过的整组应标记，避免重复扫描导致平方开销。
127. 单词接龙 困难 同样用BFS最少操作建模，本题每次乘上一条公交线路计一次，不能把经过站点数当换乘次数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/96122260
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！