代码随想录算法训练营DAY32|C++贪心算法Part.2|122.买卖股票的最佳时机II、55.跳跃游戏、45.跳跃游戏II

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

力扣题目链接

文章讲解：122.买卖股票的最佳时机II

视频讲解：

状态：本题可以用动态规划，但是贪心也是能做出来的

本题中首先要明确两个：

• 只有一只股票；
• 当前只有买股票或者卖股票的操作

想要获得利润至少要两天为一个交易单元

思路

本题最难受的就是低点和高点不太好找， 但是，如果我们从贪心的角度来思考一个局部问题。

如果我们根据当前的股票价格数组，把利润分解为每天为单位的维度。这样我们就可以得到每天的利润序列：

现在我们可以得出我们的

局部最优：收集每天的正利润；

result += max(prices[i] - prices[i - 1], 0);
1

全局最优：求得最大利润

CPP代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int result = 0;
        for (int i = 1; i < prices.size(); i++) {
            result += max(prices[i] - prices[i - 1], 0);
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10

55.跳跃游戏

力扣题目链接

文章链接：55.跳跃游戏

视频链接：贪心算法，怎么跳跃不重要，关键在覆盖范围 | LeetCode：55.跳跃游戏

状态：感觉贪心算法的题都好有意思，但是这题挺难想，局部整成啥呢？

思路

脑经急转弯：只要每次得到最大的可跳范围就行。根本就不需要我们是跳一步两步还是三步。

那么这个问题就转化为跳跃覆盖范围究竟可不可以覆盖到终点！

每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。

贪心算法局部最优解：每次取最大跳跃步数（取最大覆盖范围）；

整体最优解：最后得到整体最大覆盖范围，看是否能到终点。

从上文可以看出，我们要比较当前范围下能扩充的最终范围。

CPP代码

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
            cover = max(i + nums[i], cover);
            if (cover >= nums.size() - 1) return true; // 说明可以覆盖到终点了
        }
        return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

45.跳跃游戏II

力扣题目链接

文章链接：45.跳跃游戏II

视频链接：贪心算法，最少跳几步还得看覆盖范围 | LeetCode： 45.跳跃游戏 II

状态：

思路

在[55.跳跃游戏](# 55.跳跃游戏)中，重点在于能够跳到终点；

在本题中，重点在于最少多少步跳到终点。

但是一个基本思路还是类似的，就是关于覆盖范围的概念。我们每一步都应该是尽可能得去增加我们的覆盖范围。

所以本题可以这样理解：我们用最少的步数去增加我们的覆盖范围。

本题的贪心思路如下：

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加1。

整体最优：一步尽可能多走，从而达到最少步数。

下列图中覆盖范围的意义就在于，只要是红色的区域，最多两步一定可以到。

方法一

首先要明确的如果数组长度只有1，那么直接返回0；

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

其次，明确当前覆盖最远范围的下标和下一步覆盖最远范围的下标；

int curDistance = 0, ans = 0, nexDistance = 0;
1

我们开始遍历数组，并且要开始收集下一步能跳多远，并且更新步数。

for (i = 0; i < nums.zie(); i++){
  //nextDistance =  i + nums[i]; 下一步能跳多远，但是我们应该记录下一步里跳得最远的
  nexDistance = max(nexDistance, i + nums[i]);
  if (i == curDistance){//遇到当前覆盖最远距离的下标
    ans++; //走一步
    curDistance = nextDistance//更新当前最远距离下标
    if (nextDistance >= nums.size() - 1) break;
  } 
}
return ans;
1
2
3
4
5
6
7
8
9
10

最关键的就是搞清楚什么时候步数+1。

• 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
• 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。

个人觉得思路很结点，带式代码还是很绕的。

代码改善

这里也是一种思路的改善，就是我们不再关注当前覆盖最远距离的下标是不是终点。

让移动下标指向nums.size - 2

• 如果移动下标等于当前覆盖最大距离下标， 需要再走一步（即 ans++），因为最后一步一定是可以到的终点。（题目假设总是可以到达数组的最后一个位置），如图：
• 如果移动下标不等于当前覆盖最大距离下标，说明当前覆盖最远距离就可以直接达到终点了，不需要再走一步。

CPP代码

//方法一
class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curDistance = nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）
                if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

//方法二
class Solution {
public:
    int jump(vector<int>& nums) {
        int curDistance = 0;    // 当前覆盖的最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖的最远距离下标
        for (int i = 0; i < nums.size() - 1; i++) { // 注意这里是小于nums.size() - 1，这是关键所在
            nextDistance = max(nums[i] + i, nextDistance); // 更新下一步覆盖的最远距离下标
            if (i == curDistance) {                 // 遇到当前覆盖的最远距离下标
                curDistance = nextDistance;         // 更新当前覆盖的最远距离下标
                ans++;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17