算法训练营Day35(贪心)

2024-01-07 17:39:45

860.柠檬水找零?

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

秒了

贪心感觉就贪在优先选择10? 5留着后面用吧,和日常生活一样

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

406.根据身高重建队列?

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

class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people,(a,b)->{
            if(a[0]==b[0]) return a[1]-b[1];//如果身高相同,就按照k升序
            return b[0]-a[0];//身高不同,按照身高降序,高个排前面。
        });
        //这样先按身高拍好,插入的时候,就可以按照k且不会破坏高个子k的准确性
        //通过queue收集最终结果
        List<int[]> queue = new LinkedList<>();
        for(int [] p:people){
            queue.add(p[1],p);
        }
        return queue.toArray(new int[people.length][]);
    }
}

452.?用最少数量的箭引爆气球?

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

?重叠区间问题

class Solution {
    public int findMinArrowShots(int[][] points) {
        //左边界排序
        Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
        int count = 1;//第一个位置至少需要一🗡
        for(int i = 1;i<points.length;i++){
            if(points[i][0]>points[i-1][1]){
                count++;
            }else{
                //可以理解为,i的气球和i-1公共部分合并一下
                points[i][1]=Math.min(points[i][1],points[i-1][1]);
            }
        }
        return count;

    }
}

文章来源:https://blog.csdn.net/weixin_65728526/article/details/135350509
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。