[Java 算法] 贪心(1)

Boop_wu

387人浏览 · 2026-03-25 12:12:01

Boop_wu · 2026-03-25 12:12:01 发布

练习一 : 柠檬水找零

class Solution {
    public boolean lemonadeChange(int[] bills) {
        if(bills[0]>5){
            return false;
        }
        int five = 0,ten = 0;
        for(int i = 0;i<bills.length;i++){
            if(bills[i] == 5){
                five++;
            }
            else if(bills[i] == 10){
                ten++;
                five--;
                if(five<0||ten<0){
                    return false;
                }
            }
            else if(bills[i] == 20){
                if(ten>=1&&five>=1){
                    ten--;
                    five--;
                }
                else{
                    five-=3;
                }
                if(five<0||ten<0){
                    return false;
                }
            }

        }
        return true;
    }
}

贪心策略 : 优先用大面额 , 保留小面额万能钱

5 : 不用找零 , 直接收下

10 : 找 5 元 , 并且收下

20 : 找总共 15 元 , 不用收下 ; 找 15 元时 , 优先用 10 块钱找零 , 5 块钱可以留着给 10 块找零

练习二 : 将数组和肩膀的最小操作次数

2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

class Solution {
    public int halveArray(int[] nums) {
       PriorityQueue<Double> maxHeap = new PriorityQueue<Double>((a,b) -> b.compareTo(a));
       double sum = 0;
       for(int x:nums){
        maxHeap.offer((double)x);
        sum+=x;
       }
       int count = 0;
       double k = sum/2;
       while(sum>k){
        double t = maxHeap.poll();
        t = t/2;
        sum-=t;
        count++;
        maxHeap.offer(t);
       }
       return count;
    }
}

贪心策略 : 每次都选最大的数 , 将它减半

通过大根堆找到最大的元素 , 减半再放入大根堆 , 同时修改数组和 , 循环往复 , 便可找到最小的操作次数

练习三 : 最大数

179. 最大数 - 力扣（LeetCode）

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] strs = new String[n];
        for(int i = 0;i<n;i++){
            strs[i] = nums[i]+"";
        }
        Arrays.sort(strs,(a,b)->(b+a).compareTo(a+b));
        StringBuffer sbf = new StringBuffer();
        for(String s:strs){
            sbf.append(s);
        }
        if(sbf.charAt(0) == '0'){
            return "0";
        }
        return sbf.toString();
    }
}