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

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

文章目录

  • 题目链接:
  • 题目描述:
  • 解题思路一(贪心算法):
  • 解体思路二(动态规划):

题目链接:

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

题目描述:

在这里插入图片描述

解题思路一(贪心算法):

本问题可以通过贪心算法解决。我们可以将问题分解为一系列连续的上涨子序列,并在每个上涨子序列中,计算利润,并将其累加到最终的结果中。具体的做法是:

  • 贪心算法的核心思想:对于每个上升的子序列,我们希望在价格上涨时不断买入,价格下跌时卖出。
  • 连续上升子序列:在遍历股票价格的过程中,如果当前价格小于下一天的价格,说明价格在上涨,应该继续持有股票;如果当前价格大于或等于下一天的价格,说明我们已经遇到了一个下降的趋势,在此时卖出,计算当前区间的利润。
  • 利润计算:每次找到一个上涨子序列时,我们就将该子序列的利润(即当前价格减去子序列的起始价格)累加到总利润中。

复杂度分析:

  • 时间复杂度O(N)
  • 空间复杂度O(1)

代码实现方式一:

找到每一个连续递增子序列,将其差值作为利润记录到总利润中

class Solution {
public:int maxProfit(vector<int>& prices) {int p1 = 0;int p2 = 0;int res = 0;int n = prices.size();while(p2<n-1){if(prices[p2]< prices[p2+1]){p2++;continue;}else{res = res + (prices[p2]-prices[p1]);p2++;p1=p2;}}return res+(prices[p2]-prices[p1]);}
};

代码实现方式2:

  • 每次遍历数组,比较相邻的价格(即 prices[i]prices[i+1]):
  • 如果 prices[i+1] > prices[i],则说明价格上涨,可以在今天买入,明天卖出,获得的利润是 prices[i+1] - prices[i]
  • 如果 prices[i+1] <= prices[i],则不进行操作,不获得任何利润。
    利用 max(0, prices[i+1] - prices[i]) 确保当价格下降时不加入负的利润。
  • 本质上与第一种方式一致,但是这种实现方式更简洁
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int res = 0;for(int i=0; i<n-1; i++){res += max(0, prices[i+1]-prices[i]);}return res;}
};

解体思路二(动态规划):

由于题目中要求在任何时候手里最多只有一支股票,因此在每天交易完成后,只可能手里有一支股票或者没有股票的状态

我们可以定义:

  • dp[i][0] : 表示第i天交易完成后手里没有股票的最大利润(i从0开始)
  • dp[i][1] : 表示第i天交易完成后手里持有一支股票的最大利润(i从0开始)

因此dp[i][0] 的转移方程,如果这一天交易完成后手里没有股票,那么可能的状态转移为前一天已经没有股票了,即 dp[i-1][0],或者前一天结束的时候手里有一支股票,即dp[i-1][1],这时候我们要将其卖出,并获得prices[i]收益。因此为了利益最大化,我们的状态转移方程:

d p [ i ] [ 0 ] = max ⁡ ( d p [ i − 1 ] [ 0 ] , d p [ i − 1 ] [ 1 ] + p r i c e s [ i ] ) dp[i][0] = \max \left( dp[i-1][0], dp[i-1][1] + prices[i] \right) dp[i][0]=max(dp[i1][0],dp[i1][1]+prices[i])

再来考虑dp[i][1],如果转移状态前一天已经持有一支股票。即dp[i-1][1],或者前一天结束的时候手里没有股票,即dp[i-1][0],这时候我们要将其买入,并减少prices[i]的收益。可以列出状态转移方程:

d p [ i ] [ 1 ] = max ⁡ ( d p [ i − 1 ] [ 0 ] − p r i c e s [ i ] , d p [ i − 1 ] [ 1 ] ) dp[i][1] = \max \left( dp[i-1][0] - prices[i], dp[i-1][1] \right) dp[i][1]=max(dp[i1][0]prices[i],dp[i1][1])

对于初始状态,我们直到在第0天交易结束的时候:

  • dp[0][0] = 0
  • dp[0][1] = -prices[0]

代码实现:

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();int dp[n][2];dp[0][0] = 0;dp[0][1] = -prices[0];for(int i=1; i<n; i++){dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]);dp[i][1] = max(dp[i-1][0]-prices[i], dp[i-1][1]);}return dp[n-1][0];}
};

动态规划解析参考:

https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solutions/476791/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/?envType=study-plan-v2&envId=top-interview-150

相关文章:

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

文章目录 题目链接&#xff1a;题目描述&#xff1a;解题思路一&#xff08;贪心算法&#xff09;&#xff1a;解体思路二&#xff08;动态规划&#xff09;&#xff1a; 题目链接&#xff1a; 122.买卖股票的最佳时机II 题目描述&#xff1a; 解题思路一&#xff08;贪心算法…...

openGauss开源数据库实战十九

文章目录 任务十九 openGauss DML 语句测试任务目标实施步骤一、准备工作二、INSERT语句三、DELETE语句四、UPDATE语句五、清理工作 任务十九 openGauss DML 语句测试 任务目标 掌握DML语句的用法,包括INSERT语句、DELETE语句和UPDATE语句。 实施步骤 一、准备工作 使用Li…...

恶补英语初级第18天,《询问他人的喜好(上)》

对话 Do you like coffee? Yes, I do. Do you want a cup? Yes, please. Do you want any sugar? Yes, please. Do you want any milk? No, thank you. I don’t like milk in my coffee, I like black coffee. Do you like biscuits? Yes, I do. Do you want one? Yes, …...

centos 报 ping: www.baidu.com: Name or service not known

[rootlocalhost ~]$ ping www.baidu.com ping: www.baidu.com: Name or service not known解决办法&#xff1a; 首先要求检查特定文件&#xff08;/etc/resolv.conf&#xff09;内是否正确配置了 DNS sudo vim /etc/resolv.conf没有正确配置可以添加如下代码&#xff1a; n…...

Python:使用随机森林分类器进行模型评估:ROC 曲线与 AUC 指标计算

前言 这段代码的目标是使用 随机森林分类器&#xff08;Random Forest Classifier&#xff09; 来进行二分类任务&#xff0c;并基于每个数据子集计算 ROC 曲线&#xff08;Receiver Operating Characteristic Curve&#xff09;以及 AUC&#xff08;Area Under Curve&#xf…...

数据库表约束完全指南:提升数据完整性和准确性

数据库表约束完全指南&#xff1a;提升数据完整性和准确性 在数据库设计中&#xff0c;表约束是确保数据完整性和准确性的关键工具。本文将详细介绍各种类型的表约束及其使用方法&#xff0c;包括非空约束、唯一约束、主键约束、外键约束、默认值约束、检查约束以及自动递增约…...

【JavaEE】多线程(6)

一、用户态与内核态 【概念】 用户态是指用户程序运行时的状态&#xff0c;在这种状态下&#xff0c;CPU只能执行用户态下的指令&#xff0c;并且只能访问受限的内存空间 内核态是操作系统内核运行时的状态&#xff0c;内核是计算机系统的核心部分&#xff0c;CPU可以执行所有…...

BERT和RoBERTa;双向表示与单向的简单理解

目录 BERT和RoBERTa大型预训练语言模型 BERT的原理 RoBERTa的原理 举例说明 双向表示与单向的简单理解 除了预训练语言模型,还有什么模型 一、模型类型与结构 二、训练方式与数据 三、应用场景与功能 四、技术特点与优势 BERT和RoBERTa大型预训练语言模型 BERT(Bi…...

Pytorch使用手册-计算机视觉迁移学习教程(专题十三)

在本教程中,你将学习如何使用迁移学习训练一个卷积神经网络进行图像分类。更多关于迁移学习的内容可以参考 CS231n 课程笔记。 引用课程笔记中的内容: 实际上,很少有人从头开始训练一个完整的卷积网络(随机初始化),因为拥有足够大数据集的情况相对罕见。相反,通常会在非…...

Jackson - Java对象与JSON相互转换

在这篇文章中&#xff0c;我将向您展示如何使用Jackson-databind API来实现Java对象与JSON之间的绑定&#xff0c;以及如何将JSON数据转换为Java对象。 对于Java开发者来说&#xff0c;将JSON转换为Java对象及反向操作是一个常见的任务&#xff0c;因此我将通过示例演示如何完…...

怎麼解決路由器IP地址衝突?

路由器IP地址衝突通常發生在網路中有兩個設備嘗試使用相同的IP地址時。這種衝突會導致網路連接問題&#xff0c;因為每個設備需要一個唯一的IP地址才能正常通信。 1. 重啟設備 重啟路由器和設備&#xff1a;有時候簡單的重啟可以解決問題&#xff0c;設備重新獲取一個新的IP地…...

趣味数学 2.3.7 | 完全免费,无注册登录,简约纯净

趣味数学是一款完全免费的数学学习软件&#xff0c;支持安卓系统。它无需登录注册&#xff0c;界面简约纯净&#xff0c;分类详细&#xff0c;涵盖趣味数学、数学初练、应用计算、数字推理、图形推理、数字2048、题目练习和数学知识等多个分类。每个分类包含丰富的题目和关卡&a…...

Oracle ASM特性介绍和增删盘操作

1. 介绍 1.1. 在没有ASM之前ORACLE数据库靠什么去解决存储问题&#xff1a; 裸设备:裸设备就是没有被文件系统格式化的分区或者是直接挂载到操作系统上的磁盘。ORACLE可以直接将数据写入到裸设备中&#xff0c;读写能非常优异。像ORACLE的数据文件、控制文件、REDO日志在过去…...

深度优先搜索迷宫路径

深度优先搜索迷宫路径 问题描述 我们需要编写一个程序&#xff0c;通过深度优先搜索&#xff08;DFS&#xff09;找到从迷宫左上角到右下角的一条通路。 迷宫的表示&#xff1a; 迷宫由 0 和 1 构成的二维数组表示。0 表示可以走的路径&#xff0c;1 表示障碍。用户输入迷宫的…...

多媒体技术的 发展阶段----高中信息技术教资面试

上课&#xff0c;同学们好&#xff01;请坐 在正式上课之前&#xff0c;老师带来 了一段微课视频&#xff0c;请同学们认真观看大屏幕。等下来回答老师的问题。 好&#xff0c;视频播放完成了&#xff0c;现在老师想问问大家。大家从视频中都看到了什么尼&#xff1f;好&…...

行为型设计模式之《责任链模式》实践

定义 责任链模式&#xff08;Chain Of Responsibility Pattern&#xff09;顾名思义&#xff0c;就是为请求创建一条处理链路&#xff0c;链路上的每个处理器都判断是否可以处理请求&#xff0c;如果不能处理则往后走&#xff0c;依次从链头走到链尾&#xff0c;直到有处理器可…...

中酱黑松露手工古法酱油,邂逅独特 “酱油红”

在美食的世界里&#xff0c;调味品往往扮演着画龙点睛的角色&#xff0c;它们虽不似主食材那般夺目&#xff0c;却能悄无声息地赋予菜肴灵魂与韵味。而今天&#xff0c;要带大家走进的&#xff0c;便是中酱手工古法酱油所营造出的独特美味天地&#xff0c;去领略那一抹别具魅力…...

Java NIO channel

channel(通道)&#xff0c;byteBuffer(缓冲区)&#xff0c;selector&#xff08;io多路复用&#xff09;&#xff0c;通道FileChannel,SocketChannel的transferTo,transferFrom,MappedByteBuffer实现了零拷贝。 JVM调操作系统方法&#xff0c;read,write&#xff0c;都可以送字…...

智能交通(8)——腾讯开悟智能交通信号灯调度赛道

本文档用于记录参加腾讯开悟智能信号灯调度赛道的模型优化过程。官方提供了dqn和target_dqn算法&#xff0c;模型的优化在官方提供的代码基础上进行。最终排名是在榜单16&#xff0c;没能进入最后的决赛。 一.赛题介绍 赛题简介&#xff1a;在本地赛题中&#xff0c;参赛团队…...

ip所属地址是什么意思?怎么改ip地址归属地

在数字化时代&#xff0c;IP地址作为网络设备的唯一标识符&#xff0c;不仅关乎设备间的通信&#xff0c;还涉及到用户的网络身份与位置信息。IP所属地址&#xff0c;即IP地址的归属地&#xff0c;通常反映了设备连接互联网时的地理位置。本文将深入解析IP所属地址的含义&#…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

visual studio 2022更改主题为深色

visual studio 2022更改主题为深色 点击visual studio 上方的 工具-> 选项 在选项窗口中&#xff0c;选择 环境 -> 常规 &#xff0c;将其中的颜色主题改成深色 点击确定&#xff0c;更改完成...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...

Java 二维码

Java 二维码 **技术&#xff1a;**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...