我在leetcode用动态规划炒股
事情是这样的,突然兴起的我在letcode刷题
- 121. 买卖股票的最佳时机
- 122. 买卖股票的最佳时机 II
- 123. 买卖股票的最佳时机 III
以上三题。
1. 121. 买卖股票的最佳时机
1.1. 暴力遍历,两次遍历
1.1.1. 算法代码
public class Solution {public int MaxProfit(int[] prices) {int profitValue=0;for(int i=0;i<prices.Length;i++){for(int j=i+1;j<prices.Length;j++){if(prices[j]>prices[i]){if(prices[j]-prices[i]>profitValue){profitValue=prices[j]-prices[i];}}}}return profitValue;}
}
上述代码的逻辑为两次遍历,后一个值比前一个值大,并使用哨兵变量profitValue
记录最大差值。
1.1.2. 算法复杂度
- 时间复杂度: O ( n 2 ) = n ∗ ( n − 1 ) 2 O(n^2)=\frac {n*(n-1)}{2} O(n2)=2n∗(n−1)
- 空间复杂度: O ( 1 ) O(1) O(1),因为只有哨兵变量
profitValue
1.1.3. 算法问题
前面我们讲到,这个时间复杂度是 O ( n 2 ) O(n^2) O(n2),是一个指数函数。
那么在数据非常大的时候,其根据时间复杂度可以知道,其复杂度非常的高,如leetcode的超时案例
[886,729,539,474,5,653,588,198,313,111,38,808,848,364,819,747,520,568,583,253,605,442,779,903,217,284,927,33,859,75,418,612,174,316,167,40,945,740,174,279,985,133,38,919,528,844,101,291,673,561,.......
中间有3万个数值
.......561,644,484,868,53,936,186,35,219,84,455,971,922,862,434,553,948,857,491,622,162,934,66,486,569,690,596,506,452,635,690]
其时间复杂度是: 30000 ∗ 29999 / 2 = 449985000 30000*29999/2=449985000 30000∗29999/2=449985000,其计算数值大的可怕。
1.2. 一次遍历
1.2.1. 算法代码
public class Solution {public int MaxProfit(int[] prices) {int minprice = int.MaxValue;int maxprofit = 0;for (int i = 0; i < prices.Length; i++) {if (prices[i] < minprice) {minprice = prices[i];} else if (prices[i] - minprice > maxprofit) {maxprofit = prices[i] - minprice;}}return maxprofit;}
}
其算法,基本思路是:在最低点购入,在最高点卖出
,由于for循环是从0开始的,所以其每一次minprice
是当前时点前最低点购入值,故此算法可靠
1.2.2. 算法复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) = 2 O(1)=2 O(1)=2
2.2 122. 买卖股票的最佳时机 II
第一题相较比较简单,而第二题中增加了一个限定:可以购买多次,只是手上最多只有一支股票
2.1. 贪心算法
2.1.1. 算法代码
public class Solution {public int MaxProfit(int[] prices) {int ans = 0;int n = prices.Length;for (int i = 1; i < n; ++i) {int diffPrice=prices[i] - prices[i - 1];if(diffPrice>0){ans += diffPrice;}}return ans;}
}
2.1.2. 算法思路与步骤
只要后一天的价格比今天高,那么我今天就买,后一天就卖。
2.1.3. 算法复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) = 2 O(1)=2 O(1)=2
2.2. 动态规划算法
2.2.1. 算法代码
public class Solution {public int MaxProfit(int[] prices) {if (prices.Length < 2) {return 0;}int[] OwnStocks=new int[prices.Length];int[] NoStocks=new int[prices.Length];OwnStocks[0]=-prices[0];NoStocks[0]=0;for(int i=1;i<prices.Length;i++){OwnStocks[i]=Math.Max(OwnStocks[i-1],NoStocks[i-1]-prices[i]);NoStocks[i]=Math.Max(NoStocks[i-1],OwnStocks[i-1]+prices[i]);}return NoStocks[prices.Length-1];}
}
2.2.2. 算法思路与步骤
- 由于不可以同时存在多支股票,所以每天只有可能有两种状态
有股票
、没有股票
- 第一天存在股票=0-第一天股票价值;第一天不存在股票=0(没有购买或者当天售出)
- 后续每一天,
当天有股票的最大利益
=Math.Max(前一天有股票的值
,前一天没有股票的值
-当天股票值
[购买股票]) - 后续每一天,
当前没有股票的最大利益
=Math.Max(前一天没有股票的值
,前一天有股票的值
+当天股票值
[卖出股票]`)
图解如下:
2.2.3. 算法复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) = 2 n O(n)=2n O(n)=2n
2.3. 123. 买卖股票的最佳时机 III
2.3.1. 动态规划算法
这一题就和第二题的动态规划类似,只是第二题是两个状态,而第三题是四个状态。
没有买入
第一次买入,没有卖出
第一次买出,没有卖入
第二次买入,没有卖出
第二次买出
由于没有买入
全程是0所以不做考虑,列出了5种,但实际上只有4种状态。
2.3.2. 算法代码
public class Solution {public int MaxProfit(int[] prices) {if(prices.Length<2){return 0;}int oneBuy=-prices[0];int oneSale=0;int twoBuy=-prices[0];int twoSale=0;for(int i=1;i<prices.Length;i++){oneBuy=Math.Max(oneBuy,-prices[i]);oneSale=Math.Max(oneSale,oneBuy+prices[i]);twoBuy=Math.Max(twoBuy,oneSale-prices[i]);twoSale=Math.Max(twoSale,twoBuy+prices[i]);}return twoSale;}
}
2.3.3. 算法复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) = 4 O(1)=4 O(1)=4
相关文章:

我在leetcode用动态规划炒股
事情是这样的,突然兴起的我在letcode刷题 121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II123. 买卖股票的最佳时机 III 以上三题。 1. 121. 买卖股票的最佳时机 1.1. 暴力遍历,两次遍历 1.1.1. 算法代码 public class Solution {public int Ma…...
rust实践-异步并发socket通信
客户端 [package] name = "rust_client" version = "0.1.0" edition = "2021"[dependencies] tokio = {version = "1.14.0", features = ["full"] }use tokio::io::{self, AsyncReadExt, AsyncWriteExt}; use tokio::net::…...
SolidUI社区-根据Prompt打造人设
背景 随着文本生成图像的语言模型兴起,SolidUI想帮人们快速构建可视化工具,可视化内容包括2D,3D,3D场景,从而快速构三维数据演示场景。SolidUI 是一个创新的项目,旨在将自然语言处理(NLP)与计算机图形学相…...

设计模式行为型——观察者模式
目录 什么是观察者模式 观察者模式的实现 观察者模式角色 观察者模式类图 观察者模式举例 观察者模式代码实现 观察者模式的特点 优点 缺点 使用场景 注意事项 实际应用 什么是观察者模式 观察者模式(Observer Pattern)是一种行为型设计模式…...

Kernel Exception导致手机重启案例分析
和你一起终身学习,这里是程序员Android 经典好文推荐,通过阅读本文,您将收获以下知识点: 一、高温触发 Kernel Exception 重启问题二、解决方案三、提高电池温度方案 一、 高温触发 Kernel Exception 重启问题 手机 电池温度 默认60度以上高温…...

C++入门篇5---模板
相信大家都遇到过这么一种情况,为了满足不同类型的需求,我们要写多个功能相同,参数类型不同的代码,为此,C引入了泛型编程这一概念,而模板就是实现泛型编程的基础,其实本质就是我们写一个类似”模…...

L2CS-Net: 3D gaze estimation
L2CS-Net: Fine-Grained Gaze Estimation in Unconstrained Environments论文解析 摘要1. 简介2. Related Work3. METHOD3.1 Proposed loss function3.2 L2CS-Net 结构3.3 数据集3.4 评价指标 4. 实验4.1 实验结果 论文地址:L2CS-Net: Fine-Grained Gaze Estimation…...
kenernetes/k8s笔试面试
k8s的基础概念 k8s本质是一个容器编排系统,可以管理容器的生命周期,应用部署,更新,维护,应用提供服务,扩容缩容应用,故障自愈。 k8s与docker的关系 docker:是一种轻量级的虚拟化技术。运维层…...
我们真的是在做数据治理吗
我们真的是在做数据治理吗? 什么是数据治理? 数据治理和数据管理有什么区别? 相信即使是考过数据治理工程师的人,面对这2个问题也仍然会有这个疑问。 目前国际和国内对于数据治理没有明确统一的定义,对于数据治理的服…...

聊聊汽车电子的话题
当谈到汽车电子时,有许多有趣的话题可以探讨。以下是一些可能感兴趣的话题: 自动驾驶技术:自动驾驶技术正变得越来越先进,它们如何在汽车中实现?它们将如何改变我们的交通方式以及对道路安全的影响? 电动汽…...

ThinkPHP6企业OA办公系统
有需要请加文章底部Q哦 可远程调试 ThinkPHP6企业OA办公系统 一 介绍 勾股OA基于ThinkPHP6开发,前端Layui,数据库mysql,是一款实用的企业办公系统。可多角色登录,集成了系统设置、人事管理、消息管理、审批管理、日常办公、客户…...

PPS Tester测量原理和实施方法
怿星科技发布了新品PPS Tester,这是一款基于1PPS方法的时间同步精度测试设备。PPS Tester由硬件模块ETS2110和上位机软件ePPSTester构成。本文将围绕此设备的应用场景,介绍相关概念和设备使用方法。 什么是时间同步? 时间同步就是采取某项技…...

浅谈新电改背景下电网企业综合能源服务商业模式研究及发展方向
安科瑞 华楠 摘要: 新电改方案实施后,由于输配电价的改革和售电侧的放开,电网企业的盈利模式也随之发生了变化。这就要求电网企业转变服务理念与经营方式,来寻求竞争优势。基于“魏朱六要素商业模式”模型,对电网企业综合能源服务…...

SpringBoot + Docker 实现一次构建到处运行~
一、容器化部署的好处 图片 Docker 作为一种新兴的虚拟化方式,它可以更高效的利用系统资源,不需要进行硬件虚拟以及运行完整操作系统等额外开销。 传统的虚拟机技术启动应用服务往往需要数分钟,而 Docker 容器应用,由于直接运行…...
clang-format格式化代码
1. clang-format简介 Clang-Format可用于格式化(排版)多种不同语言的代码。其自带的排版格式主要有:LLVM, Google, Chromium, Mozilla, WebKit等; 利用style参数配置风格。通过编写 .clang-format 文件,可以实现代码风格的配置。…...

品牌宣传与媒体传播是声誉管理的主要方式之一
企业声誉是现如今影响品牌信任度、客户忠诚度的重要因素,也被视为企业的一种无形资,更影响着企业未来的发展。因此,企业声誉管理也日渐成为企业管理的重要课题之一,尤其在品牌营销管理领域。 什么是声誉管理?声誉管理有…...
2023年8月7日-8月13日,(上午熟悉公司代码,周一到周五晚上优先工作所急视频教程,其他业余时间进行ue视频教程,为独立游戏做准备)
按照规划,上午熟悉公司源码,下午进行filament和ue渲染,晚上写工作代码。回家后泛读pbrt或者其他书籍催眠。 业余学习ue的各种视频教程,为独立游戏做准备(公司也实行末位淘汰,给自己留条后路)。累…...

Vue3 第二节 Vue3的响应式
1.Vue3的响应式原理 2.ref函数和reactive函数的对比 3.setup注意点 一.Vue3的响应式原理 1.Vue2.x中的响应式原理 ① 实现原理 对象类型:通过Object.defineProperty() 对属性的读取,修改进行拦截(数据劫持)数组类型…...

通过easyui实现动态控制表格字段显示、导出表格数据
前言 学过layui前端框架的都知道,layui默认帮我们实现了控制表格字段显示以及数据的导出功能。 1、控制表格字段显示 2、数据导出 3、导出为pdf:导出按钮的右边那个按钮就是打印pdf的 那么,easyui要怎么实现这些功能呢?这篇文章就…...
JWT入门,jwt可以解密吗?
JWT 什么是 JWT JSON Web Token,通过数字签名的方式,以 JSON 对象为载体,在不同的服务终端之间安全地传输信息 官网:https://jwt.io/SDK: https://jwt.io/libraries (含Java和各种语言)Java SDK(上面的SDK链接得到): https://g…...

业务系统对接大模型的基础方案:架构设计与关键步骤
业务系统对接大模型:架构设计与关键步骤 在当今数字化转型的浪潮中,大语言模型(LLM)已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中,不仅可以优化用户体验,还能为业务决策提供…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...

高频面试之3Zookeeper
高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个?3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制(过半机制࿰…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)
可以使用Sqliteviz这个网站免费编写sql语句,它能够让用户直接在浏览器内练习SQL的语法,不需要安装任何软件。 链接如下: sqliteviz 注意: 在转写SQL语法时,关键字之间有一个特定的顺序,这个顺序会影响到…...

【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...