本文主要是介绍二刷算法训练营Day32 | 贪心算法(2/6)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
详细布置：
1. 122. 买卖股票的最佳时机 II
2. 55. 跳跃游戏
3. 45. 跳跃游戏 II
4. 1005. K 次取反后最大化的数组和
详细布置：
1. 122. 买卖股票的最佳时机 II
给你一个整数数组
prices，其中prices[i]表示某支股票第i天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
建议：本题解法很巧妙，本题大家可以先自己思考一下然后再看题解，会有惊喜！
这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入.....循环反复。
如果想到其实最终利润是可以分解的，那么本题就很容易了！
如何分解呢？
假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！
那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。
其实我们需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而我们只需要关注最终利润，不需要记录区间。
那么只收集正利润就是贪心所贪的地方！
局部最优：收集每天的正利润，全局最优：求得最大利润。
class Solution:def maxProfit(self, prices: List[int]) -> int:result = 0for i in range(1, len(prices)):result += max(prices[i] - prices[i - 1], 0)return result2. 55. 跳跃游戏
给你一个非负整数数组
nums，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回
true；否则，返回false。
建议：本题如果没接触过，很难想到，所以不要自己憋时间太久，读题思考一会，没思路立刻看题解
其实跳几步无所谓，关键在于可跳的覆盖范围！
不一定非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
这个范围内，别管是怎么跳的，反正一定可以跳过来。
那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！
每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。
贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。
局部最优推出全局最优，找不出反例，试试贪心！
class Solution:def canJump(self, nums: List[int]) -> bool:cover = 0if len(nums) == 1: return Truei = 0# python不支持动态修改for循环中变量,使用while循环代替while i <= cover:cover = max(i + nums[i], cover)if cover >= len(nums) - 1: return Truei += 1return False3. 45. 跳跃游戏 II
给定一个长度为
n的 0 索引整数数组nums。初始位置为nums[0]。每个元素
nums[i]表示从索引i向前跳转的最大长度。换句话说，如果你在nums[i]处，你可以跳转到任意nums[i + j]处:
0 <= j <= nums[i]i + j < n返回到达
nums[n - 1]的最小跳跃次数。生成的测试用例可以到达nums[n - 1]。
建议：本题同样不容易想出来。贪心就是这样，有的时候 会感觉简单到离谱，有时候，难的不行，主要是不容易想到。
本题要计算最少步数，那么就要想清楚什么时候步数才一定要加一呢？
贪心的思路，局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。整体最优：一步尽可能多走，从而达到最少步数。
思路虽然是这样，但在写代码的时候还不能真的能跳多远就跳多远，那样就不知道下一步最远能跳到哪里了。
所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！
这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。
如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。
class Solution:def jump(self, nums):if len(nums) == 1:return 0cur_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: # 当前覆盖最远距离达到数组末尾，不用再做ans++操作，直接结束breakreturn ans4. 1005. K 次取反后最大化的数组和
给你一个整数数组
nums和一个整数k，按以下方法修改该数组：
- 选择某个下标
i并将nums[i]替换为-nums[i]。重复这个过程恰好
k次。可以多次选择同一个下标i。以这种方式修改数组后，返回数组 可能的最大和 。
题的解题步骤为：
- 第一步：将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小
- 第二步：从前向后遍历，遇到负数将其变为正数，同时K--
- 第三步：如果K还大于0，那么反复转变数值最小的元素，将K用完
- 第四步：求和
class Solution:def largestSumAfterKNegations(self, A: List[int], K: int) -> int:A.sort(key=lambda x: abs(x), reverse=True) # 第一步：按照绝对值降序排序数组Afor i in range(len(A)): # 第二步：执行K次取反操作if A[i] < 0 and K > 0:A[i] *= -1K -= 1if K % 2 == 1: # 第三步：如果K还有剩余次数，将绝对值最小的元素取反A[-1] *= -1result = sum(A) # 第四步：计算数组A的元素和return result这篇关于二刷算法训练营Day32 | 贪心算法(2/6)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
