1、买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。返回 你能获得的 最大 利润 。

我的思路：首先画出图来，然后大致看了一下发现多个小区间的利润加起来会超过大区间的利润。举了几个例子都是这样。于是写出了代码运行正确。如下图。

代码随想录

1
2
3
4
5
6
7
8
9
10
11
12
//我的代码
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for(int i = 1;i<prices.size();i++){
            int diff = prices[i]-prices[i-1];
            sum = diff>0?(sum+diff):sum;
        }
        return sum;
    }
};

2、55跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

我的思路：没做出来。

代码随想录：这个问题转化为跳跃覆盖范围究竟可不可以覆盖到终点！维护一个覆盖范围，遍历覆盖范围内的元素，当覆盖范围包含目标元素时返回。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int backidx = 0;
        for(int i = 0;i<nums.size() && i<=backidx;i++){
            if(backidx>=nums.size()-1)return true;
            backidx = (i+nums[i])>backidx?(i+nums[i]):backidx; //更新覆盖范围。覆盖范围内的元素一定可达
        }
        return false;
    }
};

3、45跳跃游戏II