网站建设企业模板丫,网站建设策略阿里巴巴,photoshop手机版安卓,做网站建设公司赚钱题解#xff1a;柠檬水找零(贪心算法) 目录 1.题目2.题解3.参考代码4.证明5.总结 1.题目
题目链接#xff1a;LINK
2.题解
分情况讨论 贪心算法
当顾客为5元时#xff0c;收下当顾客为10元时#xff0c;收下10元并找回5元当顾客为20元时#xff0c;收下20元并找回10… 题解柠檬水找零(贪心算法) 目录 1.题目2.题解3.参考代码4.证明5.总结 1.题目
题目链接LINK
2.题解
分情况讨论 贪心算法
当顾客为5元时收下当顾客为10元时收下10元并找回5元当顾客为20元时收下20元并找回105元或者555元
这里仅20元时候找钱会有分歧所以这里我们用贪心算法即优先留下尽可能多的5元尽快把10元扔出去。
原因5元是“万金油”既可以给10元找零也可以给20元找零但是10元就不能给10元找零。
3.参考代码
class Solution {
public:bool lemonadeChange(vectorint bills) {//哈希数组int arr[2] {0};//05元 110元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元 最优解555(可能我们讨论最优解也为10 5的没意义)
如果这样区别就在于一个10元的问题。 当这个10元在后面没有用那么贪心解和最优解一致因为这个10元没有用。 当这个10元在后面用到了无非就是下面这种情况可以看到无非贪心解和最优解顺序不一样而已。 在某种程度上我觉得贪心算法一定是正确解法的一种所以这个题贪心算法是正确的。
5.总结 EOF
