[toc]
关键字
模拟求解，贪心
题目描述
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。
顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
分析
- 题目描述为按照顺序进行找零，进行模拟，只用维护每次找零时商家的零钱状态，对于每位顾客的付账，进行找零
- 进行找零时有多种方案，在本题中，优先用面值大的来找零是最佳方案。
直观上：总额相同的零钱比整钱的灵活性更强
分析：
本题的货币面值：，可能的找零值为
, 因此
不会用来找零（如：100RMB不会用来找零）
现证明在货币总值相同的情况下，更多的面值货币会带来更便于找零
对于找零值
，只能用
对于找零值，可以用
找零，或者用
找零
解题思路
模拟+贪心：
维护商家的零钱状态，对于每次顾客的找零，优先使用面值为10的货币进行找零。
算法
INPUT: bills
OUTPUT: bool（是否可以找零）
money <- [0,0,0]
for bill in bills :
bill -= 5
ten = min( bill/10, money[1] )
bill = bill - ten*10
five = min( bill/5, money[0] )
bill = bill - five*5
if ( bill > 0 )
return false
money[1] -= ten
money[0] -= five
return true
数据结构
无
时间复杂度：
空间复杂度：
代码实现
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
vector<int> money(3) ;
for ( int bill : bills ){
int change = bill - 5 ;
// 判断是否可以找零并记录最优找零方式
int ten_count = min( change/10, money[1] ) ;
int five_count_needed = ( change-10*ten_count )/5 ;
if ( five_count_needed > money[0] ){
return false ;
}
// 更新
money[0] -= five_count_needed ;
money[1] -= ten_count ;
money[bill/10] ++ ;
}
return true ;
}
};
思考与相关问题
1. 如果可以不按照排队顺序进行找零呢？
(例如：bills=[5,10,5,20,5,5], 按照排队顺序不能顺利找零)
sort之后在按照本题的大面值优先找零就可以么？（应该是的）
2. 如果面值更多样，相邻两个面值之间不全是2倍关系呢？
(例如：面值为5，10，20，50，100)
对于已排序的bills=[5,5,5,5,5,5,10,10,20,50]
45 = [(20+20+5),(20+10+10+5),(10+10+10+10+5),...]
对于45，优先使用面值大的仍然可行
95 = [(50+20+20+5),(50+20+10+10+5),(50+20+10+5+5),...]
问题就在于货币50不能直接用20来替换
3.相关题目
递归剪枝
leetcode-39-组合总和
4. 货币面值为什么按1、2、5来设置？
应该是为了方便人们携带。
携带尽量少的（纸张和重量），1-10的任意整数值都可以用两个数值进行+或-来得到，减法对应收付款双方。
PS.
相比较于其他已有的leetcode刷题笔记，我希望能够提供相关的解题分析和部分相关问题的链接，使得大家能获得一个较好的分析与相关问题的比较。
偶尔会进行类似题目的总结工作，有需要的读者可以对这份工作进行关注。
如果你发现有相关的错误或者表述不当不清晰的地方，请进行评论，我会尽快进行核对勘正。
