Leetcode 860 柠檬水找零

2023-12-22 12:12:33

题意理解

? ? ? ? 已知每杯柠檬水5元,最开始你没有钱,客户可能付给你的面额有5,10,20

? ? ? ? bills=[5,5,5,10,20]表示每单客户付的钱

? ? ? ? 目标:成功完成每单,且合理找零。

? ? ? ? ? ? ? ? ? ?若无零钱找零则失败。

解题思路

? ? ? ? 使用贪心算法的思路来解题,首先明确什么是全局最优解,什么是局部最优解。

? ? ? ? 全局最优解,总是能找零客户的账单

? ? ? ? 局部最优解:为了能找零客户账单,应尽量保存面额小的纸币

? ? ? ? 如20元账单找零:? ?10+5? ? ?5+5+5

? ? ? ? 10元的账单找零:? ? 5

? ? ? ? 即:小面额纸币总是拥有较大的自由度,能为提供更多的找零方式,所以我们优先消耗10元找零,保存尽可能多的5元。

1.贪心解题

我们用five、ten、twenty记录各个面值纸币的数量

public boolean lemonadeChange(int[] bills) {
        int five=0,ten=0,twenty=0;
        //遍历所有账单
        for(int i=0;i<bills.length;i++){
            //付款5元:不找零
            if(bills[i]==5) five++;
            //付款10元:需找零
            if(bills[i]==10){
                if(five>0){//10元可找零
                    five--;
                    ten++;
                }else {
                    return false;//10元无法找零
                }
            }
            //付款20元:需找零
            if(bills[i]==20) {
                if (ten > 0 && five > 0) {//20元可找零:10+5
                    five--;
                    ten--;
                    twenty++;
                } else if (ten == 0 && five >= 3) {//20元可找零:5+5+5
                    five -= 3;
                    twenty++;
                } else {//20元不可找零
                    return false;
                }

            }
        }
        return true;
    }

2.分析?

时间复杂度:O(n)

空间复杂度:O(1)

n为输入数组长度

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