代码随想录算法训练营day27| 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II 1005.K次取反后最大化的数组和
学习资料：https://programmercarl.com/0122.买卖股票的最佳时机II.html#算法公开课
贪心PART2
学习记录：
122.买卖股票的最佳时间2 （求最大利润，贪心：把所有正数相加；后一天与当天的股票价格差值，若为正就加入利润，若为负，则不加）
点击查看代码
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# 贪心法：计算隔天的价格涨跌值，若为正数就是最佳时机的组成之一
result = 0
for i in range(1, len(prices)): # 从第二天开始，保证i-1存在
add_p = max(prices[i]-prices[i-1], 0) # 若涨价则结果加上该值，若跌就加0
result += add_p
return result
55.跳跃游戏（参数：覆盖范围cover，当前位置i对应的可跳范围i+nums[i]，贪心：求最大覆盖范围，能到最后一个值，就是可跳跃的）
点击查看代码
class Solution:
def canJump(self, nums: List[int]) -> bool:
# 贪心：尽量要大的覆盖范围，最终得最大覆盖范围
if len(nums) == 1: # 如果只有一个元素，那已经跳到最后一个位置了
return True
cover_index = 0 # 求可覆盖范围的最后位置的脚标
for i in range(len(nums)):
if i<=cover_index: # 若最多跳2步，那可跳1步，跳2步，在覆盖范围内随便跳
# 若可跳范围超过覆盖范围，就更新覆盖范围
cover_index = max(cover_index, i+nums[i])
# 覆盖范围脚标大于等于最后一个元素的脚标就满足条件了
if cover_index >= len(nums)-1:
return True
return False
45.跳跃游戏2（比较难，当前可跳范围终点为cur，当前位置i可跳范围next=max(next, i+nums[i]),当到达可跳范围终点却还没到数组最后一位数时，则得继续跳，若next包含数组最后一个数，则刚刚跳完必到，就不用跳下一次了）
点击查看代码
class Solution:
def jump(self, nums: List[int]) -> int:
# 贪心法：看下一次跳跃范围，如果不能到终点，必然就还要再跳下一步
cur = 0 # 当前位置
next = 0 # 下一步最远能跳的位置
result = 0 # 最终需要跳跃的步数
if len(nums)==1: # 如果第一步就是最后一步，就根本不需要跳
return 0
for i in range(len(nums)):
next = max(next, i+nums[i]) # 该步可跳范围内，每个位置能继续跳的范围不同，只有当覆盖范围增大时，才更新最远覆盖位置
if i == cur: # 当索引走到当前位置
if i != len(nums)-1:
result += 1 # 跳下一步了
cur = next # 当前位置更新
if cur >= len(nums)-1: # 说明此时覆盖位置包含了最后一个位置，ok
break
else:
break # 当前位置正好是最后位置，就不用跳了
return result
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 nums[i]<0 and k>0: # 如果该值为负，且还有操作次数
nums[i] *= -1 # 取反
k -= 1 # 操作次数减一
# 如果所有负数都变成正数了，还有操作次数，就全部对绝对值最小的那个数进行取正负操作，如果次数是偶数，则结果不变，如果是奇数，则结果取反。
if k%2 == 1:
nums[-1] *= -1
return sum(nums)
PS:今天补周六的内容，今天天气超好，开心心
吃大餐咯，心心念念的部队火锅（我妈有能让任何菜变香变辣的魔法），圆子汤，还有不停炫的水果，爽歪歪