122.买卖股票的最佳时机II
文档和视频讲解:代码随想录(programmercarl.com)
状态:ac
用时:0.5h
思路:每次选择低的时候买入,高的时候卖出,且期间股价一次上升,这样的利润是最高的。而这期间的利润是可以分割的,如
这可以等价于第0天买入,第3天卖出。
因此这题在贪心思想中,局部最优就是两天之间为正利润,全局最优就是所有的正利润相加。
代码:
55. 跳跃游戏
文档和视频讲解:代码随想录(programmercarl.com)
状态:未ac
用时:1h
思路:每次跳几步不关键,关键是能跳几步,也就是每次跳跃覆盖范围。因此问题可以转换为最终跳跃覆盖范围是否覆盖终点。贪心的局部最优是每次取最大跳跃步数,整体最优是得到整体最大覆盖范围是否覆盖终点。
代码:
45.跳跃游戏II
文档和视频讲解:代码随想录(programmercarl.com)
状态:未ac
用时:1h
思路:以最小的步数增加覆盖范围,当覆盖范围覆盖重点,得到的就是最小步数。需要统计两个最大范围,一个是当前最大,一个是下一个最大。如果下标移动到了当前最大范围还是没到达终点,则需要步数加一进入下一次最大范围。
代码: