【贪心】柠檬水找零

2.PNG

解题思路:贪心算法

创建三个变量,分别代表5元、10元、20元的

遍历数组:

1.当顾客给钱为5时,我们将5元的数量+1

2.当顾客给钱为10时,将十元数量+1,如果没有5元了,返回false。若有,5元数量-1

3.当顾客给钱20时,如果同时有一个十元和一个5元,就将10元和五元减一。或者若有三个五元,就将5元减3。若没有,返回false

bool lemonadeChange(int* bills, int billsSize){
    int fiveNum = 0;
    int tenNum = 0;
    int i;
    for(i = 0; i < billsSize; i++) {
        int bill;
        switch(bill = bills[i]) {
            case 5:
            fiveNum++;
                break;
            case 10:
            tenNum++;
            if(fiveNum)
                fiveNum--;
            else 
                return false;
                break;
            case 20:
            if(tenNum && fiveNum) {
                tenNum--;
                fiveNum--;
            } else if(fiveNum >= 3) {
                fiveNum-=3;
            } else {
                return false;
            }
                break;
        }
    }
    return true;
}

1.PNG