在线解压zip网站,什么是网络营销系统,管理课程培训,河北城乡建设网站815. 公交路线 - 力扣#xff08;LeetCode#xff09; 一、题目
给你一个数组 routes #xff0c;表示一系列公交线路#xff0c;其中每个 routes[i] 表示一条公交线路#xff0c;第 i 辆公交车将会在上面循环行驶。
例如#xff0c;路线 routes[0] [1, 5, 7] 表示第 … 815. 公交路线 - 力扣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 105routes[i] 中的所有值 互不相同sum(routes[i].length) 1050 routes[i][j] 1060 source, target 106
二、代码
class Solution {// routes数组表示每一种公交线路包括哪些公交站// 0 : [1,3,7,0] 0号公交线路包括1、3、7、0这四个公交站// 1 : [7,9,6,2]// ....// 返回返回换乘次数1 - 返回一共坐了多少次公交。public int numBusesToDestination(int[][] routes, int source, int target) {// 如果起点和目标一致直接返回0if (source target) {return 0;}// 全部的公交线路数int n routes.length;// key : 车站// value : list - 该车站被哪些线路拥有 list中存储的公交线路编号HashMapInteger, ArrayListInteger map new HashMap();// 根据routes数组构造出mapfor (int i 0; i n; i) {// 遍历每一条路线下的每一个车站for (int station : routes[i]) {// 将每一个车站所在的线路编号加入到map中这个车站对应的value中// 如果这个车站还没有创建map就手动创建一个if (!map.containsKey(station)) {map.put(station, new ArrayListInteger());}// station车站被i号路线拥有map.get(station).add(i);}}// 至此通过map就可以快速取出一个车站可以通往哪些公交路线// 宽度优先遍历用的队列里面加入的是公交线路编号ArrayListInteger queue new ArrayList();// 标记路线是否已经被宽度优先遍历过了boolean[] set new boolean[n];// 将起点能够走到的公交线路都取出来这些公交线路就是我们一开始能走的路线for (int route : map.get(source)) {// 将公交线路加入到队列中queue.add(route);// 将这个线路标记为true表示已经遍历到了set[route] true;}// 记录换乘次数int cnt 0;// 开始深度优先遍历每次就直接把一层的都遍历出来while (!queue.isEmpty()) {// 记录下一层宽度遍历的路线列表ArrayListInteger nextRoutes new ArrayList();// 遍历当前队列中的所有线路表示当前能走到的线路for (Integer route : queue) {// 获取这些线路包括车站int[] stations routes[route];// 遍历每一条线路的所有车站for (int station : stations) {// 如果这个车站就是终点直接返回换乘次数1if (station target) {// 之所以加1是因为cnt统计的是换乘次数题目要求要返回乘坐公交车的数量所以要加1return cnt 1;}// 通过这个车站再去找下一次换乘能走到的路线由哪些。利用之前构造的map结构找for (int nextRoute : map.get(station)) {// 保证这个路线没有被遍历过if (!set[nextRoute]) {// 将这个路线加入到nextRoutes中供下一层遍历使用nextRoutes.add(nextRoute);// 将这个路线标记为已经遍历到了set[nextRoute] true;}}}}// 每遍历一层换成次数就加1cnt;// 将下一层的路线列表赋值给queue作为下一轮遍历过程中可以走到的路线列表queue nextRoutes;}// 不能走到就返回-1return -1;}
}
三、解题思路
先把每个站点拥有哪些线路标好这个线路就是指的routes[i]数组的下标把每个站点和一个数字i绑定那么就可以通过这个数字i直接找到routes[i]这个就是这个站点所在的线路。
从source出发先遍历source这个站点的所有所在路线也就遍历出了第一层1、2、3这三条路线表示source这个站点下一步可以走到1、2、3这三条公交线路中公交线路本身也是包含了多个站点的我们也就知道了从source这个点只换乘一次能到达的全新的线路有哪些将这些路线加入到队列中并且再去遍历一下这三条线路所经过的所有车站就能够得到只换乘一次能到达的所有车站有哪些再通过这些车站去找下一次换乘能到达的路线有哪些将这些新路线存储到nextRoute数组中供下一层宽度遍历时使用。
在宽度优先遍历过程中每遍历一层也就是换成次数加1因为每一层的遍历就是从一个站点到另外的线路上期间就是只需要换乘一次。两条线路虽然都有多个站点但是只有两辆不同的车而已。
遍历完第一层后下一层的宽度优先遍历就是在用相同的方法以nextRoute数组中上一轮换乘一次可以来到的全新路线为起点再遍历一下每一个路线只换乘一次就能到达的全新线路然后再去看这些全新线路都能经过的车站都找出来通过这些车站再去找下一轮换乘一次能到达的全新路线有哪些存储到nextRoute数组中在下层的遍历时就会将这些一次换乘就能走到的全新路线加入到队列中。整个流程就是每一次都直接把一整层遍历出来完成深度优先遍历。
因为每次都是向外扩一层按照宽度优先遍历的顺序来遍历所以只要是在这个过程中找到了目的地target站点那么记录的换乘次数一定是最少的。
