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.

Return true if you gave each customer the correct change, false otherwise.

Example 1:

Input: [5,5,5,10,20] Output: true Explanation: We receive 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: [5,5,10] output: trueCopy the code

Example 3:

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

Example 4:

Input: [5,5,10,10,20] Output: false Explanation: From the first two customers, we receive two $5 bills 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

Solution: Greed

  • There are no more than three types of coins, each of which can be dealt with with a strategy
    • 5: five++, change is not considered
    • 10: ten++, and I need change five
    • 20: Need change 15 –> have 10 first change 10, no more change 5 (greedy)
  • The complexity of the
    • Time: O (n), you need to iterate over all the coins
    • Space: O (1), no extra Space
public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0; // Record the number of 5 yuan coins and 10 yuan coins
        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;
}
Copy the code

122. The best time to buy and sell stocks

Given an array, its ith element is the price of a given stock on the ith day.

Design an algorithm to calculate the maximum profit you can make. You can make as many trades (buying and selling a stock multiple times) as possible.

Note: You can’t participate in more than one transaction at a time (you must sell your previous shares before buying again).

Example 1:

Input: [7,1,5,3,6,4] Output: 7 Explanation: If you buy on day 2 (stock price = 1) and sell on day 3 (stock price = 5), the exchange will make a profit = 5-1 = 4. Then, by buying on day 4 (stock price = 3) and selling on day 5 (stock price = 6), the exchange makes a profit = 6-3 = 3.Copy the code

Example 2:

Input: [1,2,3,4,5] Output: 4 Explanation: If you buy on day 1 (stock price = 1) and sell on day 5 (stock price = 5), the exchange will make a profit = 5-1 = 4. Note that you can't buy stocks on day 1 and day 2 and then sell them later. Because you're doing multiple trades at once, you have to sell your shares before you can buy them again.Copy the code

Example 3:

Input: [7,6,4,3,1] output: 0 explanation: in this case, no transaction is completed, so the maximum profit is 0.Copy the code

Tip:

  • 1 <= prices.length <= 3 * 10 ^ 4
  • 0 <= prices[i] <= 10 ^ 4

Solution: Greed

  • If the price is higher than the day before, sell it
  • The complexity of the
    • Time: O (n)
    • Space: O (1)
public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        
        int profit = 0;
        for (int i = 0; i < prices.length - 1; i++)
        	// if (prices[i] < prices[i+1]) profit += (prices[i+1] - prices[i]);
            profit =  prices[i] < prices[i+1]? profit += (prices[i+1] - prices[i]) : profit;
            
        return profit;
    }
Copy the code

455. Distribution of biscuits

Let’s say you’re a great parent and you want to give your kids some cookies. However, no more than one cookie can be given to each child. For each child, there is an appetite gi, which is the minimum size of a cookie to satisfy a child’s appetite; And every cookie j has a size Sj. If sj >= gi, we can assign this cookie J to child I, and the child will be satisfied. Your goal is to satisfy as many children as possible and output this maximum number.

Note:

You can assume that appetite is positive. A child can have no more than one cookie.

Example 1:

Input: [1,2,3], [1,1] Output: 1 Explanation: You have three children and two cookies. The appetites of the three children are: 1,2,3. Even though you have two little cookies, since they're both size 1, you can only satisfy a child with an appetite of 1. So you should print 1.Copy the code

Example 2:

Input: [1,2], [1,2,3] output: 2 explanation: you have two children and three cookies, each with an appetite value of 1,2. The number and size of cookies you have is enough to satisfy all children. So you should print 2.Copy the code

Solution: Greed

  • First meet the needs of small children –> greed
  • The complexity of the
    • Time: O (n)
    • Space: O (1)
 public int findContentChildren(int[] g, int[] s) {
 		// Sort is necessary for matching
        Arrays.sort(g);
        Arrays.sort(s);
        
        int count = 0;
        // Match cookies with children, I traverses cookies, count traverses children
        for (int i = 0; i < s.length && count < g.length; i++) {
            // count++ will be added only if the child is matched by the current cookie
            if (s[i] >= g[count]) count++;
        }
        
        return count;
    }
Copy the code

55. Jump Game ²

Given an array of non-negative integers, you start at the first position in the array.

Each element in the array represents the maximum length you can jump at that location.

Determine if you can reach the last position.

Example 1:

Input: [2,3,1,1,4] output: true explanation: we can jump 1 step from position 0 to position 1, and then jump 3 steps from position 1 to the last position.Copy the code

Example 2:

Input: [3,2,1,0,4] Output: false Explanation: No matter what, you will arrive at index 3. But that position has a maximum jump length of 0, so you'll never get to the last position.Copy the code

Solution: Greed

  • Ideas:
    • Take the biggest step every time (greedy)
    • The root cause of walking is whether 0 can be jumped over -> if not, I > maxIdx will appear
  • The complexity of the
    • Time: O (n)
    • Space: O (1)
public boolean canJump(int[] nums) {
        int maxIdx = 0; // Record the farthest location that can be reached
        for (int i = 0; i < nums.length; i++) {
        	// The farthest position that can be reached before this point < current position
            if (maxIdx < i) return  false;
            // Update the farthest position that can be reached
            maxIdx = Math.max(maxIdx, i + nums[i]);
        }
        return true;
}
Copy the code