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

我在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(n1)
  • 空间复杂度: 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 3000029999/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用动态规划炒股

事情是这样的&#xff0c;突然兴起的我在letcode刷题 121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II123. 买卖股票的最佳时机 III 以上三题。 1. 121. 买卖股票的最佳时机 1.1. 暴力遍历&#xff0c;两次遍历 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打造人设

背景 随着文本生成图像的语言模型兴起&#xff0c;SolidUI想帮人们快速构建可视化工具&#xff0c;可视化内容包括2D,3D,3D场景&#xff0c;从而快速构三维数据演示场景。SolidUI 是一个创新的项目&#xff0c;旨在将自然语言处理&#xff08;NLP&#xff09;与计算机图形学相…...

设计模式行为型——观察者模式

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

Kernel Exception导致手机重启案例分析

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

C++入门篇5---模板

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

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 实验结果 论文地址&#xff1a;L2CS-Net: Fine-Grained Gaze Estimation…...

kenernetes/k8s笔试面试

k8s的基础概念 k8s本质是一个容器编排系统&#xff0c;可以管理容器的生命周期&#xff0c;应用部署&#xff0c;更新&#xff0c;维护&#xff0c;应用提供服务&#xff0c;扩容缩容应用&#xff0c;故障自愈。 k8s与docker的关系 docker:是一种轻量级的虚拟化技术。运维层…...

我们真的是在做数据治理吗

我们真的是在做数据治理吗&#xff1f; 什么是数据治理&#xff1f; 数据治理和数据管理有什么区别&#xff1f; 相信即使是考过数据治理工程师的人&#xff0c;面对这2个问题也仍然会有这个疑问。 目前国际和国内对于数据治理没有明确统一的定义&#xff0c;对于数据治理的服…...

聊聊汽车电子的话题

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

ThinkPHP6企业OA办公系统

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

PPS Tester测量原理和实施方法

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

浅谈新电改背景下电网企业综合能源服务商业模式研究及发展方向

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

SpringBoot + Docker 实现一次构建到处运行~

一、容器化部署的好处 图片 Docker 作为一种新兴的虚拟化方式&#xff0c;它可以更高效的利用系统资源&#xff0c;不需要进行硬件虚拟以及运行完整操作系统等额外开销。 传统的虚拟机技术启动应用服务往往需要数分钟&#xff0c;而 Docker 容器应用&#xff0c;由于直接运行…...

clang-format格式化代码

1. clang-format简介 Clang-Format可用于格式化&#xff08;排版&#xff09;多种不同语言的代码。其自带的排版格式主要有&#xff1a;LLVM, Google, Chromium, Mozilla, WebKit等; 利用style参数配置风格。通过编写 .clang-format 文件&#xff0c;可以实现代码风格的配置。…...

品牌宣传与媒体传播是声誉管理的主要方式之一

企业声誉是现如今影响品牌信任度、客户忠诚度的重要因素&#xff0c;也被视为企业的一种无形资&#xff0c;更影响着企业未来的发展。因此&#xff0c;企业声誉管理也日渐成为企业管理的重要课题之一&#xff0c;尤其在品牌营销管理领域。 什么是声誉管理&#xff1f;声誉管理有…...

2023年8月7日-8月13日,(上午熟悉公司代码,周一到周五晚上优先工作所急视频教程,其他业余时间进行ue视频教程,为独立游戏做准备)

按照规划&#xff0c;上午熟悉公司源码&#xff0c;下午进行filament和ue渲染&#xff0c;晚上写工作代码。回家后泛读pbrt或者其他书籍催眠。 业余学习ue的各种视频教程&#xff0c;为独立游戏做准备&#xff08;公司也实行末位淘汰&#xff0c;给自己留条后路&#xff09;。累…...

Vue3 第二节 Vue3的响应式

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

通过easyui实现动态控制表格字段显示、导出表格数据

前言 学过layui前端框架的都知道&#xff0c;layui默认帮我们实现了控制表格字段显示以及数据的导出功能。 1、控制表格字段显示 2、数据导出 3、导出为pdf&#xff1a;导出按钮的右边那个按钮就是打印pdf的 那么&#xff0c;easyui要怎么实现这些功能呢&#xff1f;这篇文章就…...

JWT入门,jwt可以解密吗?

JWT 什么是 JWT JSON Web Token&#xff0c;通过数字签名的方式&#xff0c;以 JSON 对象为载体&#xff0c;在不同的服务终端之间安全地传输信息 官网&#xff1a;https://jwt.io/SDK: https://jwt.io/libraries (含Java和各种语言)Java SDK(上面的SDK链接得到): https://g…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

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服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

高频面试之3Zookeeper

高频面试之3Zookeeper 文章目录 高频面试之3Zookeeper3.1 常用命令3.2 选举机制3.3 Zookeeper符合法则中哪两个&#xff1f;3.4 Zookeeper脑裂3.5 Zookeeper用来干嘛了 3.1 常用命令 ls、get、create、delete、deleteall3.2 选举机制 半数机制&#xff08;过半机制&#xff0…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

【决胜公务员考试】求职OMG——见面课测验1

2025最新版&#xff01;&#xff01;&#xff01;6.8截至答题&#xff0c;大家注意呀&#xff01; 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:&#xff08; B &#xff09; A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...