Let’s look at an easy question as an appetizer for today’s quiz.

Lemonade change

LeetCode Portal 860. Lemonade Change

The title

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.

At a lemonade stand, each lemonade costs 5.Customersarestandinginaqueuetobuyfromyou,andorderoneatatime(intheorderspecifiedbybills).Eachcustomerwillonlybuyonelemo nadeandpaywitheithera5. Customers are standing in a queue to buy from you, and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a 5.Customersarestandinginaqueuetobuyfromyou,andorderoneatatime(intheorderspecifiedbybills).Eachcustomerwillonlybuyonelemo nadeandpaywitheithera5, 10,or10, or 10,or20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.

Note that you don’t have any change in hand at first.

Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with correct change, or false otherwise.

Example:

Input: bills = [5.5.5.10.20]
Output: true
Explanation: 
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.

Input: bills = [5.5.10.10.20]
Output: false
Explanation: 
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can not give change of $15 back because we only have two $10 bills.
Since not every customer received correct change, the answer is false.

Input: bills = [5.5.10]
Output: true

Input: bills = [10.10]
Output: false
Copy the code

Constraints:

  • 1 <= bills.length <= 105
  • bills[i] is either 5.10, or 20.

Thinking line

Their thinking

According to the question, we can record the amount of $5 and $10.

We don’t change $5 when we can change $10 until we finish or find that we can’t change.

Based on the above understanding we can get the following code

/ * * *@param {number[]} bills
 * @return {boolean}* /
var lemonadeChange = function (bills) {
    // Record the amount of $5, $10, can change $10, not $5, until the end, or can not find change.
    const hash = {
        five: 0.ten: 0,}for (let i = 0; i < bills.length; i++) {
        const item = bills[i];
        if (item === 5) {
            hash.five++
        } else if (item === 10) {
            hash.ten++;
            hash.five--;
            if (hash.five < 0) return false;
        } else {
            if (hash.ten > 0) {
                hash.ten--;
                hash.five--;
            } else {
                hash.five -=3;
            }
            if (hash.five < 0 || hash.ten < 0) return false; }}return true;
};
Copy the code

Complexity analysis

  • Time complexity: O(N), where N is the length of bills.
  • Space complexity: O(1).