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

能卖就卖

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

55. 跳跃游戏

不需要考虑步数，只用更新能到的最远的下标。

class Solution {
public:
    // 在能跳到的最远处选一个 能到最远的(下标+当前的权值)
    bool canJump(vector<int>& nums) {
        int idx = 0;
        int n = nums.size();
        for (int i = 0; i <= idx; i ++)
        {
            idx = max(idx, i + nums[i]);
            if (idx >= n - 1) return true;
        }
        return false;
    }
};

45. 跳跃游戏 II

和步数有关，每次跳到能到的最远处。

class Solution {
public:
    // 当前的最远距离 + 下一步的最远距离
    int jump(vector<int>& nums) {
        int res = 0, curidx = 0, nextidx = 0;
        int n = nums.size();
        if (n == 1) return 0;
        res = 1, curidx = nums[0];
        for (int i = 0; i < n; i ++)
        {
            nextidx = max(nextidx, i + nums[i]);
            if (i == curidx)
            {
                if (curidx < n - 1)
                {
                    res ++;
                    curidx = nextidx;
                    if (curidx >= n) break;
                }
                else
                {
                    break; // 直接结束了，不需要再跳
                }
            }
        }
        return res;
    }
};