贪心算法part04 算法
● 860.柠檬水找零
● 406.根据身高重建队列
● 452. 用最少数量的箭引爆气球
1.leetcode 860.柠檬水找零
https://leetcode.cn/problems/lemonade-change/description/
class Solution {
public boolean lemonadeChange(int[] bills) {
//看能不能找零
//bills[i] 不是 5 就是 10 或是 20 ,已经固定好了
//遇见5,我们就直接收起来
//遇见10我们就找张5块的给他,10元收起来
//遇见20我们就两种找零方式,优先10+5,再5+5+5
//计每种面额的数量
int five=0;
int ten=0;
int twenty=0;
for(int i=0;i<bills.length;i++){
if(bills[i]==5){
five++;
}else if(bills[i]==10){
if(five>0){
//有钱可以找
five--;
ten++;
}else{
//没钱可以找零
return false;
}
}else if(bills[i]==20){
if(ten>0&&five>0){
//可以找
ten--;
five--;
twenty++;
}else if(five>=3){
//三张五块的,也可以找
five=five-3;
twenty++;
}else{
//没得找零
return false;
}
}
}
//上面都没有返回false
//那就是都能被找零
return true;
}
}
2.leetcode 406.根据身高重建队列
https://leetcode.cn/problems/queue-reconstruction-by-height/description/文章来源:https://www.toymoban.com/news/detail-797777.html
class Solution {
public int[][] reconstructQueue(int[][] people) {
//身高从大到小排,(身高相同的k小的站i前面)
Arrays.sort(people,(a,b)->{
if(a[0]==b[0]){
//身高相同
return a[1]-b[1];
}
return b[0]-a[0];//b-a是降序排列
});
//定义一个存放结果的变量
LinkedList<int[]> result=new LinkedList<>();
for(int i=0;i<people.length;i++){
//将k有值的,不为0的插到对应的位置
//记录要插入的位置
int pesition=people[i][1];//也就是k
result.add(pesition,people[i]);//将值插到指定index去 index,value
}
return result.toArray(new int[people.length][]);
}
}
3.leetcode 452. 用最少数量的箭引爆气球
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/文章来源地址https://www.toymoban.com/news/detail-797777.html
class Solution {
public int findMinArrowShots(int[][] points) {
//画图模拟过程才好容易理解
//如果都没气球,那么都不用射箭
if(points.length==0){return 0;}
//对气球的左边界进行排序
Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
//point气球不为空至少需要一只箭
int count=1;
for(int i=1;i<points.length;i++){
//i从1开始
//如果现在的气球左区间大于上一个气球的右区间
if(points[i][0]>points[i-1][1]){
//证明没有重叠
count++;
}else{
//气球重叠了,那就更新右区间
points[i][1]=Math.min(points[i][1],points[i-1][1]);
}
}
return count;
}
}
到了这里,关于贪心算法part04 算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!