现在都用什么网站找事做,邮箱号怎么注册,如何做网站维护,中国建设银行培训网站122.买卖股票的最佳时机II - #x1f517;
讲解 - #x1f517;
方法一#xff1a;
#x1f4a1;这道题自己想到的办法没有解析那么清晰#xff0c;大致思路就是第一步先找到第一个可以买进的时间#xff08;也就是第一个prices[i] prices[i 1]的i#xff09;
讲解 -
方法一
这道题自己想到的办法没有解析那么清晰大致思路就是第一步先找到第一个可以买进的时间也就是第一个prices[i] prices[i 1]的i因为只有prices[i] prices[i 1]才能盈利。后面就是找需要卖出的时间点遇到prices[i] prices[i 1]时在i点卖出。。两种情况直接跳到下一个元素
已经有买入点了又遇到了prices[i] prices[i 1]此时直接跳过因为当前i是卖出点。还没有遇到买入点但是prices[i] prices[i 1]。
但是这种方法体现不出贪心的思想。
class Solution:def maxProfit(self, prices: List[int]) - int:res 0in_val Nonefor i in range(len(prices) - 1):if prices[i] prices[i 1] and not in_val ! None:in_val prices[i]elif prices[i] prices[i 1] and in_val ! None: # nums[i] nums[i 1]res prices[i] - in_valin_val None# 两种情况直接跳到下一个元素# 1. prices[i] prices[i 1] 且 in_val 为空# 2. prices[i] prices[i 1] 但 in_val已经有元素了说明已经买入要找卖出的元素# 处理最后一个元素if len(prices) 2 and prices[-1] prices[-2] and in_val ! None:res prices[-1] - in_valreturn res方法二
解析的思路很清晰计算每一天的盈利只对正盈利相加。 此时就是把利润分解为每天为单位的维度而不是从 0 天到第 3 天整体去考虑 思考一下这种想法其实很有道理没有必要一定要去找买入和卖出点。拿[1, 5, 10]举例在第一天买入并在第三天卖出利润为9这种买卖方式与在第一天买入第二天卖出并买入在第三天卖出的利润是一样的。
class Solution:def maxProfit(self, prices: List[int]) - int:res 0for i in range(1, len(prices)):res prices[i] - prices[i - 1] if prices[i] - prices[i - 1] 0 else 0return res55. 跳跃游戏 -
讲解 - 这道题没看解析写不出来的确落入了惯性思维的圈套。当前位置元素如果是 2我究竟是跳一步呢还是两步呢跳一步时下一步最远可以跳3步但是跳2步下一步最远只能跳1步越想越晕… 其实跳几步无所谓关键在于可跳的覆盖范围不一定非要明确一次究竟跳几步每次取最大的跳跃步数这个就是可以跳跃的覆盖范围。这个范围内别管是怎么跳的反正一定可以跳过来。 那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点 每次移动取最大跳跃步数得到最大的覆盖范围每移动一个单位就更新最大覆盖范围。 贪心算法局部最优解每次取最大跳跃步数取最大覆盖范围整体最优解最后得到整体最大覆盖范围看是否能到终点。 class Solution:def canJump(self, nums: List[int]) - bool:i 0max_len 0while i len(nums) and i max_len:max_len i nums[i] if i nums[i] max_len else max_lenif max_len len(nums) - 1:return Truei 1return False45.跳跃游戏II -
讲解 - 贪心的思路局部最优当前可移动距离尽可能多走如果还没到终点步数再加一。整体最优一步尽可能多走从而达到最少步数。 从图中可以看出来就是移动下标达到了当前覆盖的最远距离下标时步数就要加一来增加覆盖距离。最后的步数就是最少步数。 这里还是有个特殊情况需要考虑当移动下标达到了当前覆盖的最远距离下标时 如果当前覆盖最远距离下标不是是集合终点步数就加一还需要继续走。 如果当前覆盖最远距离下标就是是集合终点步数不用加一因为不能再往后走了。 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 ans
