前言:
目前朋友们对“java贪心算法最短路径”大体比较关心,同学们都想要知道一些“java贪心算法最短路径”的相关文章。那么小编在网络上搜集了一些对于“java贪心算法最短路径””的相关文章,希望我们能喜欢,我们一起来了解一下吧!#头条创作挑战赛#
❝
❤️作者简介:大家好,我是小虚竹。Java领域优质创作者,CSDN博客专家,华为云享专家,掘金年度人气作者,阿里云专家博主,51CTO专家博主
❤️技术活,该赏
❤️点赞 收藏 ⭐再看,养成习惯
❞
零、前言
今天是学习 「JAVA语言」 打卡的第11天,我的学习策略很简单,题海策略+ 费曼学习法。如果能把这100题都认认真真自己实现一遍,那意味着 「JAVA语言」 已经筑基成功了。后面的进阶学习,可以继续跟着我,一起走向架构师之路。
一、题目描述
原题地址--》传送门 题目: 给你一个下标从 0 开始长度为 n 的整数数组 buses ,其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一个下标从 0 开始长度为 m 的整数数组 passengers ,其中 passengers[j] 表示第 j 位乘客的到达时间。所有公交车出发的时间互不相同,所有乘客到达的时间也互不相同。
给你一个整数 capacity ,表示每辆公交车 最多 能容纳的乘客数目。
每位乘客都会搭乘下一辆有座位的公交车。如果你在 y 时刻到达,公交在 x 时刻出发,满足 y <= x 且公交没有满,那么你可以搭乘这一辆公交。最早 到达的乘客优先上车。
返回你可以搭乘公交车的最晚到达公交站时间。你 不能 跟别的乘客同时刻到达。
「注意:数组 buses 和 passengers 不一定是有序的。」
示例:
二、解题思路先来了解下,什么是贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,算法得到的是在某种意义上的局部最优解。我们知道所有公交车到达的时间,和所有乘客上车的时间。现在要求自己能坐上车的最晚时间,意味着:自己是可以插队的。。这就是贪心算法的核心思想这道题不只考察上公交的最晚时间,还要考察能坐上座位。 找到最后一个上车的人,代表着这个人前面都是有上车的。 顺着最后一个人往前面找,可以找到一个空位,答案就出来了。具体实现思路: 数组 buses 和 passengers 不一定是有序的。所以要先对其进行排序。模拟乘客上车的过程:遍历公交车,然后遍历乘客上车当座位满了,或者发车时间到了,这时可得到最后一个上车的乘客反遍历passengers数组,只要有符合条件的,你插队,就是答案了。三、代码详解
package com.xiaoxuzhu;import java.util.Arrays;/** * Description: 求坐上公交的最晚时间(考察贪心算法) * * @author xiaoxuzhu * @version 1.0 * * <pre> * 修改记录: * 修改后版本 修改人 修改日期 修改内容 * 2022/8/20.1 xiaoxuzhu 2022/8/20 Create * </pre> * @date 2022/8/20 */public class Solution { public static void main(String[] args) { //公交车出发的时间 int[] buses = new int[]{20,30,10}; //乘客上车的时间 int[] passengers = new int[]{19,13,26,4,25,11,21}; //座位 int capacity=2; int lastTime = latestTimeCatchTheBus(buses,passengers,capacity); System.out.println(lastTime); } public static int latestTimeCatchTheBus(int[] buses, int[] passengers, int capacity) { //数组 buses 和 passengers 不一定是有序的,先排序 Arrays.sort(buses); Arrays.sort(passengers); //乘客 int passengerIndex = 0; //空坐位个数 int emptySeatNum = 0; //模拟乘客上车的过程 //遍历公交车 for (int buse : buses){ //模拟乘客上车:乘客还没上完;乘客上车的时间要小于等于公交车出发时间 for (emptySeatNum = capacity; passengerIndex < passengers.length && passengers[passengerIndex] <= buse; --emptySeatNum){ //上车 ++passengerIndex; //坐位满了,这辆车就不让上了 if(emptySeatNum <=0 ){ break; } } //最后一个上车的乘客 --passengerIndex; } int ans =0; if(emptySeatNum > 0){ // 在发车时到达公交站 ans= buses[buses.length - 1]; }else{ //你就是上一个上车的乘客 ans= passengers[passengerIndex]; } //顺着最后一个人往前面找,可以找到一个空位 while (passengerIndex >= 0 && passengers[passengerIndex--] == ans){ --ans; // 往前找没人到达的时刻 } return ans; }}
我是虚竹哥,我们下一题见~
标签: #java贪心算法最短路径 #java贪心算法活动安排