The title

860. Lemonade change

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.

Ideas:

  1. Apply an array of pokets, which are our pockets, and walk through the target array, which is the same thing as everybody buying lemonade and paying for it
  2. And when you get a 5, you put in pokets,
  3. Return false; if there is a 10, put in a 10 and take out a 5
  4. If 20 is encountered, first determine whether there is a 10 and a 5, take out and put in a 20, if not, determine whether there are three 5, take out and put in a 20, otherwise the business can not return false

Directly on the most violent code:

/** * @param {number[]} bills * @return {boolean} */ var lemonadeChange = function(bills) { let pockets = []; for(let i=0; i<bills.length; i++){ if(bills[i] == 5){ pockets.push(5) }else if(bills[i] == 10){ if(pockets.indexOf(5)>-1){ pockets.splice(pockets.indexOf(5),1); pockets.push(10); }else{ return false; } }else if(bills[i] == 20){ if(pockets.indexOf(10)>-1 && pockets.indexOf(5)>-1){ pockets.splice(pockets.indexOf(10),1); pockets.splice(pockets.indexOf(5),1); pockets.push(20); }else if(pockets.indexOf(5)>-1){ let count = 0 for(let i=0; i<pockets.length; i++){ if(pockets[i] == 5){ count++; } } if(count >=3){ pockets.splice(pockets.indexOf(5),1); pockets.splice(pockets.indexOf(5),1); pockets.splice(pockets.indexOf(5),1); pockets.push(20); }else{ return false; } }else{ return false; } } } return true; };Copy the code

It takes an explosion…

So how do you optimize

First of all, our time is mainly consumed by the frequent splice processing array, so can not use array?

Of course I can

Whether we can do business or not, we just need to consider whether there are enough 5’s and 10’s in hand when we collect the money, so we only need to record the number of 5’s and 10’s

The logic is roughly the same

  1. Declare two variables, five and ten, record the number of $5 and $10 cards in your pocket, and start a business by iterating through the target array
  2. If you hit 5, you have five++
  3. Return false (10++, 5–); return false (10++, 5–)
  4. If 20 is encountered, the first check whether there is a 10 and a 5, 10–,5–, no check whether there are three 5, five -= 3, otherwise the business can not return false.

You don’t have to worry about the number of 20.

The code is as follows:

/** * @param {number[]} bills * @return {boolean} */ var lemonadeChange = function(bills) { let five = 0, ten = 0; for(let i=0; i<bills.length; i++){ if(bills[i] == 5){ five++; }else if(bills[i] == 10){ if(five<=0) return false; five--; ten++; }else if(bills[i] == 20){ if(ten >0 && five >0){ five--; ten--; }else{ five -= 3; } if(five<0||ten<0){ return false } } } return five>=0 && ten >=0; };Copy the code