搬家网站模板,做网站的最佳方法,微信公众号小程序怎么发布,舟山外贸营销网站建站122. 买卖股票的最佳时机 II - 力扣#xff08;LeetCode#xff09;
通过做差可以得到利润序列#xff0c;然后只要利润需求的非负数求和就可以#xff0c;因为这里没有手续费#xff0c;某天买入之后买出可以等价为这几天连续买入卖出
class Solution:def maxProfit(se…122. 买卖股票的最佳时机 II - 力扣LeetCode
通过做差可以得到利润序列然后只要利润需求的非负数求和就可以因为这里没有手续费某天买入之后买出可以等价为这几天连续买入卖出
class Solution:def maxProfit(self, prices: List[int]) - int:profit 0for i in range(1, len(prices)):profit max(prices[i]-prices[i-1], 0)return profit55. 跳跃游戏 - 力扣LeetCode
这是一个常见的贪心算法问题。我们从数组的第一个元素开始保持跟踪我们能到达的最远的下标。然后我们迭代数组中的每个元素并更新我们能到达的最远下标。如果我们能到达的最远下标大于或等于数组的长度我们就知道我们可以到达数组的最后一个元素。以下是Python语言实现此算法的代码
def canJump(nums):max_jump 0for i, num in enumerate(nums):if i max_jump:return Falsemax_jump max(max_jump, i num)return True这个函数的工作原理是这样的
max_jump 记录了在迭代过程中可以跳到的最远的下标。enumerate(nums)会遍历数组并且返回每个元素的索引i和值num。如果当前索引i超过了我们可以跳到的最远的下标那么我们就返回False因为我们不能到达当前索引。否则我们更新 max_jump 的值为当前的 max_jump 和 i num 中较大的一个。这是因为从索引i我们可以跳到的最远的下标是 i num。
然后如果我们没有提前返回False那么在遍历完数组后我们就返回True因为我们可以到达数组的最后一个元素。
45. 跳跃游戏 II - 力扣LeetCode
这个问题也是一个贪心算法问题与跳跃游戏 I 的问题相似但是我们现在需要找出到达最后一个下标的最小跳跃次数。
我们可以追踪当前位置的最大跳跃范围并将其与最大跳跃范围内的所有位置的最大跳跃范围进行比较。我们可以保留最大跳跃范围的索引然后当当前位置到达或超过当前的最大跳跃范围时我们更新最大跳跃范围并将跳跃次数加1。
以下是Python语言实现此算法的代码
def jump(nums):n, max_reach, steps, end len(nums), 0, 0, 0for i in range(n - 1):max_reach max(max_reach, i nums[i])if i end:end max_reachsteps 1return steps这个函数的工作原理是这样的
max_reach 记录了在迭代过程中可以跳到的最远的下标。steps 记录了跳跃的次数。end 记录了当前的最大跳跃范围。如果当前索引i等于当前的最大跳跃范围那么我们更新 end 的值为 max_reach并且 steps 加1因为我们需要跳跃到新的位置。
总结
Summary 通过贪心算法解决股票买卖和跳跃游戏问题。
Facts 买卖股票的最佳时机 II: 通过做差可以得到利润序列然后只要利润非负数求和即可没有手续费。 跳跃游戏: 使用贪心算法遍历数组并保持跟踪最远能到达的下标。 跳跃游戏 II: 同样是贪心算法找出到达最后一个下标的最小跳跃次数。保持最大跳跃范围并逐步更新。
