代码随想录算法训练营第30天 | 贪心算法 2: 122.买卖股票的最佳时机II、55. 跳跃游戏、45.跳跃游戏II、1005.K次取反后最大化的数组和

122.买卖股票的最佳时机II
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/
代码随想录
https://programmercarl.com/0122.买卖股票的最佳时机II.html#其他语言版本
55.跳跃游戏
https://leetcode.cn/problems/jump-game/description/
代码随想录
https://programmercarl.com/0055.跳跃游戏.html#算法公开课
45.跳跃游戏 II
https://leetcode.cn/problems/jump-game-ii/description/
代码随想录
https://programmercarl.com/0045.跳跃游戏II.html#算法公开课
1005.K次取反后最大化的数组和
https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/description/
代码随想录
https://programmercarl.com/1005.K次取反后最大化的数组和.html#其他语言版本

122.买卖股票的最佳时机 II/=-079

题解思路

• 贪心思路：拆分成每一天买卖赚的钱；只取正的不取负的；

题解代码

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

55. 跳跃游戏

题解思路

• 贪心思路
  • 考虑每一个节点的影响范围即可
    -注意是影响范围 所以不需要大于等于n 而是大于等于n-1步（即影响范围大于等于n-1步）

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

45.跳跃游戏 II

题解思路

• 贪心思路：增加下一步的影响范围
  • 走一步算一步的影响范围
  • 步数计算到影响范围最远的地方再走

题解代码：

class Solution:
    def jump(self, nums: List[int]) -> int:
        if len(nums)<=1: ##考虑不需要走的情况
            return 0
        curr_range,next_range= 0,0
        res = 0
        for i in range(len(nums)):
            next_range = max(i+nums[i],next_range)
            if i == curr_range:
                res = res+1
                curr_range = next_range
                if next_range>=len(nums)-1:##下一步就能走到
                    break
        return res

1005.K次取反后最大化的数组和

题解思路

• 让绝对值大的负数变为正数；
• 如果非要有变为负数的，选取绝对值最小的值作为变小值；

题解代码

class Solution:
    def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
        nums.sort(key=lambda x: abs(x), reverse=True)

        for i in range(len(nums)):
            if k>0 and nums[i]<0:
                nums[i] = -nums[i]
                k -=1
        
        if k%2==1:
            nums[-1] = -nums[-1]
        
        return sum(nums)