贪心算法:买卖股票的最佳时机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架构,面向对象编程思想进行项目开发。在引言中,作者将论述…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
React Native 开发环境搭建(全平台详解)
React Native 开发环境搭建(全平台详解) 在开始使用 React Native 开发移动应用之前,正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南,涵盖 macOS 和 Windows 平台的配置步骤,如何在 Android 和 iOS…...
DAY 47
三、通道注意力 3.1 通道注意力的定义 # 新增:通道注意力模块(SE模块) class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...
el-switch文字内置
el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Map相关知识
数据结构 二叉树 二叉树,顾名思义,每个节点最多有两个“叉”,也就是两个子节点,分别是左子 节点和右子节点。不过,二叉树并不要求每个节点都有两个子节点,有的节点只 有左子节点,有的节点只有…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程
STM32F1 本教程使用零知标准板(STM32F103RBT6)通过I2C驱动ICM20948九轴传感器,实现姿态解算,并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化,适合嵌入式及物联网开发者。在基础驱动上新增…...
高考志愿填报管理系统---开发介绍
高考志愿填报管理系统是一款专为教育机构、学校和教师设计的学生信息管理和志愿填报辅助平台。系统基于Django框架开发,采用现代化的Web技术,为教育工作者提供高效、安全、便捷的学生管理解决方案。 ## 📋 系统概述 ### 🎯 系统定…...
