“This is the third day of my participation in the First Challenge 2022, for more details: First Challenge 2022”.

Title description:

860. Lemonade Change – LeetCode (leetcode-cn.com)

At the lemonade stand, a glass of lemonade costs $5. Customers line up to buy your product, one cup at a time (in bill bill order).

Each customer buys a glass of lemonade and pays you $5, $10 or $20. You have to give each customer the correct change, so the net transaction is that each customer pays you $5.

Notice that you don’t have any change to start with.

I’m going to give you an array of integers bills, where Bills [I] is the bill paid by the ith customer. Return true if you gave each customer the correct change, false otherwise.

The sample a

Input: bills = [5,5,5,10,20] Output: true Explanation: We take three $5 bills from the first three customers, in order. At the fourth customer, we took a $10 bill and gave back $5. At the fifth customer, we gave back a $10 bill and a $5 bill. Since all customers got the correct change, we print true.Copy the code

Example 2

Input: bills = [5,5,10,10,20] Output: false Explanation: We take two $5 bills from the first two customers in order. For the next two customers, we charge a $10 bill and give $5 back. For the last customer, we can't refund $15 because we only have two $10 bills. Since not every customer gets the correct change, the answer is false.Copy the code

Example 3

Input: bills = [5,5,10] output: trueCopy the code

Example 4

Input: bills = [10,10] output: falseCopy the code

Tip:

  • 1 <= bills.length <= 10^5
  • bills[i]not5is10or20

Thought analysis

greedy

Because the customer can only give you three bills, namely $5, $10 and $20. Based on this, we can carry out the following classification discussion.

  1. Let’s say the customer gives us $5, and the lemonade costs $5, so we just take it.

  2. If a customer gives us $10, we need to get $5 back. If we don’t have a $5 bill, we can’t get change.

  3. If a customer gives us $20 and we need to get $15 back, there are two combinations: one is a $5 and $10 bill, and the other is three $5 bills. If neither of the two combinations is available, the change will not be correct.

    When correct change is possible, we prefer the first of the two ways to get change, because there are more scenarios that require $5 change than there are scenarios that require $10 change, and we want to keep the $5 bill as much as possible.

AC code

class Solution {
    fun lemonadeChange(bills: IntArray): Boolean {
        var five = 0
        var ten = 0
        for(i in 0 until bills.size) {
            if(bills[i] == 5){
                five++
            } else if(bills[i] == 10) {
                if(five ==0) {
                    return false
                }
                five--
                ten++
            }else {
                if(five > 0 && ten > 0){
                    five--
                    ten--
                } else if(five >= 3) {
                    five -= 3
                } else {
                    return false}}}return true}}Copy the code

conclusion

It’s greedy, but it’s actually very simple.

reference

Lemonade Change – Lemonade Change – Force Buckle (LeetCode) (leetcode-cn.com)