2023年7月4日发(作者：)

leetCode815—公交车路线每⽇⼀题 leetCode，今天分享 leetCode815题，公交车路线问题。——算法参考：左神题⽬：给你⼀个数组 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 <= <= 500.1 <= routes[i].length <= 105routes[i] 中的所有值 互不相同sum(routes[i].length) <= 1050 <= routes[i][j] < 1060 <= source, target < 106解析：本题是“图”类型问题，属于BFS变形问题，传统的BSF是按照节点遍历，本题需要将BFS按照公交路线的等次进⾏遍历。 假设有这样四条环形公交线路，站点有 A B C D ... O 公16个站点，现在我要从 A 站点出发，终点站是 O 站点，那么，我需要先坐1号线从 A -> C，再坐2号线从 C -> I，再坐3号线，从 I -> M，再坐4号线，从 M -> O。总共需要在 C I M三站换成，坐4次公交。由于题⽬给了⼀个⼆维数组 routes[][]，⽤于存储 i 号线对应的所有站点信息，所以，我还需要定义⼀个Map ，其中 key 表⽰站点，value表⽰该站点对应的所有线路集合（如图中每个站点表⽰所⽰）Map> map = new HashMap<>();我需要根据 routes[][] 中内容⽣成 map，具体代码如下：// key：站点 value：路线集合Map> map = new HashMap<>();for (int i = 0; i < ; i++) { for (int j = 0; j < routes[i].length; j++) { // i 号线路经过 j 号站点 if (!nsKey(routes[i][j])) { // 添加该线路 (routes[i][j], new ArrayList<>()); } // 向该站点加⼊真实路线数据 (routes[i][j]).add(i); }}循环结束的时候，map 集合中即可⽣成各个站点的路线集合。然后就是经典的 BFS，定义⼀个队列和⼀个查重表，与传统 BFS 不同的是，队列和查重表中存放的内容是路线，根据初始位置将两个对象初始化（添加 A 位置所有路线—只有1号线），代码如下：// 线路队列Queue queue = new LinkedBlockingQueue<>();// 线路查重集合Set set = new HashSet<>();// 初始化出发位置 source 这条线路for (Integer route : (source)) { (route); (route);}之后，根据层序遍历，根据队列中弹出的节点，获得该路线经过的所有站点，遍历所有站点，如果该站点就是⽬标站点，返回当前遍历次数即可；如果不是当前站点，需要将当前站点包含的所有线路添加进队列，以便新的⼀轮循环。具体代码如下：// 计数器int count = 1;while (!y()) { int size = (); // 按照路线进⾏宽度优先，按照层遍历 for (int i = 0; i < size; i++) { // 获得路线 Integer route = (); // 获得该路线的所有站点 int[] bus = routes[route]; for (int station : bus) { if (station == target) { // 到达终点 return count; } // 没达到终点 // 遍历所有路线，加⼊新的路线 for (Integer nextRoute : (station)) { if (!ns(nextRoute)) { // 没有包含该路线，需要加⼊ (nextRoute); (nextRoute); } } } } count++;}如果遍历完所有路线，都没有到达⽬的地 target，出发点与终点不通，返回-1即可。全部代码如下：static final int arrived = 0;static final int notArrived = -1;/** * @param routes:例如，路线 routes[0] = [1, 5, 7] 表⽰第 0 辆公交车会⼀直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... * 这样的车站路线⾏驶 * @param source：出发点 * @param target：终点 * @return */public static int numBusesToDestination(int[][] routes, int source, int target) { if (source == target) { // 起点就是终点，⽆需后续操作 return arrived; } // key：站点 value：路线集合 Map> map = new HashMap<>(); for (int i = 0; i < ; i++) { for (int j = 0; j < routes[i].length; j++) { // i 号线路经过 j 号站点 if (!nsKey(routes[i][j])) { // 添加该线路 (routes[i][j], new ArrayList<>()); } // 向该站点加⼊真实路线数据 (routes[i][j]).add(i); } } // 线路队列 Queue queue = new LinkedBlockingQueue<>(); // 线路查重集合 Set set = new HashSet<>(); // 初始化出发位置 source 这条线路 for (Integer route : (source)) { (route); (route); } // 计数器 int count = 1; while (!y()) { int size = (); // 按照路线进⾏宽度优先，按照层遍历 for (int i = 0; i < size; i++) { // 获得路线 Integer route = (); // 获得该路线的所有站点 int[] bus = routes[route]; for (int station : bus) { if (station == target) { // 到达终点 return count; } // 没达到终点 // 遍历所有路线，加⼊新的路线 for (Integer nextRoute : (station)) { if (!ns(nextRoute)) { // 没有包含该路线，需要加⼊ (nextRoute); (nextRoute); } } } } count++; } return notArrived;}测试程序：public static void main(String[] args) { int[][] routes = {{7,12},{4,5,15},{6},{15,19},{9,12,13}}; int source = 15, target = 12; int result = numBusesToDestination(routes, source, target); n("result:" + result);}总结：该题属于 leetCode 中 hard 难度，主要思想是基于 BFS，需要根据传⼊的各个路线对应的站点集数组，灵活创建各个站点对应的路线集合，⼆者是相互借⽤的关系，在循环中多次相互使⽤，笔者⼀开始没有创建该集合，⾛了很多弯路。另⼀个点就是需要想到是基于路线的 BFS，⽽不是基于站点的，这个点笔者⼀开始也没想到，⼀上来可能就根据点去 BFS了，但是，题⽬问的是乘坐路线次数，⽽不是经历站点次数，所以，需要往路线这个点去思考。