【代码随想录】day32

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

一、122买卖股票的最佳时机II

方法1:计算斜率大于0的线段的diffY

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        int buyPrice = prices.front();
        for (int i = 1; i < prices.size(); i ++) {
            if (prices[i] <= buyPrice) {
                buyPrice = prices[i];
                continue;
            }
            if (i + 1 < prices.size() && prices[i+1] > prices[i]) {
                continue;
            }
            res += prices[i] - buyPrice;
            if (i + 1 < prices.size()) buyPrice = prices[i+1];
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

方法2:套摆动序列模版

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        if (prices.size() < 2) return res;
        //找拐点，记录上升段
        int preDiff = 0;
        int curDiff, buyPrice;
        for (int i = 1; i < prices.size(); i ++) {
            curDiff = prices[i] - prices[i-1];
            if (preDiff <= 0 && curDiff > 0) {
                buyPrice = prices[i-1];
                while (i < prices.size() && prices[i] > prices[i-1]) {
                    i ++;
                }
                res += prices[i-1] - buyPrice;
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法3:把总收益折算成每日收益，累加正利润

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

二、55跳跃游戏

思路：找最大覆盖范围

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

三、45跳跃游戏II

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0;
        int cover = 0;
        int maxCover = 0;
        for (int i = 0; i <= cover && i < nums.size(); i ++) {
            if (i > maxCover) {
                res ++;
                maxCover = cover;
            }
            cover = max(cover, i + nums[i]);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

---