https://leetcode.com/problems/lemonade-change/description/
At a lemonade stand, each lemonade costs
$5.
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, $10, or $20 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.
Return
true if and only if you can provide every customer with correct change.
When the customer gives us
$20, we have two options:- To give tree
$5in return - To give one
$5and one$10.
On insight is that the second option (if possible) is always better than the first one.
Because two
Because two
$5 in hand is always better than one $10
Explanation:
Count the number of
If cutomer pay with
If cutomer pay with
If cutomer pay with
Check if five is positive, otherwise return false.
Count the number of
$5 and $10 in hand.If cutomer pay with
$5: five++If cutomer pay with
$10: ten++, five--If cutomer pay with
$20: ten--, five-- or five -= 3Check if five is positive, otherwise return false.
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int i : bills) {
if (i == 5) five++;
else if (i == 10) {five--; ten++;}
else if (ten > 0) {ten--; five--;}
else five -= 3;
if (five < 0) return false;
}
return true;
}
public boolean lemonadeChange(int[] bills) {
int five = 0, ten = 0;
for (int bill : bills) {
if (bill == 5)
five++;
else if (bill == 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;
}
