代码随想录算法训练营第三十二天 | 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.跳跃游戏 II

本文主要是介绍代码随想录算法训练营第三十二天 | 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.跳跃游戏 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-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%E…
视频讲解：https://www.bilibili.com/video/BV1ev4y1C7na

思路

计算每天股票价格的差值，将正数加起来。

代码

class Solution {public int maxProfit(int[] prices) {int res = 0;for (int i = 1; i < prices.length; i++) {int temp = prices[i] - prices[i - 1];if (temp >= 0) res += temp;}return res;}
}

分析：时间复杂度：O(n)，空间复杂度：O(1)。

55. 跳跃游戏

题目链接：https://leetcode.cn/problems/jump-game/
文档讲解：https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html
视频讲解：https://www.bilibili.com/video/BV1VG4y1X7kB

思路

通过遍历数组，判断从起点开始每个点的覆盖范围有没有覆盖到终点，如果有的话就返回true。
一开始cover的范围是0，随着数组的遍历而增加。
覆盖范围一直维持一个最大值。

cover = Math.max(i + nums[i], cover);

代码

class Solution {public boolean canJump(int[] nums) {if (nums.length == 1) return true;int cover = 0;for (int i = 0; i <= cover; i++) {cover = Math.max(i + nums[i], cover);if (cover >= nums.length - 1) return true; // 终点的距离是nums.length - 1}return false;}
}

分析：时间复杂度：O(n)，空间复杂度：O(1)。

45.跳跃游戏 II

题目链接：https://leetcode.cn/problems/jump-game-ii/
文档讲解：https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html
视频讲解：https://www.bilibili.com/video/BV1Y24y1r7XZ

思路

记录走了几步覆盖到了终点。这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

代码

class Solution {public int jump(int[] nums) {if (nums.length == 1) return 0;int curCover = 0, nextCover = 0, res = 0;for (int i = 0; i < nums.length; i++) {nextCover = Math.max(i + nums[i], nextCover);if (i == curCover) { // 已经走到了当前覆盖范围的最后if (curCover != nums.length - 1) { // 当前覆盖范围还没到终点，就再走一步curCover = nextCover;res++;if (curCover >= nums.length - 1) break;} else break; // 当前覆盖范围覆盖到终点，得到最终结果} }return res;}
}