题目链接

LeetCode

题目描述

给你一个数组 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 <= 105
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106
解题思路
方法一：BFS
为了方便，我们令每个公交站为一个「车站」，由一个「车站」可以进入一条或多条「路线」。
问题为从「起点车站」到「终点车站」，所进入的最少路线为多少。
抽象每个「路线」为一个点，当不同「路线」之间存在「公共车站」则为其增加一条边权为 1 的无向边。

由于是在边权为 1 的图上求最短路，我们直接使用 BFS 即可。
起始时将「起点车站」所能进入的「路线」进行入队，每次从队列中取出「路线」时，查看该路线是否包含「终点车站」：

包含「终点车站」：返回进入该线路所花费的距离
不包含「终点车站」：遍历该路线所包含的车站，将由这些车站所能进入的路线，进行入队

一些细节：由于是求最短路，同一路线重复入队是没有意义的，因此将新路线入队前需要先判断是否曾经入队。

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if(source == target){
            return 0;
        }
        // 记录站点经过的线路
        Map<Integer, Set<Integer>> lineMap = new HashMap<>();
        // 记录经过的线路
        Deque<Integer> dq = new LinkedList<>();
        // 记录线路所需要的步数
        Map<Integer, Integer> stepMap = new HashMap<>();
        for(int i = 0; i < routes.length; ++i){
            for(int j = 0; j < routes[i].length; ++j){
                // 将从起点可以进入的路线加入队列
                if(source == routes[i][j]){
                    dq.offer(i);
                    stepMap.put(i, 1);
                }
                Set<Integer> set = lineMap.getOrDefault(routes[i][j], new HashSet<Integer>());
                set.add(i);
                lineMap.put(routes[i][j], set);
            }
        }
        while(!dq.isEmpty()){
            // 取出当前所在的路线，与进入该路线所花费的距离
            int curLine = dq.poll();
            int step = stepMap.get(curLine);
            // 遍历当前路线的所有站点
            for(int station : routes[curLine]){
                // 存在目的站点，直接返回所花费的距离
                if(station == target){
                    return step;
                }
                // 找出包含该节点的所有线路
                Set<Integer> lines = lineMap.get(station);
                if(lines == null){
                    continue;
                }
                // 遍历并记录所有未被 stepMap 记录（未被遍历到）的线路
                for(int line : lines){
                    if(!stepMap.containsKey(line)){
                        stepMap.put(line, step + 1);
                        dq.offer(line);
                    }
                }
            }
        }
        return -1;
    }
}

时间复杂度 O(n*m)
空间复杂度 O(n*m)

算法(leetcode 牛客网)

815. 公交路线***

题目链接

题目描述

解题思路

方法一：BFS