860. Lemonade change

Address ：

Power button https://leetcode-cn.com/problems/lemonade-change/

subject ：

On the lemonade stand , The price of each lemonade is  5  dollar . Customers line up to buy your products ,（ By bill bills The order of payment ） Buy one cup at a time .

Each customer only buys a glass of lemonade , Then pay you 5 dollar 、10 US dollars or 20 dollar . You have to give every customer the right change , That is to say, the net transaction is that every customer pays you 5 dollar .

Be careful , You didn't have any change at first .

Give you an array of integers bills , among bills[i] It's No i A customer paid the bill . If you can give every customer the right change , return  true , Otherwise return to false .

Example 1：

Input ：bills = [5,5,5,10,20] Output ：true explain ： front 3 There are customers , We charge in order 3 Zhang 5 Dollar bills . The first 4 There are customers , We take one 10 Dollar bills , And return it 5 dollar . The first 5 There are customers , Let's return one 10 A dollar bill and a 5 Dollar bills . Because all customers get the right change , So we output true.

Example 2：

Input ：bills = [5,5,10,10,20] Output ：false explain ： front 2 There are customers , We charge in order 2 Zhang 5 Dollar bills . For the next 2 Customers , We take one 10 Dollar bills , And return it 5 dollar . For the last customer , We can't return 15 dollar , Because we only have two 10 Dollar bills . Because not every customer gets the right change , So the answer is false.

Example 3：

Input ：bills = [5,5,10] Output ：true

Example 4：

Input ：bills = [10,10] Output ：false

Tips ：

1 <= bills.length <= 105 bills[i]  No  5  Namely  10  or  20

source ： Power button （LeetCode）
link ：https://leetcode-cn.com/problems/lemonade-change
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas ：

The cashier's idea is ok , Cash register yes 3 Lattice , Separately put 5,10,20

No money at work , The lattice is empty , Normal business is ok , No advance payment

Method 1 、 Count array

It is not strictly a counting array operation , It's similar

bool lemonadeChange(int* bills, int billsSize){
    int count[3] = {0};

    for(int i=0; i<billsSize; i++)
    {
        if(bills[i] == 5)
            count[0]++;
        else if(bills[i] == 10)
        {
            if(count[0] != 0)
            {
                count[0]--;
                count[1]++;
            }
            else
                return false;
            
        }
        else if(bills[i] == 20)
        {
            if(count[1] != 0)
            {
                count[1]--;
                if(count[0] != 0)
                {
                    count[0]--;
                    count[2]++;
                }
                else
                    return false;
            }
            else
            {
                if(count[0] >= 3)
                {
                    count[0] -= 3;
                    count[2]++;
                }
                else
                    return false;
            }
        }
    }

    return true;
}

See more brush notes