贪心算法:买卖股票的最佳时机II 跳跃游戏 跳跃游戏II
122.买卖股票的最佳时机II
- 思路:
- 想要获得利润,至少要以两天为一个交易单元,因为两天才会有股价差。
- 因此可以将最终利润进行分解,如prices[3] - prices[0] = (prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0]),也就是把利润分解为每天为单位的维度,那么就可以很清晰地看出,哪些天有收益,哪些天是亏损,而要获得最大利润,只需要收集所有正利润。

- 局部最优:收集每天的正利润,全局最优:求得最大利润。
- 时间复杂度:O(n)
- 空间复杂度:O(1)
class Solution {
public:int maxProfit(vector<int>& prices) {int res = 0;for(int i = 1; i < prices.size(); i++) {if(prices[i] - prices[i - 1] > 0) {//只统计正利润res += prices[i] - prices[i - 1];}// res += max(prices[i] - prices[i - 1], 0);//也可以这样写}return res;}
};
55. 跳跃游戏
- 思路:
- 本题关键在于可跳的覆盖范围,即每次取最大的跳跃步数,只要终点在可以跳到的覆盖范围之内,那么就一定能跳到终点。
- 做法:
- 每次移动取最大跳跃步数(得到最大的覆盖范围),每移动一个单位,就更新最大覆盖范围。i只能在覆盖范围cover内遍历,每移动一个元素,cover 得到该元素数值(新的覆盖范围)的补充,让 i 继续移动下去。而cover更新时,取cover和新的覆盖范围的较大者。如果 cover 大于等于了终点下标,说明可以到达最后一个位置,直接 return true 。
- 贪心算法局部最优解:每次取最大跳跃步数(取最大覆盖范围)。
- 整体最优解:最后得到整体最大覆盖范围,看是否能到终点。
- 时间复杂度: O(n)
- 空间复杂度: O(1)
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;}
}; 参考链接
代码随想录:最买卖股票的佳时机II 跳跃游戏
相关文章:
贪心算法:买卖股票的最佳时机II 跳跃游戏 跳跃游戏II
122.买卖股票的最佳时机II 思路: 想要获得利润,至少要以两天为一个交易单元,因为两天才会有股价差。因此可以将最终利润进行分解,如prices[3] - prices[0] (prices[3] - prices[2]) (prices[2] - prices[1]) (prices[1] - pr…...
音频DAC,ADC,CODEC的选型分析,高性能立体声
想要让模拟信号和数字信号顺利“交往”,就需要一座像“鹊桥”一样的中介,将两种不同的语言转变成统一的语言,消除无语言障碍。这座鹊桥就是转换器芯片,也就是ADC芯片。ADC芯片的全称是Analog-to-Digital Converter, 即模拟数字转换…...
python 连接SQL server 请用pymssql连接,千万别用pyodbc
pymssql官方介绍文档 python 使用 pymssql连接 SQL server 代码示例: 安装pymssql包: pip install pymssql代码: import pymssqldef conn_sqlserver_demo():# 连接字符串示例(根据您的配置进行修改)conn Nonetry:co…...
IntelliJ IDEA 自带HTTP Client接口插件上传文件示例
如何使用IntelliJ IDEA自带的HTTP Client接口插件进行文件上传的示例。在这个示例中,我们将关注Controller代码、HTTP请求文件(xxx.http),以及文件的上传和处理。 Controller代码 首先,让我们看一下处理文件上传的Co…...
C++中的接口有什么用
2023年12月13日,周三上午 今天上午在适配器模式,我发现如果想真正理解适配器模式,就必须学会使用C中的接口,就必须明白为什么要在C中使用接口,所以重新学习了一下C中的接口 目录 C中的接口有什么用用代码说明“实现多…...
el-table合并相同数据的单元格
相同的数据合并单元格 <el-table :data"userList" :span-method"objectSpanMethod" border><el-table-column type"selection" width"50" align"center" /><el-table-column label"用户名称" a…...
Verilog Systemverilog define宏定义
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 文章前情预告一、define是个啥?二、为什么要使用define三、怎么使用define四、define的横向拓展五、define思想在生活中的体现!六、结论七、参考资料八、…...
51单片机应用从零开始(十一)·数组函数、指针函数
51单片机应用从零开始(九)数组-CSDN博客 51单片机应用从零开始(十)指针-CSDN博客 目录 1. 用数组作函数参数控制流水花样 2. 用指针作函数参数控制 P0 口 8 位 LED 流水点亮 1. 用数组作函数参数控制流水花样 要在51单片机中…...
【PostgreSQL】从零开始:(八)PostgreSQL-数据库PSQL元命令
元命令 postgres# \? General\bind [PARAM]... set query parameters\copyright show PostgreSQL usage and distribution terms\crosstabview [COLUMNS] execute query and display result in crosstab\errverbose show most recent error…...
02 使用Vite创建Vue3项目
概述 A Vue project is structured similarly to a lot of modern node-based apps and contains the following: A package.json fileA node_modules folder in the root of your projectVarious other configuration files are usually contained at the root level, such …...
Shell三剑客:sed(简介)
一、前言 Stream EDitor:流编辑 sed 是一种在线的、非交互式的编辑器,它一次处理一行内容。处理时,把当前处理的行存储在临时缓冲区中,称为“模式空间”(pattern space),接着用sed命令处理缓冲区中的内容,处理完成后&…...
tp连接数据库
ThinkPHP内置了抽象数据库访问层,把不同的数据库操作封装起来,我们只需要使用公共的Db类进行操作,而无需针对不同的数据库写不同的代码和底层实现,Db类会自动调用相应的数据库驱动来处理。采用PDO方式,目前包含了Mysql…...
jmeter,断言:响应断言、Json断言
一、响应断言 接口A请求正常返回值如下: {"status": 10013, "message": "user sign timeout"} 在该接口下创建【响应断言】元件,配置如下: 若断言成功,则查看结果树的接口显示绿色,若…...
dockerfite创建镜像---INMP+wordpress
搭建dockerfile---lnmp 在192.168.10.201 使用 Docker 构建 LNMP 环境并运行 Wordpress 网站平台 [rootdocker1 opt]# mkdir nginx mysql php [rootdocker1 opt]# ls #分别拖入四个包: nginx-1.22.0.tar.gz mysql-boost-5.7.20.tar.gz php-7.1.10.tar.bz2 wor…...
服务器数据恢复—raid5热备盘未激活崩溃导致上层oracle数据丢失的数据恢复案例
服务器数据恢复环境: 某品牌X系列服务器,4块SAS硬盘组建了一组RAID5阵列,还有1块磁盘作为热备盘使用。服务器上层安装的linux操作系统,操作系统上部署了一个基于oracle数据库的OA(oracle已经不再为该OA系统提供后续服务…...
生产派工自动化:MES系统的关键作用
随着制造业的数字化转型和智能化发展,生产派工自动化成为了提高生产效率、降低成本,并实现优质产品生产的关键要素之一。制造执行系统(MES)在派工自动化中发挥着重要作用,通过实时数据采集和智能调度,优化生…...
netty-daxin-2(netty常用事件讲解)
文章目录 netty常用事件讲解ChannelHandler接口ChannelHandler适配器类ChannelInboundHandler 子接口Channel 的状态调用时机ChannelHandler 生命周期示例NettServer&CustomizeInboundHandlerNettyClient测试分析 ChannelInboundHandlerAdapter适配器类SimpleChannelInboun…...
使用playbook部署k8s集群
1.部署ansible集群 使用python脚本一个简单的搭建ansible集群-CSDN博客 2.ansible命令搭建k8s: 1.主机规划: 节点IP地址操作系统配置server192.168.174.150centos7.92G2核client1192.168.174.151centos7.92G2核client2192.168.174.152centos7.92G2 …...
Python基础入门第四节,第五节课笔记
第四节 第一个条件语句 if 条件: 条件成立执行的代码1 条件成立执行的代码2 ...... else: 条件不成立执行的代码1 条件不成立执行的代码2 …… 代码如下: 身高 float(input("请输入您的身高(米):")) if 身高 >1.3:print(f您的身高是{身高},已经超过1.3米,您需…...
基于Java SSM框架实现智能停车场系统项目【项目源码+论文说明】
基于java的SSM框架实现智能停车场系统演示 摘要 本论文主要论述了如何使用JAVA语言开发一个智能停车场管理系统,本系统将严格按照软件开发流程进行各个阶段的工作,采用B/S架构,面向对象编程思想进行项目开发。在引言中,作者将论述…...
深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
力扣热题100 k个一组反转链表题解
题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...
Spring Security 认证流程——补充
一、认证流程概述 Spring Security 的认证流程基于 过滤器链(Filter Chain),核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤: 用户提交登录请求拦…...
SQL Server 触发器调用存储过程实现发送 HTTP 请求
文章目录 需求分析解决第 1 步:前置条件,启用 OLE 自动化方式 1:使用 SQL 实现启用 OLE 自动化方式 2:Sql Server 2005启动OLE自动化方式 3:Sql Server 2008启动OLE自动化第 2 步:创建存储过程第 3 步:创建触发器扩展 - 如何调试?第 1 步:登录 SQL Server 2008第 2 步…...
aardio 自动识别验证码输入
技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”,于是尝试整合图像识别与网页自动化技术,完成了这套模拟登录流程。核心思路是:截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...
PH热榜 | 2025-06-08
1. Thiings 标语:一套超过1900个免费AI生成的3D图标集合 介绍:Thiings是一个不断扩展的免费AI生成3D图标库,目前已有超过1900个图标。你可以按照主题浏览,生成自己的图标,或者下载整个图标集。所有图标都可以在个人或…...
2.2.2 ASPICE的需求分析
ASPICE的需求分析是汽车软件开发过程中至关重要的一环,它涉及到对需求进行详细分析、验证和确认,以确保软件产品能够满足客户和用户的需求。在ASPICE中,需求分析的关键步骤包括: 需求细化:将从需求收集阶段获得的高层需…...
