代码随想第31天 | 122.买卖股票的最佳时机II 、 55. 跳跃游戏、 45.跳跃游戏II

一、前言

参考文献：代码随想录

今天主要还是贪心，但是是比较难想到的题目，不管那么多吧，直接做吧！

二、买卖股票的最佳时机||

1、思路：

这个思路我确实想不出来，但是这个思路又异常的简单！

只要比较第二天和第一天的股票差值是否大于0，如果大于0那就直接把差价加入到porfit当中去。

就是这么简单的一个思路。。

2、整体代码如下：

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

三、跳跃游戏

1、思路：

我自己想的思路是：

（1）遍历，数组，然后就不断跳最大值（就不断地贪），但是并不能通过所有的用例

代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int temp = 0;
        int i = 0;
        if (nums.size() == 1) {
            return true;
        }

        while (i < nums.size() - 1) {
            temp = i;

                i += nums[i];
            if (i == temp) {
                return false;
            }
        }
        return true;
    }
};

这个用例通过不了，然后就一直缝缝补补，也过不去；

然后我去问了一下GPT教授，他跟我说的思路是：

（1）创建一个for循环，遍历数组nums，再创建一个farthest来记录当前nums中到达的最远距离

（2）每次遍历之前，先检查这个farthest是小于i如果小于说明到达不了i就卡一直接返回false了。

（3）如果最后出来的时候farthest大于等于nums.size() - 1的话就可以返回true了。

2、整体代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        // 记录能jump的最远处
        int farthest = 0;
        for (int i = 0; i < nums.size(); i++) {
            // 比较是否能到达i
            if (i > farthest) {
                return false;
            }
            // 维护farthest
            farthest = max(farthest, i + nums[i]);

        }

        return farthest >= nums.size() - 1;
    }
};

四、跳跃游戏||

1、思路：

我自己想，真想不出来。

看完卡哥的视频后，发现这个主要话是一个覆盖范围的问题：

（1）首先需要定义好边界和最大覆盖范围

（2）遍历所有nums，然后当i == end（边界）时，就可以进行下一步跳了，然后再划分覆盖最大的范围。

（3）在此期间要更新最大的覆盖范围；

2、整体代码如下：

class Solution {
public:
    int jump(vector<int>& nums) {
        // 跳的次数
        int result = 0;
        // 覆盖范围
        int end = 0;
        // 最大范围
        int next = 0;
        if (nums.size() == 1) {
            return result;
        }
        for (int i = 0; i < nums.size(); i++) {
            next = max(next, i  +nums[i]);
            // 说明i到了覆盖范围了，说明需要跳一步了
            if (end == i) {
                // 判断一下有没有到达终点
                if (end < nums.size() - 1) {
                    // 没有就要跳一步了
                    result++;
                    // 重新划分范围
                    end = next;
                    //再判断一下，有没有到达边界
                    if (end >= nums.size() - 1) break;
                } else {
                    break;
                }
            }
        }
        return result;
    }
};