思路:
首先分析题目,由于一开始没有零钱,所以如果bills[0] != 5 直接false即可。
由于要找零,所以要把现在每张钞票的张数记录下来,这里直接用变量就可以了,不用再开hash数组。
分析:如果是5元,收下即可;如果是10元,要找一张5元;如果是20元,有两种方法:5+10 || 5+5+5,通过分析可以看到对于20的处理方案就是要点。因为5元用的最多,消耗最大,所以肯定要省着点,所以优先采取方案A。
class Solution {
public:
bool lemonadeChange(vector<int>& bills) {
if(bills[0]!=5)
return false;
int five=0,ten=0;
for(int i=0;i<bills.size();i++)
{
if(bills[i]==5)
five++;
if(bills[i]==10)
{
if(five==0)//花光了
return false;
five--;
ten++;
}
if(bills[i]==20)
{
if(five==0)
return false;//两个方案都要用到5元,所以如果没有的话直接返回false
if(ten)//有10块的钱,这个if要放在上面
{
ten--;
five--;
}
else
{
five-=3;
if(five<0)
return false;
}
}
}
return true;
}
};