当前位置: 首页 > news >正文

贪心算法:买卖股票的最佳时机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 思路&#xff1a; 想要获得利润&#xff0c;至少要以两天为一个交易单元&#xff0c;因为两天才会有股价差。因此可以将最终利润进行分解&#xff0c;如prices[3] - prices[0] (prices[3] - prices[2]) (prices[2] - prices[1]) (prices[1] - pr…...

音频DAC,ADC,CODEC的选型分析,高性能立体声

想要让模拟信号和数字信号顺利“交往”&#xff0c;就需要一座像“鹊桥”一样的中介&#xff0c;将两种不同的语言转变成统一的语言&#xff0c;消除无语言障碍。这座鹊桥就是转换器芯片&#xff0c;也就是ADC芯片。ADC芯片的全称是Analog-to-Digital Converter, 即模拟数字转换…...

python 连接SQL server 请用pymssql连接,千万别用pyodbc

pymssql官方介绍文档 python 使用 pymssql连接 SQL server 代码示例&#xff1a; 安装pymssql包&#xff1a; pip install pymssql代码&#xff1a; import pymssqldef conn_sqlserver_demo():# 连接字符串示例&#xff08;根据您的配置进行修改&#xff09;conn Nonetry:co…...

IntelliJ IDEA 自带HTTP Client接口插件上传文件示例

如何使用IntelliJ IDEA自带的HTTP Client接口插件进行文件上传的示例。在这个示例中&#xff0c;我们将关注Controller代码、HTTP请求文件&#xff08;xxx.http&#xff09;&#xff0c;以及文件的上传和处理。 Controller代码 首先&#xff0c;让我们看一下处理文件上传的Co…...

C++中的接口有什么用

2023年12月13日&#xff0c;周三上午 今天上午在适配器模式&#xff0c;我发现如果想真正理解适配器模式&#xff0c;就必须学会使用C中的接口&#xff0c;就必须明白为什么要在C中使用接口&#xff0c;所以重新学习了一下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宏定义

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 文章前情预告一、define是个啥&#xff1f;二、为什么要使用define三、怎么使用define四、define的横向拓展五、define思想在生活中的体现!六、结论七、参考资料八、…...

51单片机应用从零开始(十一)·数组函数、指针函数

51单片机应用从零开始&#xff08;九&#xff09;数组-CSDN博客 51单片机应用从零开始&#xff08;十&#xff09;指针-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 是一种在线的、非交互式的编辑器&#xff0c;它一次处理一行内容。处理时&#xff0c;把当前处理的行存储在临时缓冲区中&#xff0c;称为“模式空间”(pattern space)&#xff0c;接着用sed命令处理缓冲区中的内容&#xff0c;处理完成后&…...

tp连接数据库

ThinkPHP内置了抽象数据库访问层&#xff0c;把不同的数据库操作封装起来&#xff0c;我们只需要使用公共的Db类进行操作&#xff0c;而无需针对不同的数据库写不同的代码和底层实现&#xff0c;Db类会自动调用相应的数据库驱动来处理。采用PDO方式&#xff0c;目前包含了Mysql…...

jmeter,断言:响应断言、Json断言

一、响应断言 接口A请求正常返回值如下&#xff1a; {"status": 10013, "message": "user sign timeout"} 在该接口下创建【响应断言】元件&#xff0c;配置如下&#xff1a; 若断言成功&#xff0c;则查看结果树的接口显示绿色&#xff0c;若…...

dockerfite创建镜像---INMP+wordpress

搭建dockerfile---lnmp 在192.168.10.201 使用 Docker 构建 LNMP 环境并运行 Wordpress 网站平台 [rootdocker1 opt]# mkdir nginx mysql php [rootdocker1 opt]# ls #分别拖入四个包&#xff1a; nginx-1.22.0.tar.gz mysql-boost-5.7.20.tar.gz php-7.1.10.tar.bz2 wor…...

服务器数据恢复—raid5热备盘未激活崩溃导致上层oracle数据丢失的数据恢复案例

服务器数据恢复环境&#xff1a; 某品牌X系列服务器&#xff0c;4块SAS硬盘组建了一组RAID5阵列&#xff0c;还有1块磁盘作为热备盘使用。服务器上层安装的linux操作系统&#xff0c;操作系统上部署了一个基于oracle数据库的OA&#xff08;oracle已经不再为该OA系统提供后续服务…...

生产派工自动化:MES系统的关键作用

随着制造业的数字化转型和智能化发展&#xff0c;生产派工自动化成为了提高生产效率、降低成本&#xff0c;并实现优质产品生产的关键要素之一。制造执行系统&#xff08;MES&#xff09;在派工自动化中发挥着重要作用&#xff0c;通过实时数据采集和智能调度&#xff0c;优化生…...

netty-daxin-2(netty常用事件讲解)

文章目录 netty常用事件讲解ChannelHandler接口ChannelHandler适配器类ChannelInboundHandler 子接口Channel 的状态调用时机ChannelHandler 生命周期示例NettServer&CustomizeInboundHandlerNettyClient测试分析 ChannelInboundHandlerAdapter适配器类SimpleChannelInboun…...

使用playbook部署k8s集群

1.部署ansible集群 使用python脚本一个简单的搭建ansible集群-CSDN博客 2.ansible命令搭建k8s&#xff1a; 1.主机规划&#xff1a; 节点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语言开发一个智能停车场管理系统&#xff0c;本系统将严格按照软件开发流程进行各个阶段的工作&#xff0c;采用B/S架构&#xff0c;面向对象编程思想进行项目开发。在引言中&#xff0c;作者将论述…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

省略号和可变参数模板

本文主要介绍如何展开可变参数的参数包 1.C语言的va_list展开可变参数 #include <iostream> #include <cstdarg>void printNumbers(int count, ...) {// 声明va_list类型的变量va_list args;// 使用va_start将可变参数写入变量argsva_start(args, count);for (in…...

沙箱虚拟化技术虚拟机容器之间的关系详解

问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西&#xff0c;但是如果把三者放在一起&#xff0c;它们之间到底什么关系&#xff1f;又有什么联系呢&#xff1f;我不是很明白&#xff01;&#xff01;&#xff01; 就比如说&#xff1a; 沙箱&#…...

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

篇章二 论坛系统——系统设计

目录 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 1. 数据库设计 1.1 数据库名: forum db 1.2 表的设计 1.3 编写SQL 2.系统设计 2.1 技术选型 2.2 设计数据库结构 2.2.1 数据库实体 通过需求分析获得概念类并结合业务实现过程中的技术需要&#x…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...