求出最少乘坐的公交车数量"/>
lc815. 公交路线 求出最少乘坐的公交车数量
力扣 815
给你一个数组 routes ,表示一系列公交线路,其中每个 routes[i] 表示一条公交线路,第 i
辆公交车将会在上面循环行驶。例如,路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 ->
7 -> 1 -> … 这样的车站路线行驶。 现在从 source 车站出发(初始时不在公交车上),要前往 target 车站。
期间仅可乘坐公交车。求出 最少乘坐的公交车数量 。如果不可能到达终点车站,返回 -1 。
来源:力扣(LeetCode) 链接:
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
首先,分析题目意思
- 我需要乘坐公交车,需要换乘多次,求从某个站到达另外一个站的最少换乘次数。无法到达终点,返回-1.
- 两辆公交车如果有相同的公交站,那么这两辆车相邻。
- 我们需要安装公交车的编号建立邻接链表,使用一个HashMap作为数据结构来进行存储。<key,value>表示 <公交车i,邻接链表集合{j,k,m,n,…}> 。如果公交车i和公交车j具有相同的车站,那么他们相互邻接。
- 本题的核心解法在于广度优先搜索,利用一个队列存储等待访问的公交车索引,一个队列存储已经访问的公交车索引,不断的从队列的头弹出当前访问的公交车索引,然后遍历当前公交车的邻居节点,更新所有邻居节点到起点的距离。
- 为什么可以控制起点到终点的换乘次数最少呢?
- 答:因为如果到中间车站有一条更简单的路的时候,层序遍历(广度优先搜索)会先走那个更简单的路。
如下图,在第一次访问邻接链表时就已经把终点访问了,如图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;
源代码如下
参考文献:
/
/
/
/
更多推荐
lc815. 公交路线 求出最少乘坐的公交车数量
发布评论