本文介绍: 本题目设计的还是比较巧妙的,把最终的利润分为每天利润解决了(贪心),每天利润就是前一天买进,后一天卖出,转化到代码上就是:p[i]-p[i-1],我们要取得最大利润,就需要最起码让每天利润不为负数,所以我们需要每天大于0的利润加起来就能得到最终的最大利润了。本题目还是比较有按难度的,首先说一下贪心思路:我们用每步最大覆盖范围来取得最少的步数。本题目之前在dp专题做过两个差不多的,本题目比较简单,直接说贪心思路了,取最大范围,在i点时,最大范围能否到达最后一个点可以判断了。

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

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

本题设计的还是比较巧妙的,把最终的利润分为每天的利润就解决了(贪心),每天的利润就是前一天买进,后一天卖出,转化到代码上就是:p[i]-p[i-1],我们要取得最大利润,就需要最起码让每天的利润不为负数,所以我们需要取每天大于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;
    }
};

Leetcode 55. 跳跃游戏

题目链接 55 跳跃游戏

本题目之前在dp专题做过两个差不多的,本题目比较简单,直接说贪心思路了,取最大范围,在i点时,最大范围能否到达最后一个点可以判断了。

下面直接上代码

class Solution {
public:
    bool canJump(vector<int&gt;&amp; nums) {
        int court = 0;
        if(nums.size() == 1){
            return true;
        }
        for(int i=0;i<=court;i++){//i 每次移动只能在 cover 的范围内移动,每移动一个元素cover 得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。
             court = max(court,i+nums[i]);
             if(court>=nums.size()-1){
                return true;
            }
        }
            return false;
    }
};

Leetcode 45. 跳跃游戏 II

题目链接 45 跳跃游戏 II

本题目还是比较有按难度的,首先说一下贪心思路:我们用每步最大的覆盖范围来取得最少的步数。如果移动下标达到了当前一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点。这时我们必须走的下一步必须是在第一步走的范围内点的能走的最大的覆盖范围这里代码表示的话就是:

 nextDistance = max(nums[i] + i, nextDistance)

当移动下标达到了当前覆盖的最远距离下标

下面上代码

class Solution {
public:
    int jump(vector<int>&amp; nums) {
        if(nums.size()==1){
            return 0;
        }
            int result;
            int curDistance = 0;
            int nextDistance = 0;
            for(int i=0;i<nums.size();i++){
                nextDistance = max(nums[i]+i,nextDistance);//在遍历最大覆盖范围时,收集下一步最大覆盖范围
                if(i==curDistance){
                    result++;//步数
                    curDistance = nextDistance;//更新最大范围
                    if(nextDistance>=nums.size()-1){//覆盖范围到终点就结束
                        break;
                    }
                }
            }
          return result;  
    }
};

晚上学六级 end

原文地址:https://blog.csdn.net/weixin_72635630/article/details/134613734

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任

如若转载,请注明出处:http://www.7code.cn/show_17643.html

如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱suwngjj01@126.com进行投诉反馈,一经查实,立即删除

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注