815. 公交路线

落日映苍穹つ 2022-10-10 14:50 195阅读 0赞

#### 2021-06-28 LeetCode每日一题 ####

链接：[https://leetcode-cn.com/problems/bus-routes/][https_leetcode-cn.com_problems_bus-routes]

标签：**广度优先搜索、数组、哈希表**

> 题目

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

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

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

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
    输出：2
    解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。 
    
    输入：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 < 10

> 分析

这依然是一道用BFS求解的问题。按照常规的思路，找到出发站所在的路线（一个站可能对应多条路线），把路线中的所有点加入队列，然后再找队列中每个点所在的路线，把路线中的点加入队列…重复下去，知道找到终点站或者返回-1。

按照这个思路写出代码来并不困难，但其实会超时的，大概卡在最后三个用例了。耗时点在于对于队列中每个车站，都要去找对应的路线，然后又把路线中的点加入队列，尽管进行了剪枝，但依然非常耗时。

所以我们要避免对于每个站点都去查找它对应的路线，而且这里我们记录已经访问过的元素，应该是基于路线层面而不是车站层面，这样可以去掉大量的重复节点。

基于以上分析，我们可以先用哈希表记录下每个车站能够到达哪些路线（即二维数组的横坐标），并且在队列中存放路线，每次弹出队列中的元素时，通过该元素值可以快速拿到该路线有哪些站点，然后判断是否包含目标站点即可。

> 编码

class Solution { 
        public int numBusesToDestination(int[][] routes, int source, int target) { 
            // 特殊情况。。
            if (source == target) { 
                return 0;
            }
            
            int step = 1;
            // 记录每个车站可以达到哪几条线路
            Map<Integer, HashSet<Integer>> map = new HashMap<>();
            for (int i = 0; i < routes.length; i++) { 
                int[] stops = routes[i];
                for (int j = 0; j < stops.length; j++) { 
                    HashSet set = map.getOrDefault(stops[j], new HashSet<>());
                    set.add(i);
                    map.put(stops[j], set);
                }
            }
    
            Queue<Integer> queue = new LinkedList<>(map.get(source));
            // 记录已经走过的线路
            Set<Integer> visited = new HashSet<>(map.get(source));
    
            while (!queue.isEmpty()) { 
                int len = queue.size();
                for (int i = 0; i < len; i++) { 
                    int num = queue.poll();
        
                    // 该线路有哪些站点
                    int[] stations = routes[num];
                    for (int station : stations) { 
                        // 包含目标站点
                        if (station == target) { 
                            return step;
                        }
                        // 该站点可以到哪些路线
                        for (int r : map.get(station)) { 
                            // 没有访问该线路
                            if (!visited.contains(r)) { 
                                queue.offer(r);
                                visited.add(r);
                            }
                        }
                    }
                }
                step++;
            }
    
            return -1;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70]

[https_leetcode-cn.com_problems_bus-routes]: https://leetcode-cn.com/problems/bus-routes/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70]: /images/20221005/1837cad4fdc04d728d97679bdfcd3204.png