前言
在前几篇文章中,我们已经覆盖了贪心算法的基本思路和多种题型。这次我将继续分享几道具有挑战性的贪心题目。希望这篇文章能为大家带来更多解题灵感和技巧
柠檬水找零
这道题就是能否给顾客正确找零,你的柠檬水摊位卖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;
}
}
这道题重点还是找钱逻辑要梳理清楚
根据身高重建队列
这道题就是说有一群人站成一排,但是它们的顺序不对,一个二维数组,其中每个数组[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
位置插入一个新元素时,该位置的现有元素以及所有后续元素都会向后移动一位,为新元素腾出位置,该方法十分契合题目重新排序的逻辑
用最少数量的箭引爆气球
这道题的表述看起来非常的复杂,但实际上就是一个区间重合的问题,就是若干个气球的位置[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]
的方式,当处理很大的整数时,两数相减的结果可能会超出整数范围致使报错
总结
通过这几道题目,我们可以看到贪心算法在解决区间、排序、和找零等问题时的强大之处。贪心算法的核心在于每一步都做出局部最优解,从而推导出全局最优解。在解题过程中,贪心策略的选择至关重要,要仔细分析每步局部选择的可行性,并确保这种局部选择能够带来全局最优,希望博主记录的内容能够给大家带来帮助
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » LeetCode刷题日记之贪心算法(四)
发表评论 取消回复