[LeetCode] 815. Bus Routes

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.

For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … forever.
You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.

Example 1:
Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Example 2:
Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1

Constraints:
1 <= routes.length <= 500.
1 <= routes[i].length <= 105
All the values of routes[i] are unique.
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106

公交路线。

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> … 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

思路

这是一道 graph 的题，思路是用 BFS 做。既然是图论的题，那么首先还是要将数据转换成图的形式。这里的图是一个邻接表，用 hashmap 表示，key 是车站，value 是一个 list，list 里存的是经过这个车站的公交车列表。然后从 source 开始 BFS 遍历，直到找到 target。需要注意的是 BFS 的 queue 中存储的是没有被访问过的车站的 index。当我们从 queue 中弹出一个车站的时候，我们就可以找到经过这个车站的所有公交车，也就能找到所有公交车他们各自的路线了。在这些路线中，我们再把没有路线中没有被访问过的车站加入到 queue 中。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        // corner case
        if (source == target) {
            return 0;
        }

        // normal case
        int n = routes.length;
        // 建立站点到公交车编号的映射
        // 每个站点都经过哪些bus
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int stop : routes[i]) {
                if (!map.containsKey(stop)) {
                    map.put(stop, new ArrayList<>());
                }
                map.get(stop).add(i);
            }
        }

        // bfs
        Queue<Integer> queue = new LinkedList<>();
        Set<Integer> visitedStops = new HashSet<>();
        boolean[] visitedBuses = new boolean[n];
        queue.offer(source);
        visitedStops.add(source);
        int busCount = 0;

        while (!queue.isEmpty()) {
            busCount++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int curStop = queue.poll();
                // 遍历当前站点可以搭乘的公交车
                for (int bus : map.getOrDefault(curStop, new ArrayList<>())) {
                    if (visitedBuses[bus]) {
                        continue;
                    }
                    visitedBuses[bus] = true;
                    for (int nextStop : routes[bus]) {
                        if (nextStop == target) {
                            return busCount;
                        }
                        if (visitedStops.contains(nextStop)) {
                            continue;
                        }
                        visitedStops.add(nextStop);
                        queue.offer(nextStop);
                    }
                }
            }
        }
        return -1;
    }
}