思路:
首先分析题目,由于一开始没有零钱,所以如果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; } };