贪心|122.买卖股票的最佳时机II、55.跳跃游戏、45.跳跃游戏II

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

思路

局部最优：收集每天的正利润，全局最优：求得最大利润。

利润分解

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 0; i < prices.size() - 1; i++){
            int price = prices[i + 1] - prices[i];
            ans += max(price, 0);
        }
        return ans;
    }
};

参考详解

55.跳跃游戏

思路

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

代码：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if(nums.size() == 1) return true;
        for(int i = 0; i <= cover; i++){
            cover = max(nums[i] + i, cover);
            if (cover >= nums.size() - 1) {
                return true;
            }
        }
        return false;
    }
};

参考详解

45.跳跃游戏II

思路

首先 起始位置为0，覆盖范围为零。然后遍历目前的数组，因为本题目一定有解，所以我们记录在目前的覆盖范围内最大的可跳跃值（在目前跳跃范围中我们最远可以到达的值）这个值是目前遍历的index加该index所对应的数组的值（nums[i] + i）。当遍历到当前覆盖范围的末尾，我们首先发现覆盖范围小于数组长度，说明我们需要再跳跃一步，而且我们已经收集到了目前跳跃范围内，能跳跃到的最大位置。此时given我们需要再跳跃一步，我们要更新覆盖范围，这个新范围就是我们之前记录的最大范围值。

代码：

class Solution {
public:
    int jump(vector<int>& nums) {
        int cover = 0, cnt = 0, next = 0;

        if(nums.size() == 1) return cnt;

       for(int i = 0; i <= cover; i++) { //在覆盖范围内判断
           next = max(next, nums[i] + i);   //next 记录的是覆盖范围内的最大下一跳
           if(i == cover) {    //已经到达覆盖范围
               if(cover < nums.size() - 1) { //但还未到达终点
                   cnt++;   //跳数增加
                   cover = next;    //跳到最大下一跳
                   if(cover >= nums.size() - 1) break;  //到达终点结束
               } else break;
           }
       }

        return cnt;
    }
};

参考详解