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

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

article 2024/10/18 21:55:17

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;
    }
}