第二十八天 | 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

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  

本题解法很巧妙,大家可以看题思考一下,在看题解。 

https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html 

 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   

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容