leetcode815 公交路线

公交路线"/>

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

解析：最开始的想法是希望通过并查集来解决，但是只能解决是否能到达，而不能计算出最少乘坐的公交车路线。正确解法应该是使用广度优先搜索求最短路径。将每条公交线看成一个点，点与点之间是否连通就看两条公交线是否有相交点；将包含source车站的点作为初始点（注意：可能不止有一个初始点），另外，由于终点也可能有多个，所以可选择虚拟一个终点len，将包含target车站的路线加一条虚拟线路表示能到达终点。至此，就已经构建出一个图，然后只需要使用广度优先遍历求最短路线即可。

   public static int numBusesToDestination(int[][] routes, int source, int target) {if(source == target)return 0;ArrayList<ArrayList<Integer>> graph = new ArrayList<>();int len = routes.length;//将每辆车看成一个点，构建图for(int i = 0;i < len;i++)graph.add(new ArrayList<>());for(int i = 0;i < len;i++){for(int j = i + 1;j < len;j++){if(isLiantong(routes[i],routes[j])){graph.get(i).add(j);graph.get(j).add(i);}}}HashSet<Integer> set = new HashSet<>();for(int i = 0;i < routes.length;i++){for(int j = 0;j < routes[i].length;j++){if(routes[i][j] == source)set.add(i);//起点if(routes[i][j] == target)graph.get(i).add(len);//虚拟终点}}boolean[] visit = new boolean[routes.length];return bfs(graph,set,len,visit);}private static int bfs(ArrayList<ArrayList<Integer>> graph, HashSet<Integer> from, int to, boolean[] visit) {if(from.contains(to))return 0;HashSet<Integer> set = new HashSet<>();for(int i : from){if(!visit[i]){set.addAll(graph.get(i));visit[i] = true;}}if(set.size() == 0)return -1;int r = bfs(graph,set,to,visit);return r == -1 ? r : r + 1;//易错！！！不能直接返回r+1}private static boolean isLiantong(int[] a, int[] b) {Arrays.sort(a);Arrays.sort(b);int i = 0,j = 0;while(i < a.length && j < b.length){if(a[i] == b[j])return true;if(a[i] > b[j])j++;elsei++;}return false;}