lc815. 公交路线 求出最少乘坐的公交车数量

求出最少乘坐的公交车数量"/>

lc815. 公交路线 求出最少乘坐的公交车数量

力扣 815

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i
辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 ->
7 -> 1 -> … 这样的车站路线行驶。 现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。
期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

来源：力扣（LeetCode） 链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先，分析题目意思

1. 我需要乘坐公交车，需要换乘多次，求从某个站到达另外一个站的最少换乘次数。无法到达终点，返回-1.
   
2. 两辆公交车如果有相同的公交站，那么这两辆车相邻。
3. 我们需要安装公交车的编号建立邻接链表，使用一个HashMap作为数据结构来进行存储。<key,value>表示 <公交车i,邻接链表集合{j,k,m,n,…}> 。如果公交车i和公交车j具有相同的车站，那么他们相互邻接。
4. 本题的核心解法在于广度优先搜索，利用一个队列存储等待访问的公交车索引，一个队列存储已经访问的公交车索引，不断的从队列的头弹出当前访问的公交车索引，然后遍历当前公交车的邻居节点，更新所有邻居节点到起点的距离。
5. 为什么可以控制起点到终点的换乘次数最少呢？
6. 答：因为如果到中间车站有一条更简单的路的时候，层序遍历（广度优先搜索）会先走那个更简单的路。
   如下图，在第一次访问邻接链表时就已经把终点访问了，如图2的绿色节点。而深度优先搜索是图3，先访问绿色再访问蓝色，是不满足我们广度优先搜索的条件的。
   下面开始写代码：
   第一步，构造邻接链表的代码如下，排列组合，C(n,2) 时间复杂度为O(n^2)

    public Map<Integer, List<Integer>> constructAdjList(int[][] routes){Map<Integer, List<Integer>> map = new HashMap<>();for(int i = 0; i < routes.length; i++){for(int j = i + 1; j < routes.length; j++){if(interact(routes[i], routes[j])){//公交车i和j相邻List<Integer> list = map.getOrDefault(i, new ArrayList<>());list.add(j);map.put(i, list);List<Integer> list1 = map.getOrDefault(j, new ArrayList<>());list1.add(i);map.put(j, list1);}}}return map;}

第二步，完善第一步中判断两个公交车是否相邻的函数

    private boolean interact(int[] route, int[] route1) {for(int i = 0; i < route.length; i++){//如果公交车route1里面查到了route[i]（车站），说明可以换车if(Arrays.binarySearch(route1, route[i]) >= 0) return true;}return false;}

第三步，写主函数，进行初始化，首先如果起点车站和终点车站一样，不需要坐车返回0。其次，因为interact函数里面使用了二分查找，所以对每辆公交车内的车站进行sort。

		if(target == source) return 0;for(int i = 0; i < routes.length; i++) {Arrays.sort(routes[i]);}

第四步，还是初始化，构建领接链表

Map<Integer, List<Integer>> adj = constructAdjList(routes);

第五步，初始化

        List<Integer> targets = new ArrayList<>();//终点集合Map<Integer, Integer> distance = new HashMap<>();//每个公交的距离//使用队列存放等待访问的节点Deque<Integer> queue = new LinkedList<>();//队列Deque<Integer> seen = new LinkedList<>();//已经被访问过了的节点集合for(Integer i : adj.keySet()){distance.put(i, Integer.MAX_VALUE);//无穷大}

第六步，把源节点加入队列中，

		for(int i = 0; i < routes.length; i++){if(Arrays.binarySearch(routes[i], source) >= 0) {queue.add(i);distance.put(i, 0);//设置距离为0seen.add(i);}if(Arrays.binarySearch(routes[i], target) >= 0) {targets.add(i);//构造终点集合}}

第七步，开始遍历队列，每次从队头弹出一个值叫cur，如果cur属于终点集合target，返回distance.get(cur) + 1。就是说，如果当前节点为终点，把原来的车数量加上最后的这辆车。

比如distance原来是get(cur)=0，表示从起点到终点都是一趟车，需要坐0+1趟车。

比如distance原来是get(cur)=1，表示当前车站是中转站，需要坐1+1=2趟车（包括终点站）。

比如distance原来是get(cur)=2，表示当前车站是第二个中转站，需要坐2+1=3趟车（包括终点站）。

代码如下：
广度优先搜索需要保证不能访问已经访问的节点，所以我们遍历所有的邻居，寻找未被访问的节点，更新当前邻居i的距离值，从+无穷到distance.get(cur) + 1；

        while(!queue.isEmpty()){//如果遇到target，记录当前距离返回Integer cur = queue.pollFirst();if(targets.contains(cur)) return distance.get(cur) + 1;for(Integer i : adj.getOrDefault(cur,new ArrayList<>())){//遍历邻居if(!seen.contains(i)){queue.addLast(i);seen.add(i);distance.put(i, distance.get(cur) + 1);}}}return -1;

源代码如下


参考文献：
/
/
/
/