大佬教程收集整理的这篇文章主要介绍了剑指Offer 815. 公交路线，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。
给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。@H_450_2@
例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。@H_450_2@现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。@H_450_2@
求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。@H_450_2@
示例1：@H_450_2@
输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6@H_450_2@输出：2@H_450_2@解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。 @H_450_2@
示例2：@H_450_2@
输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12@H_450_2@输出：-1@H_450_2@
提示：@H_450_2@
1 <= routes.length <= 500.@H_450_2@1 <= routes[i].length <= 105@H_450_2@routes[i] 中的所有值 互不相同@H_450_2@sum(routes[i].length) <= 105@H_450_2@0 <= routes[i][j] < 106@H_450_2@0 <= source, target < 106@H_450_2@
@H_674_80@ 1@H_450_2@ public@H_450_2@ class@H_450_2@ numbusesToDesTination815 { @H_450_2@@H_674_80@ 2@H_450_2@ //@H_450_2@ 建立邻接表，保存车到车之间是否存在直线的连线，也就是可以直接换成@H_450_2@ @H_674_80@ 3@H_450_2@ Map<Integer, Set<Integer>> bus2buses = new@H_450_2@ HashMap<>(); @H_450_2@@H_674_80@ 4@H_450_2@ //@H_450_2@ 保存车经过哪些站台, key是车, value是站台@H_450_2@ @H_674_80@ 5@H_450_2@ Map<Integer, Set<Integer>> bus2stations = new@H_450_2@ HashMap<>(); @H_450_2@@H_674_80@ 6@H_450_2@ //@H_450_2@ 保存站台有哪些车经过, key是站台, value是车@H_450_2@ @H_674_80@ 7@H_450_2@ Map<Integer, List<Integer>> station2buses = new@H_450_2@ HashMap<>(); @H_450_2@@H_674_80@ 8@H_450_2@ public@H_450_2@ int@H_450_2@ numbusesToDesTination(int@H_450_2@[][] routes, int@H_450_2@ source, int@H_450_2@ target) { @H_450_2@@H_674_80@ 9@H_450_2@ if@H_450_2@(source == target) return@H_450_2@ 0; @H_450_2@@H_674_80@10@H_450_2@ @H_674_80@11@H_450_2@ int@H_450_2@ n = routes.length; @H_450_2@@H_674_80@12@H_450_2@ int@H_450_2@ res = n + 1; @H_450_2@@H_674_80@13@H_450_2@ @H_674_80@14@H_450_2@ //@H_450_2@ 初始化两个映射@H_450_2@ @H_674_80@15@H_450_2@ for@H_450_2@(int@H_450_2@ i = 0; i < n; i++) { @H_450_2@@H_674_80@16@H_450_2@ bus2buses.put(i, new@H_450_2@ HashSet<>()); @H_450_2@@H_674_80@17@H_450_2@ bus2stations.put(i, new@H_450_2@ HashSet<>()); @H_450_2@@H_674_80@18@H_450_2@ } @H_450_2@@H_674_80@19@H_450_2@ @H_674_80@20@H_450_2@ //@H_450_2@ 初始化两个映射@H_450_2@ @H_674_80@21@H_450_2@ for@H_450_2@(int@H_450_2@ i = 0; i < n; i++) { //@H_450_2@ 遍历所有车@H_450_2@ @H_674_80@22@H_450_2@ for@H_450_2@(int@H_450_2@ r : routes[i]) { //@H_450_2@ 当前车经过的站台@H_450_2@ @H_674_80@23@H_450_2@ if@H_450_2@(!station2buses.containsKey(r)) { //@H_450_2@ station2buses未添加到hash表中@H_450_2@ @H_674_80@24@H_450_2@ station2buses.put(r, new@H_450_2@ ArrayList<>()); //@H_450_2@ 添加站r并初始化@H_450_2@ @H_674_80@25@H_450_2@ } @H_450_2@@H_674_80@26@H_450_2@ station2buses.get(r).add(i); //@H_450_2@ 将i车加入站r的列表@H_450_2@ @H_674_80@27@H_450_2@ bus2stations.get(i).add(r); //@H_450_2@ 将r车加入站i的列表@H_450_2@ @H_674_80@28@H_450_2@ } @H_450_2@@H_674_80@29@H_450_2@ } @H_450_2@@H_674_80@30@H_450_2@ @H_674_80@31@H_450_2@ //@H_450_2@ 不存在target站@H_450_2@ @H_674_80@32@H_450_2@ if@H_450_2@ (!station2buses.containsKey(target)) return@H_450_2@ -1; @H_450_2@@H_674_80@33@H_450_2@ @H_674_80@34@H_450_2@ //@H_450_2@ 填入车与车之间的直接关系@H_450_2@ @H_674_80@35@H_450_2@ for@H_450_2@(int@H_450_2@ s : station2buses.keySet()) { @H_450_2@@H_674_80@36@H_450_2@ for@H_450_2@(int@H_450_2@ i = 0; i < station2buses.get(s).size(); i++) { @H_450_2@@H_674_80@37@H_450_2@ bus2buses.get(station2buses.get(s).get(i)).addAll(station2buses.get(s)); @H_450_2@@H_674_80@38@H_450_2@ } @H_450_2@@H_674_80@39@H_450_2@ } @H_450_2@@H_674_80@40@H_450_2@ @H_674_80@41@H_450_2@ //@H_450_2@ 遍历当前站台为出发点的所有车，作为dfs的出发车辆@H_450_2@ @H_674_80@42@H_450_2@ for@H_450_2@(int@H_450_2@ cur : station2buses.get(sourcE)) { @H_450_2@@H_674_80@43@H_450_2@ //@H_450_2@ 存放经过出发站台的当前车辆，以及经过目的站台的所有车辆@H_450_2@ @H_674_80@44@H_450_2@ Set<Integer> start = new@H_450_2@ HashSet<>(), end = new@H_450_2@ HashSet<>(); @H_450_2@@H_674_80@45@H_450_2@ //@H_450_2@ 当前车辆加入起点集合@H_450_2@ @H_674_80@46@H_450_2@ start.add(cur); @H_450_2@@H_674_80@47@H_450_2@ //@H_450_2@ 加入终点集合@H_450_2@ @H_674_80@48@H_450_2@ end.addAll(station2buses.get(target)); @H_450_2@@H_674_80@49@H_450_2@ //@H_450_2@ 如果当前车辆的路线中已经包含了目标站台，那么只乘一次车@H_450_2@ @H_674_80@50@H_450_2@ if@H_450_2@(bus2stations.get(cur).contains(target)) return@H_450_2@ 1; @H_450_2@@H_674_80@51@H_450_2@ //@H_450_2@ 广度优先搜索比较@H_450_2@ @H_674_80@52@H_450_2@ res = Math.min(res, bfs(start, end, 2, n)); @H_450_2@@H_674_80@53@H_450_2@ } @H_450_2@@H_674_80@54@H_450_2@ return@H_450_2@ res == n + 1 ? -1 : res; @H_450_2@@H_674_80@55@H_450_2@ } @H_450_2@@H_674_80@56@H_450_2@ @H_674_80@57@H_450_2@ //@H_450_2@ 广度优先搜索，参数分别代表起点集合、终点集合、当前搜索的深度、最大深度@H_450_2@ @H_674_80@58@H_450_2@ private@H_450_2@ int@H_450_2@ bfs(Set<Integer> start, Set<Integer> end, int@H_450_2@ len, int@H_450_2@ maX) { @H_450_2@@H_674_80@59@H_450_2@ //@H_450_2@ 没有车辆或者@H_450_2@ @H_674_80@60@H_450_2@ if@H_450_2@(start.size() == 0 || len > maX) return@H_450_2@ max + 1; @H_450_2@@H_674_80@61@H_450_2@ Set<Integer> next = new@H_450_2@ HashSet<>(); @H_450_2@@H_674_80@62@H_450_2@ //@H_450_2@ 枚举所有车辆@H_450_2@ @H_674_80@63@H_450_2@ for@H_450_2@(int@H_450_2@ cur : start) { @H_450_2@@H_674_80@64@H_450_2@ //@H_450_2@ 该车与其他车辆无连线@H_450_2@ @H_674_80@65@H_450_2@ if@H_450_2@(!bus2buses.containsKey(cur)) conTinue@H_450_2@; @H_450_2@@H_674_80@66@H_450_2@ //@H_450_2@ 枚举与当前车辆有连线的所有车辆@H_450_2@ @H_674_80@67@H_450_2@ for@H_450_2@(int@H_450_2@ b : bus2buses.get(cur)) { @H_450_2@@H_674_80@68@H_450_2@ //@H_450_2@ 如果当前车要经过目标车站，那么可以返回长度@H_450_2@ @H_674_80@69@H_450_2@ if@H_450_2@(end.contains(b)) return@H_450_2@ len; @H_450_2@@H_674_80@70@H_450_2@ //@H_450_2@ 不然需要将当前车辆放到下一个起点集合中再进行搜索@H_450_2@ @H_674_80@71@H_450_2@ else@H_450_2@ next.add(b); @H_450_2@@H_674_80@72@H_450_2@ } @H_450_2@@H_674_80@73@H_450_2@ } @H_450_2@@H_674_80@74@H_450_2@ return@H_450_2@ bfs(next, end, len + 1, maX); @H_450_2@@H_674_80@75@H_450_2@ } @H_450_2@@H_674_80@76@H_450_2@ }
努力去爱周围的每一个人，付出，不一定有收获，但是不付出就一定没有收获！ 给街头卖艺的人零钱，不和深夜还在摆摊的小贩讨价还价。愿我的博客对你有所帮助(*^▽^*)(*^▽^*)！@H_450_2@@H_450_2@@H_450_2@
如果客官喜欢小生的园子，记得关注小生哟，小生会持续更新(#^.^#)(#^.^#)。@H_450_2@
以上是大佬教程为你收集整理的剑指Offer 815. 公交路线全部内容，希望文章能够帮你解决剑指Offer 815. 公交路线所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。