首页 > 编程语言 >代码随想录算法训练营第32天| 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.跳跃游戏 II

代码随想录算法训练营第32天| 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.跳跃游戏 II

时间:2024-03-31 16:30:24浏览次数:31  
标签:游戏 nums int cover II prices 跳跃 覆盖范围

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

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

题目描述:给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

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

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

解题思想:

主要思想就是最终利润是可以分解到,

假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。

相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。

此时就是把利润分解为每天为单位的维度,而不是从 0 天到第 3 天整体去考虑!

那么根据 prices 可以得到每天的利润序列:(prices[i] - prices[i - 1])…(prices[1] - prices[0])。

其实我们需要收集每天的正利润就可以,收集正利润的区间,就是股票买卖的区间,而我们只需要关注最终利润,不需要记录区间局部最优:收集每天的正利润,全局最优:求得最大利润

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sum = 0;
        for (int i = 1; i < prices.size(); i++) {
            sum += max(prices[i] - prices[i - 1], 0);
        }
        return sum;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

55. 跳跃游戏

题目链接:跳跃游戏

题目描述:给你一个非负整数数组 nums ,你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标,如果可以,返回 true ;否则,返回 false 。

解题思想:

本题可以转化为跳跃覆盖范围究竟可不可以覆盖到终点!

每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。

贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围),整体最优解:最后得到整体最大覆盖范围,看是否能到终点

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = 0;
        for (int i = 0; i <= cover; i++) {
            cover = max(cover, i + nums[i]);
            if (cover >= nums.size() - 1)
                return true;
        }
        return false;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

45.跳跃游戏 II

题目链接:跳跃游戏 II

题目描述:给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说,如果你在 nums[i] 处,你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]

解题思想:

要从覆盖范围出发,不管怎么跳,覆盖范围内一定是可以跳到的,以最小的步数增加覆盖范围,覆盖范围一旦覆盖了终点,得到的就是最少步数!

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

如果移动下标达到了当前这一步的最大覆盖最远距离了,还没有到终点的话,那么就必须再走一步来增加覆盖范围,直到覆盖范围覆盖了终点。

class Solution {
public:
    int jump(vector<int>& nums) {
        if (nums.size() == 1)
            return 0;
        int result = 0;
        int cur_cover = 0;
        int next_cover = 0;
        for (int i = 0; i < nums.size(); i++) {
            next_cover = max(next_cover, i + nums[i]);
            if (i == cur_cover) {
                result++;
                cur_cover = next_cover;
                if (next_cover >= nums.size() - 1)
                    break;
            }
        }
        return result;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

标签:游戏,nums,int,cover,II,prices,跳跃,覆盖范围
From: https://blog.csdn.net/Intro_Nitro/article/details/137081398

相关文章

  • java数据结构与算法刷题-----LeetCode95. 不同的二叉搜索树 II
    java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846文章目录分治回溯+记忆化搜索分治回溯+记忆化搜索卡特兰数,例如对于n个进栈元素,有多少种出栈顺序,......
  • Numerical Results of iITCGP
    NumericalResultsofTest1       NumericalResultsofTest2 ......
  • 使用C语言在VS 环境下基本实现贪吃蛇游戏
    使用C语言在VS环境下基本实现贪吃蛇游戏一丶实现前的准备工作1.设置vs运行环境为window控制台而非window终端1.正确的运行环境页面2.设置正确的运行环境2.了解句柄(下面代码能看明白会照葫芦画瓢用就行)3.利用system函数丶cmd命令设置window控制台窗口的尺寸4.了......
  • C语言中char字符型数据的存取形式:ASCII码之间的转换
    unsignedcharchannelNum=49;则编译器会将ASCII码49存入变量channelNum,实际channelNum表示字符1,所以下次如果以%c形式打印出来,则输出1。e.g:查看代码unsignedcharchannelNum=49;#include"bsp_seg.h"#include"bsp_Init.h"//------------------------------------//将s......
  • 基于SpringBoot的“游戏分享网站”的设计与实现(源码+数据库+文档+PPT)
    基于SpringBoot的“游戏分享网站”的设计与实现(源码+数据库+文档+PPT)开发语言:Java数据库:MySQL技术:SpringBoot工具:IDEA/Ecilpse、Navicat、Maven系统展示系统总体结构图网站首页界面图用户注册界面图游戏文章界面图交流论坛界面图个人中心界面图后......
  • 游戏开发:生产可用的登录验证流程(C/S模式)
    如何设计一个生产可用的登录验证流程(C/S模式)平台SDK(SoftwareDevelopmentKit)软件中央数据后台(CenterServer)软件服务端(Server)软件客户端(Client)渠道平台登录验证(channelloginverify)软件开发期需要依据平台SDK规范接入平台的账号登录验证流程(比如AppleStore),发起登录时首......
  • Acwing 1318. 取石子游戏(博弈论)
    https://www.acwing.com/problem/content/1320/输入样例:233输出样例:1#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;typedefpair<int,int>PII;constLLMAXN=1e18,MINN=-MAXN,INF=0x3f3f3f3f;constLLN=100200,M=2020;intmain()......
  • PTA L2-040 哲哲打游戏
    哲哲是一位硬核游戏玩家。最近一款名叫《达诺达诺》的新游戏刚刚上市,哲哲自然要快速攻略游戏,守护硬核游戏玩家的一切!为简化模型,我们不妨假设游戏有 N 个剧情点,通过游戏里不同的操作或选择可以从某个剧情点去往另外一个剧情点。此外,游戏还设置了一些存档,在某个剧情点可以将玩......
  • 数字游戏(蓝桥杯历届真题)
    ##题目描述栋栋正在和同学们玩一个数字游戏。游戏的规则是这样的:栋栋和同学们一共n个人围坐在一圈。栋栋首先说出数字1。接下来,坐在栋栋左手边的同学要说下一个数字2。再下面的一个同学要从上一个同学说的数字往下数两个数说出来,也就是说4。下一个同学要往下数三个数,说7。依......
  • Yii2-助手类(ArrayHelper)
    Yii2-助手类(ArrayHelper)数组助手类ArrayHelperYii数组助手类提供了额外的静态方法,让你更高效的处理数组。模型转数组$model=Country::findOne(['code'=>'BR']);VarDumper::dump(ArrayHelper::toArray($model));//['code'=>'BR''name'=&g......