【算法】贪心算法——柠檬水找零

题解：柠檬水找零(贪心算法)

1.题目

题目链接：LINK

2.题解

分情况讨论 + 贪心算法

• 当顾客为5元时，收下
• 当顾客为10元时，收下10元并找回5元
• 当顾客为20元时，收下20元并找回10+5元或者5+5+5元

这里仅20元时候找钱会有分歧，所以这里我们用贪心算法，即优先留下尽可能多的5元，尽快把10元扔出去。

原因：5元是“万金油”，既可以给10元找零，也可以给20元找零，但是10元就不能给10元找零。

3.参考代码

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        //哈希数组
        int arr[2] = {0};
        //0：5元 1：10元
        for(auto& money: bills)
        {
            if(money == 5) arr[0]++;
            else if(money == 10) arr[1]++,arr[0]--;// 收钱 + 找钱
            else
            {
                //收钱
                arr[2]++;
                
                //找钱
                if(arr[1] >= 1 && arr[0] >= 1) arr[1]--,arr[0]--;
                else arr[0]-=3;
            } 

            if(arr[0] < 0) return false;
        }

        return true;
    }
};

4.证明

证明思路：交换论证法
如果最优解和贪心解可以相互交换，即证明贪心解法有效。
注：最优解这里可以认为一定正确的解法。

因为在顾客给5元或者10元时候，找钱策略是唯一的，因而没有区别，我们这里只讨论顾客给20元的场景。

如果顾客给20元，
贪心算法：10 + 5元
最优解：5+5+5(可能，我们讨论最优解也为10 + 5的没意义)

如果这样，区别就在于一个10元的问题。
当这个10元在后面没有用，那么贪心解和最优解一致，因为这个10元没有用。
当这个10元在后面用到了，无非就是下面这种情况，可以看到无非贪心解和最优解顺序不一样而已。

在某种程度上，我觉得贪心算法一定是正确解法的一种，所以这个题贪心算法是正确的。

5.总结

---

EOF

原文地址：https://blog.csdn.net/2302_79031646/article/details/139349290

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！