JLUVicent

122买卖股票最佳时机II&45跳跃游戏II&55跳跃游戏

 
  • 2023年 03月18日
  • 0 阅读

day32

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

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

解题思路：参考 视频

直接判断相邻的是增长还是减弱，第一遍直接AC了

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        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;
    }
};

55.跳跃游戏

题目链接：55. 跳跃游戏

解题思路：参考 视频

从第一个数组开始，找到数的覆盖范围，然后遍历覆盖范围中的每个数，找到最大的覆盖范围，不断去循环遍历，判断条件就是cover是否大于等于数组的最后一个元素的小标

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        if( nums.size() == 1) return true;

        for( int i = 0; i <= cover ; i++){
            cover = max( i+nums[i], cover);
            if( cover >= nums.size()-1) return true;
        }
        return false;
    }
};

45.跳跃游戏II

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

解题思路：参考 视频

局部最优：当可移动距离尽可能多，没到终点时候，步数加1

整体最优：一步尽可能多走，达到最小步数

所以真正解题的时候，要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最小步数！

需要统计两个覆盖范围：当前的最大覆盖和下一步的最大覆盖

45.跳跃游戏II

  • 如果当前覆盖最远距离下标不是是集合终点，步数就加一，还需要继续走。
  • 如果当前覆盖最远距离下标就是是集合终点，步数不用加一，因为不能再往后走了。
class Solution {
public:
    int jump(vector<int>& nums) {
        int cur = 0;
        int next = 0;
        int result = 0;
        for( int i = 0; i < nums.size(); i++){
            next = max( i+nums[i],next);    //获得最大覆盖范围
            if( i == cur ){
                if( cur < nums.size()-1){
                    result++;
                    cur = next;
                	if( next >= nums.size()-1) break;
                }
                else break;
            }
        }
        return result;
    }
};
搜索