1. 题目
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。
例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。
2. 示例
示例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
3. 题解
- 本题是一个无向图的搜索问题，但是题意很容易把我们弄混，可能一开始以为要将站台作为图上的点，其实应该将车作为点，如果两辆车的路线之间存在公共站点，那么就视作这两个点之间存在连线；
- 因为需要绕弯，所以，同时用到多个映射用于保存车和站台，站台和车，车和车之间的关系。
- 已经将问题转化为图的搜索问题了，那就很好做了，常规的做法就是将点与点关系存在映射之中，建立领接表，然后搜索映射。
4. 实现
1 public class NumBusesToDestination815 { 2 // 建立邻接表，保存车到车之间是否存在直线的连线，也就是可以直接换成 3 Map<Integer, Set<Integer>> bus2buses = new HashMap<>(); 4 // 保存车经过哪些站台, key是车, value是站台 5 Map<Integer, Set<Integer>> bus2stations = new HashMap<>(); 6 // 保存站台有哪些车经过, key是站台, value是车 7 Map<Integer, List<Integer>> station2buses = new HashMap<>(); 8 public int numBusesToDestination(int[][] routes, int source, int target) { 9 if(source == target) return 0; 10 11 int n = routes.length; 12 int res = n + 1; 13 14 // 初始化两个映射 15 for(int i = 0; i < n; i++) { 16 bus2buses.put(i, new HashSet<>()); 17 bus2stations.put(i, new HashSet<>()); 18 } 19 20 // 初始化两个映射 21 for(int i = 0; i < n; i++) { // 遍历所有车 22 for(int r : routes[i]) { // 当前车经过的站台 23 if(!station2buses.containsKey(r)) { // station2buses未添加到hash表中 24 station2buses.put(r, new ArrayList<>()); // 添加站r并初始化 25 } 26 station2buses.get(r).add(i); // 将i车加入站r的列表 27 bus2stations.get(i).add(r); // 将r车加入站i的列表 28 } 29 } 30 31 // 不存在target站 32 if (!station2buses.containsKey(target)) return -1; 33 34 // 填入车与车之间的直接关系 35 for(int s : station2buses.keySet()) { 36 for(int i = 0; i < station2buses.get(s).size(); i++) { 37 bus2buses.get(station2buses.get(s).get(i)).addAll(station2buses.get(s)); 38 } 39 } 40 41 // 遍历当前站台为出发点的所有车，作为dfs的出发车辆 42 for(int cur : station2buses.get(source)) { 43 // 存放经过出发站台的当前车辆，以及经过目的站台的所有车辆 44 Set<Integer> start = new HashSet<>(), end = new HashSet<>(); 45 // 当前车辆加入起点集合 46 start.add(cur); 47 // 加入终点集合 48 end.addAll(station2buses.get(target)); 49 // 如果当前车辆的路线中已经包含了目标站台，那么只乘一次车 50 if(bus2stations.get(cur).contains(target)) return 1; 51 // 广度优先搜索比较 52 res = Math.min(res, bfs(start, end, 2, n)); 53 } 54 return res == n + 1 ? -1 : res; 55 } 56 57 // 广度优先搜索，参数分别代表起点集合、终点集合、当前搜索的深度、最大深度 58 private int bfs(Set<Integer> start, Set<Integer> end, int len, int max) { 59 // 没有车辆或者 60 if(start.size() == 0 || len > max) return max + 1; 61 Set<Integer> next = new HashSet<>(); 62 // 枚举所有车辆 63 for(int cur : start) { 64 // 该车与其他车辆无连线 65 if(!bus2buses.containsKey(cur)) continue; 66 // 枚举与当前车辆有连线的所有车辆 67 for(int b : bus2buses.get(cur)) { 68 // 如果当前车要经过目标车站，那么可以返回长度 69 if(end.contains(b)) return len; 70 // 不然需要将当前车辆放到下一个起点集合中再进行搜索 71 else next.add(b); 72 } 73 } 74 return bfs(next, end, len + 1, max); 75 } 76 }
5. 题解
努力去爱周围的每一个人，付出，不一定有收获，但是不付出就一定没有收获！ 给街头卖艺的人零钱，不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)！
如果客官喜欢小生的园子，记得关注小生哟，小生会持续更新(#^.^#)(#^.^#)。