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

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

题目链接：122.买卖股票的最佳时机II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

文章讲解/视频讲解：https://programmercarl.com/0122.%E4%B9%B0%E5%8D%96%E8%82%A1%E7%A5%A8%E7%9A%84%E6%9C%80%E4%BD%B3%E6%97%B6%E6%9C%BAII.html

思路

局部最优策略：

每一次找到股票走势图的谷底，买入，然后从谷底出发，从后找到最近的一处谷顶，卖出，之后同理。

如何找到谷底和谷顶：当左右值（如有）都大于等于当前值时，当前便处于谷底；当左右值（如有）都小于等于当前值时，当前便处于谷顶。

我的代码写得好长。。回头再看看代码少的解法吧。

C++实现

class Solution {
public:
    bool isBottomOrTop(const vector<int>& prices, bool bottom, int index){
        if(index == 0){
            return bottom ? prices[index + 1] >= prices[index] : prices[index + 1] <= prices[index];
        }
        else if(index == prices.size() - 1){
            return bottom ? prices[index - 1] >= prices[index] : prices[index - 1] <= prices[index];
        }
        else{
            return bottom ? (prices[index - 1] >= prices[index] && prices[index + 1] >= prices[index]) : 
                            (prices[index - 1] <= prices[index] && prices[index + 1] <= prices[index]);
        }
    }

    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1) return 0;

        int profitSum = 0;
        int index = 0;

        while(index < prices.size()){
            if(isBottomOrTop(prices, true, index)){
                // 如果找到了谷底，下一步就是寻找谷顶
                int prePrice = prices[index];
                index++;
                while(index < prices.size()){
                    if(isBottomOrTop(prices, false, index)){
                        int curPrice = prices[index];
                        profitSum += (curPrice - prePrice);
                        break;
                    }
                    else{
                        index++;
                    }
                }
            }
            else{
                index++;
            }
        }
        return profitSum;
    }
};

55. 跳跃游戏

题目链接：55. 跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

文章讲解/视频讲解：https://programmercarl.com/0055.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8F.html

思路

记录一个accessible数组，代表当前下标可到达最后一个下标。从后往前遍历，对于当前下标i，记step = nums[i]，如果在[i+1,i+step]范围内有下标可达，则当前下标可达。

另外一个更简便的思路：

从后往前遍历，每一步记录当前能够最终到达最后一个下标的最后一个值lastAccess。如果从当前下标i开始跳，能够超过lastAccess，则说明该下标可到达最后一个下标，

更新lastAccess为i。

C++实现

// 第一种思路
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int n = nums.size();
        vector<bool> memo(n, false);
        memo[n - 1] = true;

        for(int i = n - 2;i>=0;i--){
            int step = nums[i];
            for(int j = 1;j<=step;j++){
                if(memo[i + j]){
                    memo[i] = true;
                    break;
                }
            }
        }

        return memo[0];
    }
};

// 另一种思路
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int lastAccess = nums.size() - 1;
        for(int i = nums.size() - 2;i>=0;i--){
            if(nums[i] + i >= lastAccess){
                lastAccess = i;
            }
        }
        return lastAccess == 0;
    }
};

45.跳跃游戏II

题目链接：45.跳跃游戏II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

文章讲解/视频讲解：https://programmercarl.com/0045.%E8%B7%B3%E8%B7%83%E6%B8%B8%E6%88%8FII.html

思路

记录一个数组stepsToLast，每一个下标记录了当前位置到达最后一个下标的最小跳跃次数。

然后从后往前遍历，对于当前下标i，记step = nums[i]，在[i+1,i+step]范围内寻找stepsToLast最小的值，取该值加1，作为当前下标i到达最后一个下标的最小跳跃次数。

C++实现

class Solution {
public:
    int jump(vector<int>& nums) {
        vector<int> stepsToLast(nums.size(), 1001);
        stepsToLast[nums.size() - 1] = 0;
        for(int i = nums.size() - 2;i>=0;i--){
            int step = nums[i];
            int minskipidx = -1;
            for(int j = i + 1;j<nums.size() && j <= i + step;j++){
                if(minskipidx == -1 || stepsToLast[j] < stepsToLast[minskipidx]){
                    minskipidx = j;
                }
            }
            if(minskipidx != -1) stepsToLast[i] = stepsToLast[minskipidx] + 1;
        }
        return stepsToLast[0];
    }
};