代码随想录训练营Day32：● 122.买卖股票的最佳时机II ● 55. 跳跃游戏 ● 45.跳跃游戏II

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

题目链接

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

题目描述

思路

看完视频讲解之后豁然开朗啊简直了！！！

统计后一天减去前一天，差值为正数的，再把他们加起来，就是获利最大的了

class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        //要从 1 开始，因为第 0 天刚刚买入，还没有利息
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i]-prices[i-1],0);
        }
        return result;
    }
}

55. 跳跃游戏

题目链接

https://leetcode.cn/problems/jump-game/description/

题目描述

思路

class Solution {
    public boolean canJump(int[] nums) {
        if(nums.length==1) return true;
        int cover = 0;
        //cover 表示每个位置能够覆盖的长度
        // 在 cover 个长度里边走，不能超过 cover
        for (int i = 0; i <= cover; i++) {
            cover = Math.max(i+nums[i],cover);
            if(cover>= nums.length-1){
                return true;
            }
        }
        return false;
    }
}

45.跳跃游戏II

题目链接

https://leetcode.cn/problems/jump-game-ii/description/

题目描述

思路

太难想了/(ㄒoㄒ)/~~
没太听明白，得再看看

class Solution {
    public int jump(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length == 1) {
            return 0;
        }
        //记录跳跃的次数
        int count=0;
        //当前的覆盖最大区域
        int curDistance = 0;
        //最大的覆盖区域
        int maxDistance = 0;
        for (int i = 0; i < nums.length; i++) {
            //在可覆盖区域内更新最大的覆盖区域
            maxDistance = Math.max(maxDistance,i+nums[i]);
            //说明当前一步，再跳一步就到达了末尾
            if (maxDistance>=nums.length-1){
                count++;
                break;
            }
            //走到当前覆盖的最大区域时，更新下一步可达的最大区域
            if (i==curDistance){
                curDistance = maxDistance;
                count++;
            }
        }
        return count;
    }
}