Greedy algorithm: lemonade change 🍋

This is the fourth day of my participation in the November Gwen Challenge. Check out the details: The last Gwen Challenge 2021

I also used to brush Leetcode for a period of time, but later I stopped for a long time because I was busy. It’s time to start brushing up again. It’s just a bit of a front end, so I’ll continue writing JavaScript (the most familiar).

Greedy algorithm

Greedy algorithms (also known as greedy algorithms) are those that always make the best choice for the moment when solving a problem. In other words, instead of considering global optimality, the algorithm gets a local optimal solution in a certain sense.

Greedy algorithm can not get the overall optimal solution for all problems, the key is the choice of greedy strategy

I always think the answer to the greedy algorithm of the topic is very clever, sometimes often out of your expectation, such as: “the third largest number, the scheduling of two places”, the scheduling of two places in this problem if you think through, in fact, it is very simple, the key is their own ideas.

Lemonade change

Lemonade change problem is a very classic greedy algorithm problem

Leetcode address

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.

Example:

Enter: bills = [5,5,5,10,20]

Output: true,

Explanation: We take three $5 bills in order from the first three customers.

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.

Do you have enough change for 10 yuan and 20 yuan?

Which of the following is the best way to make change for $20? The greedy algorithm is to achieve local optimal solution.

So I’m going to use 10 plus 5, because 5 dollars is used for both 10 dollars and 20 dollars, and 10 dollars is only used for 20 dollars, so I’m going to use 10 dollars first.

Answer :(I didn’t write optimal code, but I managed to pass the test successfully 💎)

var lemonadeChange = function(bills) {
    // Fives 5 yuan, tens 10 yuan
    let fives = 0, tens = 0;
    if (bills[0] != 5) return false;
    for(let item of bills) {
        if (item == 5) { fives ++; }
        else if (item == 10) {
            if (fives > 0) {
                fives --;
                tens ++;
            } else {
                return false; }}else if (item == 20) {
            if (tens > 0 && fives > 0) {
                fives --;
                tens --;
            } else if (fives > 2) {
                fives -= 3;
            } else {
                return false; }}}return true;
};
Copy the code