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

参考

代码随想录

题目一：LeetCode 122.买卖股票的最佳时机II

按照自己的想法，无非就是在最低点买入，在最高点卖出，因此只需要找到成对的极小值和极大值，就可以计算利润了。代码实现如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int index = 0;
        int profit = 0;
        bool flag1,flag2;
        int value1,value2;
        vector<pair<int,int>> vec;
        while(index < prices.size()){
            flag1 = flag2 = false;
            //求极小值
            value1 = prices[index];
            for(;index < prices.size(); index++){
                if(prices[index] <= value1) value1 = prices[index]; //这里要包含等号
                else{ //下一个值比当前极小值大，说明已经找到了极小值
                    flag1 = true;
                    break;
                }
            }
            //求极大值
            value2 = value1;
            for(;index < prices.size(); index++){
                if(prices[index] >= value2){ //这里要包含等号
                    value2 = prices[index]; 
                    if(index == prices.size()-1) //右边界处理   
                        flag2 = true;   
                }
                else{
                    flag2 = true;
                    break;
                }
            }
            //保存极值
            if(flag1 && flag2) vec.push_back(pair<int,int>(value1,value2));
            else break;  //找不到一组极值，退出 
        }
        for(int i = 0; i < vec.size(); i++)
            profit = profit - vec[i].first + vec[i].second;
        return profit;      
    }
};  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

上面的求解过程只关注了极小值和极大值两个点，但其实利润是可以分解的，从极小值到极大值的过程中，每天都是正利润，例如求prices[4]-prices[1]，完全可以分解为(prices[4]-prices[3]) + (prices[3]-prices[2]) + (prices[2]-prices[1])，这样只需要关注当天相对于前一天的利润。按照分解利润的思想，不再需要求极值点，而只需要关注当前相对于前一天的利润，而且我们只需要关注正利润，这就是贪心所贪的地方。代码实现如下：

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

题目二：LeetCode 55. 跳跃游戏

因为这个题问的是能不能跳到最后一个位置，因此只需要做判断就可以了，不必关心具体的路径。每个位置给出了能跳的最大长度，将每个位置的最大长度转化成一个范围，最终判断这个范围能不能覆盖最后一个位置就可以了。

如上图所示，左图能覆盖终点，而右图不能覆盖终点。

但其实不必列出所有位置的覆盖范围，只需要每次移动取最大跳跃步数（得到最大的覆盖范围），每移动一个单位，就更新最大覆盖范围。如下图所示：

在代码实现上，i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。

而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。

如果cover大于等于了终点下标，直接return true就可以了。

代码实现如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        for(int i = 0; i <= cover; i++){
            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

题目三：LeetCode 45. 跳跃游戏II

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数再加一。
整体最优：一步尽可能多走，从而达到最小步数。

这里需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。如果移动下标达到了当前这一步的最大覆盖最远距离了，还没有到终点的话，那么就必须再走一步来增加覆盖范围，直到覆盖范围覆盖了终点。

这里有个特殊情况需要考虑，当移动下标达到了当前覆盖的最远距离下标时

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

class Solution {
public:
    int jump(vector<int>& nums) {
        int curDistance = 0, nextDistance = 0;
        int step = 0;
        for(int i = 0; i < nums.size(); i++){
            nextDistance = max(i+nums[i],nextDistance);
            if(i == curDistance){
                if(curDistance != nums.size()-1){
                    step++;
                    curDistance = nextDistance;
                    if(nextDistance >= nums.size()-1)   break;
                }
                else break;
            }
        }
        return step;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19