欢迎来到尧图网

客户服务 关于我们

您的位置:首页 > 教育 > 培训 > 每日一题——贪心算法

每日一题——贪心算法

2024/11/29 16:57:05 来源:https://blog.csdn.net/2202_75570972/article/details/141227618  浏览:    关键词:每日一题——贪心算法

860. 柠檬水找零 - 力扣(LeetCode)

这道题目乍一看可能没有什么头绪,但是当你仔细想想就会明白一个道理,那就是,《论电子支付的重要性》哈哈哈哈,言归正传,其实很简单无非就是找钱,因为他只会给你5块10块和20块吗,也就是说你的找钱零钱就只有5块和10块,所以你就设置一个遍历,然后判断他给你的是那种情况,然后找钱就完事了,如果是5块,那你不用找钱,只需要five++就完事了,如果是10块那就是给他五块你自己ten++,要是20就有两种情况了,一个是给他一个10块一个五块,但是你还可以给他3张五块,就这么简单

 
class Solution {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){five--;ten++;}else if(bills[i] == 20){if(ten > 0){five--;ten--;}else{five -= 3;}}if(five<0||ten<0){return false;}}return true;}
}

406. 根据身高重建队列 - 力扣(LeetCode)

这个题目我的个人感觉还是比较难得,我看了评论区的思路感觉挺不错就分享出来

上了第一节体育课,老师给大家排好了体操的队伍,可是大家脑子都很笨,记不清自己在哪,老师说,你就看前面有几个比自己高的就行!就像这样:

[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

该上第二节课的时候,大家记住了前面有几个比自己高的,却还是忘记了怎么排,老师见状让学生从高到低排好队,身高一样的,比自己高的越多,越往后面站,像这样:

[[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]

每次让最高的学生出来找自己的位置,第一个高个子[7,0]自然站到了第一个位置:

[[7,0]]

而第二个高个子[7,1]知道有一个人大于等于自己的身高,站在了第一个人身后:

[[7,0],[7,1]]

第三个人[6,1]想了想,有一个人比自己高,那自己肯定站在第二位,于是就插队,现在也站到了第一个人身后:

[[7,0],[6,1],[7,1]]

第四个人[5,0]想了想,没人比自己高,那自己肯定站在第一位,于是就插队,站到了队头:

[[5,0],[7,0],[6,1],[7,1]]

第五个人[5,2]想了想,有两个人比自己高,于是就插队,站到了第二个人后面,也就是第三个位置:

[[5,0],[7,0],[5,2],[6,1],[7,1]]

第六个人[4,4]看了看眼前的队伍,比自己高的人都在里面,他安心的数着前面有四个人比自己高,心安理得的站到了第四个人身后:

[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

其实这道题的大概思路就是这样,只有先让身高高的先进入队伍,后面身高低的才能根据前面高的来找自己的位置,希望看完我的题解能帮助大家理解这道题目!

这样一看就清晰明了多了

然后上代码,我们先排序,从高到低的排序,这个排序怎么排,就是比较身高,高的就在前面,如果一样高,就比较后面那个数,然后就是设置一个动态数组,向里面添加就好了

 
class Solution {public int[][] reconstructQueue(int[][] people) {Arrays.sort(people,new Comparator<int []>(){public int compare(int[] person1,int[] person2){if(person1[0] != person2[0]){return person2[0] - person1[0];}else{return person1[1] - person2[1];}}});List<int[]> ans = new ArrayList<int[]>();for(int[] person : people){ans.add(person[1],person);}return ans.toArray(new int[ans.size()][]);}
}

452. 用最少数量的箭引爆气球 - 力扣(LeetCode)

class Solution {public int findMinArrowShots(int[][] points) {if (points.length == 0) {return 0;}Arrays.sort(points, new Comparator<int[]>() {public int compare(int[] point1, int[] point2) {if (point1[1] > point2[1]) {return 1;} else if (point1[1] < point2[1]) {return -1;} else {return 0;}}});int pos = points[0][1];int ans = 1;for (int[] balloon: points) {if (balloon[0] > pos) {pos = balloon[1];++ans;}}return ans;}
}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com