代码随想录算法训练营第三十二天 | LeetCode 122. 买卖股票的最佳时机 II、55. 跳跃游戏、45. 跳跃游戏 II

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

1.1 思路

1. 本题可以用贪心算法和动态规划解决。这里用贪心算法。本题中你买和卖分别是什么时候？多低时候买算低，多高时候卖算高？这些都不好把握，因此这思路不太好找。
2. 以 prices 数组 [7,1,5,10,3,6,4] 为例，以 p[3]-p[0] 为例，是不是相当于 p3-p2+p2-p1+p1-p0。这一段区间就是相当于我每天的利润和，每天的利润有正有负，而只有正利润相加才对总利润有正向的作用，因此每天的利润就收集正的即可，以 prices 数组为例的利润数组 [-6,4,5,-7,3,-2] 这就是每天的利润组成的数组，这里只收集 4、5、3 就是我们的最大总利润，其实这里的 4、5 就相当于在 p1 买入 p3 卖出得到的利润，3 就相当于在 p4 买入 p5 卖出得到的利润。但此题不需要记录位置，只关注最大总利润
3. 局部最优：只收集每天的正利润
4. 全局最优：收集到的最大总利润。这样的思路找不出明显反例反驳
5. 定义 result 收集每天的正利润，for(int i=1; i<price.length; i++)，i 为什么从 1 开始，我们收集每天的利润是不是起码要从下标 1 的位置才能减去昨天的价格得出当天的利润对吧。然后 result+=Math.max(price[i]-price[i-1]，0)。这样就是加上每天的正利润

1.2 代码

//
// 贪心思路
class Solution {
    public int maxProfit(int[] prices) {
        int result = 0;
        for (int i = 1; i < prices.length; i++) {
            result += Math.max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
}

2. LeetCode 55. 跳跃游戏

2.1 思路

1. 根据题目的 nums 数组我们可以知道在当前位置可以往前跳几步，但比如这个位置数字是 3 的话我是跳 1 步 还是 2 步 还是 3 步呢？跳到下一个元素了又应该跳几步呢？按照这个思路想就很难解出出来了。
2. 我们可以换一个思路：我们不去纠结具体跳几步，只去看覆盖范围，如果在当前位置的覆盖范围能把终点覆盖了就是对了
3. 局部最优：每次跳跃取最大跳跃步数（取最大覆盖范围）
4. 全局最优：最后得到整体的最大覆盖范围，看是否能到终点
5. 定义个 cover=0。如果数组长度就是 1 就是一定可以跳跃到的，因为最开始起始位置已经站在那了。 for(int i=0; i<=cover; i++)，注意这里是<=cover，因为我们遍历是在覆盖范围内遍历的，然后得到可跳跃的步数补充的时候再增加我们的覆盖范围。如何增加覆盖范围呢？cover=Math.max(i+nums[i]，cover)，i+nums[i] 就是我们的最新覆盖范围，但我们新的覆盖范围要比原来的覆盖范围 cover 大才去更新，这样才是我们要的。
6. 如果 cover>=nums.length-1，就是到达最后一个下标的位置了，就 return true。如果结束循环了也没找到那就是 false 了

2.2 代码

//
class Solution {
    public boolean canJump(int[] nums) {
        if (nums.length == 1) {
            return true;
        }
        //覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的
        int coverRange = 0;
        //在覆盖范围内更新最大的覆盖范围
        for (int i = 0; i <= coverRange; i++) {
            coverRange = Math.max(coverRange, i + nums[i]);
            if (coverRange >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

3. LeetCode 45. 跳跃游戏 II

3.1 思路

1. 根据题目的 nums 数组我们可以知道在当前位置可以往前跳几步，这题问的是最少跳多少步可以到我们的终点位置，默认起始位置是下标 0 的位置。
2. 本题的贪心思路：尽可能的去增加我的覆盖范围，用最少的步数去增加我的覆盖范围，一旦覆盖了终点，就输出步数即可
3. 局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一
4. 整体最优：一步尽可能多走，从而达到最少步数
5. if(nums.length==1)就 return 0，因为起点就是终点。然后定义当前的覆盖范围 cur=0，下一步的覆盖范围 next ，一旦当前的覆盖范围 cur 到头了就启动下一步的覆盖范围 next。定义个 result 记录需要的步数。
6. for(int i=0; i<nums.length; i++)在循环一开始就要收集下一步的覆盖范围 next 了，next=Math.max(i+nums[i]，next)，这里只记录最远的覆盖范围。if(i==cur)这里的意思是 i 走到了当前的覆盖范围的终点。再继续判断 if(cur!=nums.length-1)这里的意思是这个位置还不是当前数组的终点，此时就要再继续走一步了也就是 result++，然后 cur 更新 next 即为下一步的覆盖范围，如果是说明 cur 已经覆盖终点了那就 break。前面如果不是终点，在更新了 result 和 cur 之后，再在这里判断 if(cur>=nums.length-1)这里意思是当前覆盖范围已经覆盖终点了，就 break。
7. 最后 return result 就行

3.2 代码

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