力扣860 柠檬水找零(C++,附思路)

力扣860 柠檬水找零(C++,附思路)

思路:

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

上一篇:PAT乙级 1023 组个最小数 (20 分)


下一篇:n皇后问题