[量化投资接口] 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

Day312买卖股票的最佳时机II,5跳跃游戏,4跳跃游戏II

买卖股票的最佳时机II

整体思路

思路，局部贪心：每次未来有收益便执行买入卖出操作。无收益就不买入。因此初步写成代码为：

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

继续抽象，那么可以看成，将每两天之间的股票价格作差，如果今天和昨天股票的差值大于0，即存在收益。如果差值小于0，则置为0，意为不进行购买，简化代码如下：

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

跳跃游戏

解题思路

跳跃游戏，重点在于对覆盖范围的计算，当前可以前进的步数中，查询前进后有新的最大覆盖范围的步数。并进行前进，如果发现前进最大步数后无法继续前进，则说明该数组无法完成跳跃游戏。

代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==1) return true;
        int jumpLen = 0,jumpIndex = 0;
        for(int i=0;i<nums.size()-1;){
            if((i+nums[i])>=(nums.size()-1)) return true;
            jumpLen = 0,jumpIndex = 0;
            for(int j=0;j<=nums[i];j++){
                if(j+nums[i+j]>jumpLen){
                    jumpLen = j + nums[i+j];
                    jumpIndex = j;
                }
            }
            if(jumpIndex==0) return false;
            i+=jumpIndex;
        }
        return false;
    }
};

这是比较复杂的方法，因为相当于求得了最少次数跳跃成功。如果不考虑复杂度，可以对每次新的覆盖范围都进行一次遍历。代码如下：

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==1) return true;
        int jumpLen = 0;
        for(int j=0;j<=jumpLen;j++){
            jumpLen = max(j+nums[j],jumpLen);
            if(jumpLen>=nums.size()-1) return true;
        }        
        return false;
    }
};

跳跃游戏II

解题思路

跳跃游戏2需要求得最短步数，因此可以直接用i中最长部署范围的思想。只不过加入额外的计数器来进行跳跃的计算。

代码如下：

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1) return 0;
        int jumpNum = 0;
        for(int i=0;i<nums.size()-1;){
            if((i+nums[i])>=(nums.size()-1)) return jumpNum+1;
            int jumpLen = 0,jumpIndex = 0;
            for(int j=0;j<=nums[i];j++){
                if(j+nums[i+j]>jumpLen){
                    jumpLen = j + nums[i+j];
                    jumpIndex = j;
                }
            }
            i+=jumpIndex;
            jumpNum++;
        }
        return jumpNum;
    }
};

也可以进行进一步的简化，已知这次要跳跃的最大覆盖范围了，那么在下次迭代，只要下标没有到达最大覆盖范围所指向的位置，均可以直接跳过。直到到达当前最大覆盖位置后，对覆盖位置进行更新，并且视作跳跃次数+往复直到到达n-1位置。

值得注意的是，在下一次覆盖范围超过n-1位置时，理论上应该再跳一次才是正确答案，但这里没有加是因为curdis的初始值为0，所以在第一次更新的时候多出一次额外的+1,。代码如下：

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1) return 0;
        int curDistance = 0;    // 当前覆盖最远距离下标
        int ans = 0;            // 记录走的最大步数
        int nextDistance = 0;   // 下一步覆盖最远距离下标
        for (int i = 0; i < nums.size(); i++) {
            nextDistance = max(nums[i] + i, nextDistance);  // 更新下一步覆盖最远距离下标
            if (i == curDistance) {                         // 遇到当前覆盖最远距离下标
                ans++;                                  // 需要走下一步
                curDistance = nextDistance;             // 更新当前覆盖最远距离下标（相当于加油了）
                if (nextDistance >= nums.size() - 1) break;  // 当前覆盖最远距到达集合终点，不用做ans++操作了，直接结束
            }
        }
        return ans;
    }
};

文章为作者独立观点，不代表股票自动交易程序化数据接口观点

[量化投资接口] 122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II

[量化投资接口]JD 某工业平台详情API接口PHP接口数据API接口

[量化投资接口]通义听悟上线强大的视频会议和学习直播分析能力人工智能如

[量化投资接口]深入研究Python在股票回撤分析中的应用

[量化投资接口]DDLDMLDQLDCL快速入门

[量化投资接口]JD 某工业平台详情API接口PHP接口数据API接口

[量化投资接口]通义听悟上线 强大的视频会议和学习直播分析能力 人工智能如

[量化投资接口]深入研究Python在股票回撤分析中的应用

[量化投资接口]DDLDMLDQLDCL快速入门

[量化投资接口]通义听悟上线强大的视频会议和学习直播分析能力人工智能如