欢迎来CILMY23的博客
本篇主题为 零钱兑换的始端---柠檬水找零
个人主页:CILMY23-CSDN博客
个人专栏系列: Python | C++ | C语言 | 数据结构与算法
感谢观看,支持的可以给个一键三连,点赞关注+收藏。
前言:
柠檬水找零:860. 柠檬水找零 - 力扣(LeetCode)
一、题目解析
从题目中我们可以知道以下信息:
- 一开始我们手头没有任何零钱,如果我们一开始没有净交易,那么后续是无法找零钱的
- 顾客一次只买一杯,按照账单bill支付的顺序
- 正确找零返回true,错误或者无法找零返回false
- 顾客只会给我找币值5,10,20美元
二、原理和代码
首先,顾客只会给我三种币值的美元,所以我对这三种情况讨论:
那根据贪心,我们会尽可能保留5美元的,把币值大的先找出去。
代码如下:
class Solution {
public:
bool lemonadeChange(vector<int>& bills)
{
int five = 0;
int ten = 0;
for (auto x : bills)
{
if (x == 5)
{
five++;
}
else
if(x == 10)
{
if(five == 0)
return false;
five--;
ten++;
}
else
{
if(ten && five)
{
ten--;
five--;
}
else
if(five >= 3)
{
five -= 3;
}
else
return false;
}
}
return true;
}
};
三、贪心策略的证明
证明策略:交换论证法
证明目的:把最优解逐步通过交换调整为贪心解
证明过程:
假设贪心解是 a b c d e f ,最优解(正确解)是 E B C D A F ,在不破坏最优解“最优性质”和“正确”的前提下,把最优解调整为贪心解。对上述三种情况进行讨论:
假设顾客只找给我5美元和十美元,最优解和贪心解是没区别的,它们只有三种情况,5美元收下,找五美元和没零钱找不了。
所以重点讨论的地方就是顾客给我二十美元,贪心和最优解不一样的时候怎么办?
假设后面没用到十美元交换,我们可以用十美元来替代我第一次交换的两张5美元
假设后面有用到十美元交换,我们可以用前面第一次的两张5美元来交换后面的十美元,即调整顺序并不影响最优和正确性,于是所有情况我们都论证完毕了。贪心解就是最优解。
感谢各位同伴的支持,本期C++就讲解到这啦,如果你觉得写的不错的话,可以给个一键三连,点赞,关注+收藏,若有不足,欢迎各位在评论区讨论。