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

注：此篇后文章讲解统一放最后

1.题目
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

2.实现
开始做的时候只是举例分析，也有受到昨天峰谷的影响，其实在这里真正的原理就是利润分解，条件是当天卖出后可当天购买

class Solution:def maxProfit(self, prices: List[int]) -> int:total = 0for i in range(1, len(prices)):diff = prices[i] - prices[i - 1]if diff > 0:total += diffreturn total

55. 跳跃游戏

1.题目
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。

2.复习前
纠结于跳几步

3.实现
从覆盖范围来看，是否能覆盖到终点；
细节：当数组长度为1时的讨论情况，涉及遍历到哪——建议选择边界为n

class Solution:def canJump(self, nums: List[int]) -> bool:n = len(nums)max_length = nums[0]for i in range(n):if max_length >= n - 1:return True if i > max_length or i == n - 1:return False# tmp = nums[i] + i# max_length = tmp if tmp > max_length else max_length  max_length = max(nums[i] + i, max_length)

45.跳跃游戏II

1.题目
给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。

2.复习前：
已知讨论覆盖范围，不知如何决定局部最优

3.实现

class Solution:def jump(self, nums: List[int]) -> int:total = 0n = len(nums)next_distance = 0cur_distance = 0for i in range(n):next_distance = max(nums[i] + i, next_distance)if i == cur_distance:if cur_distance >= n - 1:return total  # 可以直接返回是因为total已经加过1了else:total += 1cur_distance = next_distanceif cur_distance >= n - 1:  # 这里是避免多余的遍历return total    

总结：
1）采用遍历的方式，用next记录了 **到达cur（上一个最远覆盖下标）**时 的最远覆盖范围；区别于我的考虑：单独对这个点跳到最远时，并和两个点之间经过的点比较覆盖范围，这样就限定了cur
2）实现细节：
（1）可以单独讨论长度为1的情况
（2）对cur和next赋初值为0，什么时候更新次数和返回值
值得二刷

文章讲解