宁波市国家高新区建设局网站,万柏林网站建设,什么是sns网站,互联网网站开发服务合同860.柠檬水找零
参考视频#xff1a;贪心算法#xff0c;看上去复杂#xff0c;其实逻辑都是固定的#xff01;LeetCode#xff1a;860.柠檬水找零_哔哩哔哩_bilibili
解题思路#xff1a;
只需要维护三种金额的数量#xff0c;5#xff0c;10和20。
有如下三种情…860.柠檬水找零
参考视频贪心算法看上去复杂其实逻辑都是固定的LeetCode860.柠檬水找零_哔哩哔哩_bilibili
解题思路
只需要维护三种金额的数量510和20。
有如下三种情况
情况一账单是5直接收下。 情况二账单是10消耗一个5增加一个10 情况三账单是20优先消耗一个10和一个5如果不够再消耗三个5 此时大家就发现 情况一情况二都是固定策略都不用我们来做分析了而唯一不确定的其实在情况三。
而情况三逻辑也不复杂甚至感觉纯模拟就可以了其实情况三这里是有贪心的。
账单是20的情况为什么要优先消耗一个10和一个5呢
因为美元10只能给账单20找零而美元5可以给账单10和账单20找零美元5更万能
所以局部最优遇到账单20优先消耗美元10完成本次找零。全局最优完成全部账单的找零。
局部最优可以推出全局最优并找不出反例那么就试试贪心算法
public class Leetcode860 {public boolean lemonadeChange(int[] bills) {int five 0;int ten 0;for (int i 0; i bills.length; i) {if (bills[i] 5) {five;} else if (bills[i] 10) {if (five 1) {return false;}five--;ten;} else if (bills[i] 20) {if (ten 1 five 1) {ten--;five--;} else if (five 3) {five - 3;} else {return false;}}}return true;}
}
406.根据身高重建队列
解题思路
那么按照身高h来排序呢身高一定是从大到小排身高相同的话则k小的站前面让高个子在前面。
此时我们可以确定一个维度了就是身高前面的节点一定都比本节点高
那么只需要按照k为下标重新插入队列就可以了为什么呢
public class Leetcode406 {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people, (a, b) - {if (a[0] b[0]) return a[1] - b[1];return b[0] - a[0];});LinkedListint[] que new LinkedList();for (int[] p : people) {que.add(p[1], p);}return que.toArray(new int[people.length][]);}
}
452. 用最少数量的箭引爆气球
解题思路
如何使用最少的弓箭呢
直觉上来看貌似只射重叠最多的气球用的弓箭一定最少那么有没有当前重叠了三个气球我射两个留下一个和后面的一起射这样弓箭用的更少的情况呢
尝试一下举反例发现没有这种情况。
那么就试一试贪心吧局部最优当气球出现重叠一起射所用弓箭最少。全局最优把所有气球射爆所用弓箭最少。
算法确定下来了那么如何模拟气球射爆的过程呢是在数组中移除元素还是做标记呢
如果真实的模拟射气球的过程应该射一个气球数组就remove一个元素这样最直观毕竟气球被射了。
但仔细思考一下就发现如果把气球排序之后从前到后遍历气球被射过的气球仅仅跳过就行了没有必要让气球数组remove气球只要记录一下箭的数量就可以了。
以上为思考过程已经确定下来使用贪心了那么开始解题。
为了让气球尽可能的重叠需要对数组进行排序。
那么按照气球起始位置排序还是按照气球终止位置排序呢
其实都可以只不过对应的遍历顺序不同我就按照气球的起始位置排序了。
既然按照起始位置排序那么就从前向后遍历气球数组靠左尽可能让气球重复。
从前向后遍历遇到重叠的气球了怎么办
如果气球重叠了重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。
以题目示例 [[10,16],[2,8],[1,6],[7,12]]为例如图方便起见已经排序
public class Leetcode452 {public int findMinArrowShots(int[][] points) {Arrays.sort(points, (a, b) - Integer.compare(a[0], b[0]));int res 0;for (int i 1; i points.length; i) {if (points[i][0] points[i - 1][1]) {res;}if (points[i][0] points[i - 1][1]) {points[i][1] Math.min(points[i - 1][1], points[i][1]);}}return res;}
}
