12.15 log 122.买卖股票的最佳时机 II,55. 跳跃游戏

发布时间:2024年01月05日

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

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

这道题贪心贪的时每一段即买即涨,求数组的每一段单调递增区间值的累加。

55. 跳跃游戏

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

count和cover都是代表数组下标,count代表当前点所能跳到的数组下标 , cover则是当前所走范围内的所能走的最远距离,走一步就要判断一步,cover是不是所能到的最远数组下标,如果count比cover大,cover就要替换为count,所以跳跃游戏贪的就是,在有限的步数之内永远选跨度最大的那一步,如果当前count所能到达的数组下标已经超过最后一个元素的下标则返回true。

45.跳跃游戏 II?

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

跳跃游戏I是判断能否到达终点,跳跃游戏II是给定一定能到达终点,求最小步数,跳跃游戏I是每走一步就要判断覆盖范围,求最大覆盖范围是否包含了终点,跳跃游戏II是在当前覆盖范围里走最大覆盖范围,每变更一次覆盖范围,count++,当i走到当前覆盖范围终点时,覆盖范围变更,如果下一个覆盖范围大于等于终点,break

文章来源:https://blog.csdn.net/weixin_58515995/article/details/135004527
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。