代码随想录Day27 贪心算法02 LeetCode T122 买卖股票的最佳时机II LeetCode T55 跳跃游戏 LeetCode T45 跳跃游戏II

LeetCode T122 买卖股票的最佳时机II

题目链接:122. 买卖股票的最佳时机 II - 力扣（LeetCode）

题目思路:

这题的基本思路还是使用贪心算法,有人可能还在思考啥是贪心算法,这个算法就是你提出一个思想,且找不到明显的反例,这个思路就可以一试,这道题的局部最优就是后一天减去前一天的结果大于0,全局最优就是利润最多,所以我们就有一个思路,for循环从0开始遍历这个数组,只要每次取出两天中的股票差和前一天作比较,如果>0就加入累计和里,小于0则不做处理,最后就能得到所求答案了.

更好理解的解释:

这道题目可能我们只会想，选一个低的买入，再选个高的卖，再选一个低的买入.....循环反复。

如果想到其实最终利润是可以分解的，那么本题就很容易了！

如何分解呢？

假如第 0 天买入，第 3 天卖出，那么利润为：prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度，而不是从 0 天到第 3 天整体去考虑！

那么根据 prices 可以得到每天的利润序列：(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。

题目代码:

class Solution {
    public int maxProfit(int[] prices) {
        int maxP = 0;
        for(int i = 0;i<prices.length-1;i++)
        {
            maxP += Math.max(prices[i+1] - prices[i],0);
        }
        return maxP;
    }
}

LeetCode T55 跳跃游戏

题目链接:55. 跳跃游戏 - 力扣（LeetCode）

题目思路:

这题我们可以换一个思想,将跳跃问题转换为覆盖问题,我们每遇到一个元素就跳到这个元素可以覆盖到的最大位置,当能覆盖下整个数组的时候,就说明能达到,返回true,否则返回false

这题的局部最优是每次取最大跳跃步数 全局最优是最后得到整体最大覆盖范围，看是否能到终点。

题目代码:

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

LeetCode T45 跳跃游戏II

题目链接:45. 跳跃游戏 II - 力扣（LeetCode）

题目思路:

这题我们仍然使用贪心的思路来解决问题,我们仍然是判断每次能跳的最大步数来达到用最少的步数到达终点,这题我们仍然采用覆盖的思想,我们采用一个cur记录下目前的最大覆盖,采用一个next记录下次跳到哪个位置(在覆盖中更新以得到最大距离),一个result记录步数,只要cur没走到终点后面,我进行更新cur的时候就算走了一步,如果到终点或者超越终点了,就跳出循环,直接返回目前记录的步数即可

题目代码:

class Solution {
    public int jump(int[] nums) {
        int result = 0;
        int next = 0;
        int cur = 0;
        for(int i = 0;i<nums.length;i++)
        {
            next = Math.max(i+nums[i],next);
            if(i == cur)
            {
                if(cur<nums.length-1)
                {
                    result++;
                    cur = next;
                }
                else
                {
                    break;
                }
            }
        }
        return result;
    }
}