122.买卖股票的最佳时机II
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
55. 跳跃游戏
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。
思路:定义一个最大的覆盖范围 max_reach,初始化为0。对 i in range(len(nums))循环,如果 i <= max_reach,则意味着可以到达当前位置,再根据nums[i]更新max_reach.
45.跳跃游戏II
给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。
思路:还是一样定义max_reach,同时再定义一个jump_limit,两者都初始化为0。jump_limit = 0 就是第0步能达到的范围是0。遍历i in range(n),只要 i > jump_limit,就需要再跳一步,新一步的范围更新为max_reach。
以下是卡哥资料
122.买卖股票的最佳时机II
本题解法很巧妙,大家可以看题思考一下,在看题解。
55. 跳跃游戏
本题如果没接触过,很难想到,所以不要自己憋时间太久,读题思考一会,没思路立刻看题解
https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
45.跳跃游戏II
本题同样不容易想出来。贪心就是这样,有的时候 会感觉简单到离谱,有时候,难的不行,主要是不容易想到。
https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html