LeetCode Day 32 Greedy Algorithm (2/6)

Begin greedy algorithm practice day 2

Question 1

122. Best Time to Buy and Sell Stock II

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Purchase at lowest and sell when it is relatively high to ensure maximum benefit. This problem is still using a local optimum to find the global optimum and is a classic greedy problem.

Since you can’t predict the movement of the stock, you need to sell the stock when it is relatively high, and you can’t sell it at that price after that day, so you can only find all the cases where the difference in this series is positive, and then add them up.

Be careful to exclude day0 as [i-1] on that day will be the penultimate position in the array, leading to the wrong result!

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i]-prices[i-1] >= 0:
                profit += prices[i]-prices[i-1]
        return profit

Question 2

55. Jump Game

You are given an integer array nums. You are initially positioned at the array’s first index, and each element in the array represents your maximum jump length at that position.

Return true if you can reach the last index, or false otherwise.

This question is not asking how to jump the shortest number of steps, but just whether it is possible to jump out, so it depends on whether the maximum range of each jump can cover the whole array.

When jumping, the cover is responsible for calculating the range of the jumps, if the cover is larger than the array, then it means that it must be possible to jump out.

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        cover = 0
        if len(nums) == 1: return True
        i = 0
        while i <= cover:
            cover = max(i + nums[i], cover)
            if cover >= len(nums) - 1: return True
            i += 1
        return False

Question 3

45. Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0].

Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where:

• 0 <= j <= nums[i] and
• i + j < n

Return the minimum number of jumps to reach nums[n - 1]. The test cases are generated such that you can reach nums[n - 1].

From the position of the array 0 to the position of the array n-1 even if the jump out, but this question requires the return of the minimum number of jumps. Because test cases can be guaranteed to jump to the position of n-1, so only need to design the method with the least number of times on the line.

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 0
        cur_distance = 0  
        ans = 0  
        next_distance = 0  
        for i in range(len(nums)):
            next_distance = max(nums[i] + i, next_distance) 
            if i == cur_distance:  
                ans += 1  
                cur_distance = next_distance  
                if next_distance >= len(nums) - 1: 
                    break
        
        return ans