算法学习 | day28/60 买卖股票的最佳时机/跳跃游戏/跳跃游戏II

一、题目打卡

        1.1 买卖股票的最佳时机

        题目链接：. - 力扣（LeetCode）        

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 1) return 0;
        // int result = 0;
        // int prediff = 0;
        // int curdiff = 0;
        // int tmp = 0; // 存储低谷 i 的位置
        // for(int i = 0, j = 1; j < prices.size();i++,j++){
        //     curdiff = prices[j] - prices[i];
        //     if(curdiff > 0 && prediff <=0){
        //         tmp = i;
        //     }
        //     else if(curdiff <= 0 && prediff > 0){
        //         result += prices[i] - prices[tmp];
        //     }
        //     else if(curdiff)
        //     prediff = curdiff;
        // }
        // return result;
        int result = 0;
        for(int i = 0; i < prices.size() -1 ; i++){
            if(prices[i+1] - prices[i] >=0) result+=prices[i+1]-prices[i];
        }
        return result;
    }
};

        好好好，我专门考虑记录波峰波谷，结果案例过不去，然后突然醒悟，如果是贪心全部加上正区间不就可以了，然后发现确实是，我只能说，确实挺贪心的，这样等于是买了，只要是正的第二天就卖。

        1.2 跳跃游戏

        题目链接：. - 力扣（LeetCode）

class Solution {
public:
    bool canJump(vector<int>& nums) {
        if(nums.size() == 1) return true;
        int cover = nums[0];
        for(int i = 0; i <= cover;i++){ // 这里要带等于，否则123会被误判
            // if(nums[i] + 1 >= nums.size() - 1) return true;
            // cover = max(nums[i] + nums[nums[i]],cover);
            // if(cover >= nums.size() - 1) return true;
            cover = max(i + nums[i], cover);
            if(cover >= nums.size() - 1) return true;
        }
        return false;
    }
};

        答案有一种解法和这个思路是一样的，这样不断更新迭代范围的方法第一次尝试，踩坑的点有两个，一个是cover的那里，必须要带等号，第二个是更新 cover 的过程，我之前写错了，那样逻辑也不对，而且会越界。

        1.3 跳跃游戏II（答案思路）

        题目链接：. - 力扣（LeetCode）

class Solution {
public:
    int jump(vector<int>& nums) {
        int res = 0, curCover = 0, nextCover = 0;
        for(int i = 0 ; i < nums.size() - 1; i++){
            nextCover = max(nums[i] + i,nextCover);
            if(i == curCover){
                res++;
                curCover = nextCover;
            }
        }
        return res;
    }
};

        感觉自己做完全想不到这个写法，思考的大方向虽然没问题，但是细节想不清楚，答案我感觉我理解的也不是很透彻，但是这种题目也没有泛化性，所以不强求了，先标记一下留在这里吧。