Day32——122.买卖股票的最佳时机II 55. 跳跃游戏 45.跳跃游戏II +第二天复习

赶上进度，冲冲冲

目录

前言

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

二、跳跃游戏

解题思路：

三、跳跃游戏||

总结

---

---

前言

生命能与世俗相契合，才能不朽，生命的整体是象征的，因为他是有意义的.

                                                                                                                ——《日瓦戈医生》

---

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

力扣

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

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

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

解题思路：

我一开始是这么想的，我怎么才能让它知道，什么时候该买什么时候该卖呢，我知道全局来算肯定简单，它不知道，我要怎么告诉它，太难了！看答案hhh

but，我们不需要告诉它，我们知道就行，只要我们拆开，把没两天的差值（利润）都算出来，只拿正收入不就行了嘛。因为你在那里同一天卖了在买，到下一天卖，其实就等于是分散的。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        
        int sum=0;
        for(int i=0;isize()-1;i++)
        {
            if(prices[i+1]-prices[i]>0)        //只要正收入
            {
                sum+=prices[i+1]-prices[i];
            }
        }
        return sum;
    }
};

二、跳跃游戏

力扣

解题思路：

我们用覆盖范围来做，只要覆盖到了终点就行了。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size()==1)
        {
            return true;
        }
        int disance=0;
        for(int i=0;i<=disance;i++)    //重点，我们只在已经覆盖的区域里遍历，因为我们跳不出去
        {
            disance=max(disance,nums[i]+i);    //取最大的
            if(disance>=nums.size()-1)        
            {
                return true;
            }
        }
        return false;
    }
};

---

三、跳跃游戏||

和上一题非常像，也是用范围覆盖来求，只不过因为要计算步骤，所以复杂一点。

class Solution {
public:
    int jump(vector<int>& nums) {
        if(nums.size()==1)
        {
            return 0;
        }
 
        int curindance=0;        //上一个距离
        int nextindance=0;        //下一个距离
        int ans=0;            //步数
 
        for(int i=0;isize();i++)
        {
            nextindance=max(nextindance,i+nums[i]);        //更新最大覆盖范围
            if(i==curindance)          //如果已经走到尽头了，在覆盖范围内选下一个覆盖范围
            {
                if(curindance!=nums.size()-1)        //还没到终点
                {
                    curindance=nextindance;        //跳一步，扩大范围
                    ans++;
                    if(nextindance>=nums.size()-1)    //找到了
                    {
                        break;
                    }
                }
                else
                {
                    break;
                }
            }
        }
        return ans;
    }
};

第二天复习：

1、先排序，两边就是最大的，然后双指针，平方，取最大的，最后再反转

2、滑动窗口，注意双指针移动

3、螺旋数组，感觉难

---

总结

复习，迷茫了。