当前位置：首页 > news >正文

Day31 || 122.买卖股票的最佳时机 II、55. 跳跃游戏、 45.跳跃游戏II 、1005.K次取反后最大化的数组和

news 2025/8/20 10:17:59

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

题目链接：力扣题目链接

思路：因为是求虽大利润完全可以假设知道第二天涨前一天买入即可，就是求两天只差大于0 的和。

55. 跳跃游戏

题目链接：力扣题目链接

思路：应该从后往前循环判断，只要能在当前位置跳跃到队尾，就可以把队尾更新到当前位置，然后继续循环。

class Solution {boolean res = false;public boolean canJump(int[] nums) {int lastPos = nums.length - 1;for(int i=nums.length - 2;i>=0;i--){if(i+nums[i]>=lastPos){lastPos = i;}}return lastPos == 0;}
}

45.跳跃游戏II

题目链接：力扣题目链接

思路：一开始的想法是动态规划，但是动态规划会超时（不是不能用只是时间复杂度高会超时）。只能使用贪心算法。要计算当前范围能到哪里，另一个就是当前范围跳到的地方下一次最远能到哪里。也就是这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

class Solution {public int jump(int[] nums) {int time=0;int currentEnd = 0; // 当前跳跃的最远边界int farthest = 0;for (int i = 0; i < nums.length - 1; i++) {// 更新能够跳到的最远位置farthest = Math.max(farthest, i + nums[i]);// 当我们到达了当前跳跃的边界if (i == currentEnd) {time++; // 增加跳跃次数currentEnd = farthest; // 更新当前边界为最远位置// 如果当前边界已经超过或到达终点if (currentEnd >= nums.length - 1) {break;}}}return time;}
}