代码随想录算法训练营Day24 | 122.买卖股票的最佳时期、55.跳跃游戏、45.跳跃游戏||

LeetCode 122 买卖股票的最佳时期

本题思路：记录每天的利润值，第一天的为 0 ，第二天的当天的减去前一天的。然后遍历相加为正的利润值。最后得到的结果就是最大利润。

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

LeetCode 55 跳跃游戏

本题思路：记录每一步的覆盖区域，并随时更新覆盖区域。如果覆盖区域大于等于 nums.length - 1。就说明能跳到末尾去。

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(cover, i + nums[i]);
            if(cover >= nums.length-1){
                return true;
            }
        }
        return false;
    }
}

LeetCode 45 跳跃游戏||

本题思路：主要是以下几个

1. 每走一步记录最大的一个覆盖范围
2. 当 i 遍历到当前的最大覆盖范围的时候
   • 如果 i 不等于 nums.length-1的时候，说明还没到末尾，此时就 res++ 说明移动了一次
   • 就要更新当前的覆盖范围为最大覆盖范围
   • 并且如果当前覆盖范围大于等于 nums.length - 1，就要break，退出遍历数组

class Solution {
    public int jump(int[] nums) {
        if(nums.length == 1){
            return 0;
        }
        int cur = 0;
        int next = 0;
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            // 最大覆盖范围
            next = Math.max(i + nums[i], next);
            // 如果当前 i 已经到达了 cur 覆盖区域
            if(i == cur){
                // 并且不是数组末尾
                if( cur != nums.length-1){
                    res++;
                    // 更新 cur 值，最大覆盖范围
                    cur = next;
                    if(cur >= nums.length - 1){
                        break;
                    }
                }
            }
        }
        return res;
    }
}