LeetCode刷题日记之贪心算法（四）
目录
- 前言
- 柠檬水找零
- 根据身高重建队列
- 用最少数量的箭引爆气球
- 总结
前言
在前几篇文章中，我们已经覆盖了贪心算法的基本思路和多种题型。这次我将继续分享几道具有挑战性的贪心题目。希望这篇文章能为大家带来更多解题灵感和技巧✍✍✍
柠檬水找零
LeetCode题目链接
这道题就是能否给顾客正确找零，你的柠檬水摊位卖5美元但你一开始没有零钱，一个整数数组bills,其中每个元素是指第i顾客付的帐，这里注意顾客给的不是5块10块就是20块🤔🤔🤔
我们来思路梳理
-
我们贪心策略就是优先使用大额的零钱进行找零。如果需要找 15 美元，应该优先使用 10 美元加 5 美元的组合，这样可以保留更多的 5 美元零钱，以备后续使用🤔🤔🤔
-
我们进一步来梳理这里的找零情况，可以维护两个变量， 一个记录 5 美元的数量，一个记录 10 美元的数量。
- 如果顾客支付 5 美元，不需要找零，直接增加 5 美元的数量🤔
- 如果顾客支付 10 美元，需要找 5 美元的零，检查是否有足够的 5 美元。如果没有，则返回
false🤔 - 如果顾客支付 20 美元，需要找 15 美元，优先使用 10 美元加 5 美元的组合进行找零，如果没有 10 美元，则需要使用三张 5 美元进行找零。如果也不能找零，返回
false🤔
逻辑梳理的很清楚了，完整贪心代码如下
class Solution {public boolean lemonadeChange(int[] bills) {int five = 0; //记录手头5美元的数量int ten = 0; //记录手头10美元的数量for(int bill : bills){if(bill == 5){//顾客支付5美元five++;}else if(bill == 10){//顾客支付10美元if(five > 0){five--;ten++;}else{return false;}}else{ //顾客支付20元//优先使用一张10美元和两张5美元if(ten > 0 && five > 0){ten--;five--;}else if(five >= 3){five -= 3;}else{return false;}}}return true;}
}
这道题重点还是找钱逻辑要梳理清楚
根据身高重建队列
LeetCode题目链接
这道题就是说有一群人站成一排，但是它们的顺序不对，一个二维数组，其中每个数组[h,k]其中h是这个人的身高，k是他应该站的位置，含义是指这个人前面有k个身高大于他的人🤔🤔🤔
我们来思路梳理
- 首先按照每个人的身高
h从高到低排序。如果身高相同，则按照k（前面有多少个大于等于他的人）从小到大排序。这是因为身高高的人不会受到比他矮的人的影响，身高矮的人则需要依据前面更高的人的数量进行插入🤔🤔🤔 - 按照排好序的数组依次插入队列。每个人的
k值表示在最终队列中他应该插入的位置，即他前面有k个比他身高高的人。由于数组是从高到低排列的，后续的插入不会影响已经插入的高个子🤔🤔🤔 - 贪心策略采用优先按照k值处理高个子，这样当身高矮的人插入时，前面已经有了更高的个子，这样保证插入时不影响已插入的高个子🤔🤔🤔
逻辑梳理完毕，完整代码如下
class Solution {public int[][] reconstructQueue(int[][] people) {//排序Arrays.sort(people, (a, b) -> {if(a[0] == b[0]){ return a[1] - b[1];//按k值从小到大排序}else{return b[0] - a[0];//按身高从高到低排序}});//用列表插入元素List<int[]> queue = new LinkedList<>();for(int[] person : people){queue.add(person[1], person);//按照k值插入位置}return queue.toArray(new int[people.length][2]);}
}
可能不好理解的部分
Arrays.sort()方法通过比较器Comparator来实现升降序逻辑- 当
Comparator返回负数时，a被认为比b“小”，a被排在b前面 - 当
Comparator返回正数时，a被认为比b“大”，a被排在b后面
- 当
这说明Comparator就是默认进行升序排列的，a-b < 0说明a比b小则Comparator会把a排列在前面，反之说明a比b大则会把a放在后面,所以只要把a[1]-b[1]则默认升序k值，反过来b[0]-a[0]则表示降序身高🤔🤔🤔
queue.add(index, element),其中index为要插入的位置，element为要插入的元素，当在指定的index位置插入一个新元素时，该位置的现有元素以及所有后续元素都会向后移动一位，为新元素腾出位置，该方法十分契合题目重新排序的逻辑🤔🤔🤔
用最少数量的箭引爆气球
LeetCode题目链接
这道题的表述看起来非常的复杂，但实际上就是一个区间重合的问题，就是若干个气球的位置[start, end],然后求最小弓箭数量，弓箭的x如果大于start小于end则就能引爆气球🤔🤔🤔
我们来思路梳理
- 我们需要将气球按照它们的结束坐标（
end）进行升序排序。这样做的原因是：如果一支箭可以射中尽可能多的气球，那么它应该射在尽量靠近当前一批气球结束的位置（即最小的xend位置）。这可以确保当前射出的箭能够覆盖更多的气球。所以贪心选择在当前气球的结束坐标xend处射出一支箭，这样可以保证尽可能多的气球被引爆。当遇到下一个气球的起始坐标xstart大于当前箭的射击位置时，意味着需要再射出一支箭。当当前气球无法被已有的箭射中时，更新箭的位置并增加箭的数量🤔🤔🤔
逻辑梳理的很清晰，完整代码如下
class Solution {public int findMinArrowShots(int[][] points) {//按照气球结束位置升序排序Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));int arrows = 1;//初始化箭矢的数量int arrowPos = points[0][1];//初始化当前箭的射出位置for(int i = 1; i < points.length; i++){if(points[i][0] > arrowPos){//如果当前气球的起始位置大于箭的位置，说明需要新的箭arrows++;arrowPos = points[i][1];//更新箭的位置为当前气球的结束位置}}return arrows;}
}
这里有个点和上题排序处理不一样的是Integer.compare(a[1], b[1])不会产生整数溢出问题，这话怎么说呢，如下图所示，如果采用return a[1]-b[1]的方式，当处理很大的整数时，两数相减的结果可能会超出整数范围致使报错🤔🤔🤔
总结
通过这几道题目，我们可以看到贪心算法在解决区间、排序、和找零等问题时的强大之处。贪心算法的核心在于每一步都做出局部最优解，从而推导出全局最优解。在解题过程中，贪心策略的选择至关重要，要仔细分析每步局部选择的可行性，并确保这种局部选择能够带来全局最优，希望博主记录的内容能够给大家带来帮助✍✍✍