算法训练营day28 贪心算法②122.买卖股票的最佳时机II、55. 跳跃游戏、 45.跳跃游戏II 、1005.K次取反后最大化的数组和

        贪心算法第二篇博客！感觉这篇博客中的算法都很巧妙，需要动动脑筋

122.买卖股票的最佳时机II

        （这道题可以遍历数组，如果不能遍历的话，就不能做了，需要注意的是：

• 只有一只股票！
• 当前只有买股票或者卖股票的操作

        所以想获得利润至少要两天为一个交易单元。

        如果想到其实最终利润是可以分解的，那么本题就很容易了！——如何分解呢？

• 假如第 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 = 0 for i in range(1, len(prices)):# 左闭右开 result += max(prices[i] - prices[i - 1], 0)# 取大于0的利润累加进结果中 return result

55. 跳跃游戏

        我想的方法：判断0的个数及0之前的可走长度，如果能跨过则可以通过（太麻烦了）

        贪心算法：局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

注释：引用自《代码随想录》

• i 每次移动只能在 cover 的范围内移动，每移动一个元素，cover 得到该元素数值（新的覆盖范围）的补充，让 i 继续移动下去。
• 而 cover 每次只取 max(该元素数值补充后的范围, cover 本身范围)。
• 如果 cover 大于等于了终点下标，直接 return true 就可以了。

        不用拘泥于每次究竟跳几步，而是看覆盖范围，覆盖范围内一定是可以跳过来的，不用管是怎么跳的。

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

45.跳跃游戏II 

        这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。

        核心就是这一步的最远距离没到终点，才需要加1，继续下一步的最远距离……（不断重复）,同时以这一步的最远距离是否到达终点为判断条件，来进行加1

        如何划分“步”的区间，下一步的区间由上一步区间每个元素统计出的最远距离而定，区间起点紧邻上一步

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

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

        第一眼的想法是：排序，统计负数个数

• 如果负数个数l 大于等于k，那么将最小的k个数取反
• 如果负数个数l 小于k，将所有负数取反，同时最小的负数重复取反

bingo!

        贪心的思路，局部最优：让绝对值大的负数变为正数，当前数值达到最大，整体最优：整个数组和达到最大。

        如果将负数都转变为正数了，K依然大于0，此时的问题是一个有序正整数序列，如何转变K次正负，让 数组和 达到最大。

        那么又是一个贪心：局部最优：只找数值最小的正整数进行反转，当前数值和可以达到最大（例如正整数数组{5, 3, 1}，反转1 得到-1 比 反转5得到的-5 大多了），全局最优：整个 数组和 达到最大。

class Solution: def largestSumAfterKNegations(self, nums: List[int], k: int) -> int: nums.sort(key = lambda x: abs(x), reverse = True) # key是排序函数 如 sorted()、list.sort()的参数, 用于指定每个元素在排序前的转换规则 # lambda x: abs(x) 是一个匿名函数, 它接受参数 x 并返回其绝对值 abs(x) # 作用：排序时将根据元素的绝对值大小进行比较，而非元素本身。 # 指定排序结果为降序。若省略该参数，默认升序。 # lambda 函数: add = lambda a, b: a + b for i in range(len(nums)): if nums[i]  0: nums[i] *= -1 k -= 1 if k % 2 == 1: nums[-1] *= -1 result = sum(nums) return result