LC:动态规划-买卖股票
文章目录
- 121. 买卖股票的最佳时机
- 122. 买卖股票的最佳时机 II
- 714. 买卖股票的最佳时机含手续费
- 309. 买卖股票的最佳时机含冷冻期
121. 买卖股票的最佳时机
链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/

使用贪心,直接秒了,需要注意的是,由于题目所说股票只能购买一次,所以不存在累加的情况,对比下面第二题思考:
代码:
class Solution {public int maxProfit(int[] prices) {// 只能有一直股票,所以价格不能够累加,只拥有一直股票。int minPrice = prices[0];int ans = 0;for(int price : prices){ans = Math.max(ans, price - minPrice);minPrice = Math.min(minPrice, price);}return ans;}
}
122. 买卖股票的最佳时机 II
题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/description/

方法一:直接使用贪心,类似第一题,本题最大不同在于可以多次购买并且出售股票,只需要保证每次购买后出售股票中获取利润大于0即可,随后将遍历过程中获取到的所有利润相加,并且需要及时更新上次购买股票的价格:prevPrice即可。
代码如下:
class Solution {public int maxProfit(int[] prices) {// 直接贪心int ans = 0;int prevPrice = prices[0];for(int price : prices){if(price - prevPrice > 0){ans += price - prevPrice;}prevPrice = price;}return ans;}
}
方法二:动态规划 秒了,设二维dp数组,dp[i][0]表示第i天不持有能够获得的最大利润,dp[i][1]表示第 i 天持有股票能够获取的最大利润。
注意需要初始化第一天的利润值:dp[0][0] = 0,dp[0][1] = -prices[0];
具体动态数组递推公式参考下面代码:
class Solution {public int maxProfit(int[] prices) {// 动态规划,dp[i][0]表示第i天不持有股票能够获取的最大利润,dp[i][1]表示第i天持有股票能够获取的最大利润int m = prices.length;int[][] dp = new int[m][2];dp[0][0] = 0; dp[0][1] = -prices[0];for(int i = 1; i < m; i++){dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);}return Math.max(dp[m - 1][0], dp[m - 1][1]);}
}
对于动态规划的理解,是解决下面变形题的关键。
714. 买卖股票的最佳时机含手续费
题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

带手续费的题目本质上和上面题目使用动态规划解决并无差异。
首先需要明确题目意思,题目说道,每笔交易需要支付一笔手续费,并且这个手续费指的是买入、卖出这整个过程。 借助此,我们可以将手续费统一到购买股票的时候支付,此后题目就和上述动态规划一样。
代码如下:
class Solution {public int maxProfit(int[] prices, int fee) {// 动态规划// dp[i][0]表示第i天不持有股票能够获取的最大利润// dp[i][1]表示第i天持有股票能够获取的最大利润// 并且规定股票的手续费全部在买入的时候付,卖出的时候不需要付手续费int len = prices.length;int[][] dp = new int[len][2];dp[0][0] = 0;dp[0][1] = -prices[0] - fee;for(int i = 1; i < len; i++){dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i] - fee);}return Math.max(dp[len - 1][0], dp[len - 1][1]);}
}
309. 买卖股票的最佳时机含冷冻期
题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/

第一次看到题目联想到的是在上面两道动态规划的基础上修改一番,仍然使用两个变量表示0表示不持有股票,1表示持有股票。但此时存在一个问题:对于dp[i][0] 不持有股票的表示,无法确定对于某一天「是前一天不持有股票还是前一天持有股票随后将股票卖掉而出现的新的不持有股票的状态。」对于这两种不同的状态采用的处理方式也不同,所以使用两种状态进行动态规划存在状态歧义。意识到这一点后,在两个状态变量的基础上添加新的一个新的状态。此时使用dp[len][3]进行递归。
- dp[i][0]:表示第i天不持有股票且未卖出股票。
- dp[i][1]:表示第i天不持有股票且可能有卖出股票。
- dp[i][2]:表示第i天持有股票。
具体状态转移公式及参考下面代码:
class Solution {public int maxProfit(int[] prices) {// 动态规划int len = prices.length;int[][] dp = new int[len][3];// dp[i][0]不持有未卖出 dp[i][1]不持有有卖出 dp[i][2]持有dp[0][0] = 0;dp[0][1] = 0;dp[0][2] = -prices[0];for(int i = 1; i < len; i++){dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2] + prices[i]);dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][0] - prices[i]);}return Math.max(dp[len - 1][0], Math.max(dp[len - 1][1], dp[len - 1][2]));}
}
相关文章:
LC:动态规划-买卖股票
文章目录 121. 买卖股票的最佳时机122. 买卖股票的最佳时机 II714. 买卖股票的最佳时机含手续费309. 买卖股票的最佳时机含冷冻期 121. 买卖股票的最佳时机 链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/ 使用贪心,…...
FLINK SQL 任务参数
在Flink SQL任务中,参数配置对于任务的性能和稳定性至关重要。以下是对运行时参数、优化器参数和表参数的详细解析: 一、运行时参数 运行时参数主要影响Flink作业在执行过程中的行为。以下是一些关键的运行时参数: 并行度(Para…...
HCIP——以太网交换安全(四)DHCP Snooping
目录 一、DHCP Snooping的知识点 二、DHCP Snooping实验拓扑 三、总结 一、DHCP Snooping的知识点 1.1、DHCP snooping 概述: ①DHCP Snooping使能DHCP的一种安全特性,用于保证DHCP客户端从合法的DHCP服务端获取IP地址。DHCP服务器记录DHCP客户端IP…...
k8s worker 节点关机 sts 管理的 pod 无法迁移
背景 1.28.2 版本 k8s 中的一台 worker 节点内存异常,需要关机换内存,正好可以测试一下 pod 的迁移。 发现 deployment 管理的 pod 是能够重新创建飘到其他节点上的,但是 statefulset 管理的 pod 一直处于 Terminating 状态无法迁移&#…...
排序04 视频播放建模
视频播放时长 用p拟合y,t是用户的实际观看时长,用y和p熵作为损失函数,使得p接近y。 输出z,对z做sigmoid变换。 exp(z)可以视为对播放时长的预估 视频完播 回归方法 二元分类方法 调整:预估完播率不能直接使用...
【常见大模型API调用】第三篇:清华智谱--智谱AI
1. 公司及模型介绍 智谱AI是一家由清华大学计算机系知识工程实验室的技术成果转化而来的AI知识智能技术开发商。智谱AI致力于打造新一代认知智能大模型,专注于做大模型的中国创新。 2024年1月16日,智谱AI在首届技术开放日上发布了新一代基座大模型GLM-…...
LayerSkip – Meta推出加速大型语言模型推理过程的技术
我们提出的 LayerSkip 是一种端到端的解决方案,可加快大型语言模型(LLM)的推理速度。 首先,在训练过程中,我们采用了层间丢弃技术(layer dropout),早期层间丢弃率较低,后期层间丢弃率较高。 其次…...
环境变量与本地变量(Linux)
引言 在当今的计算机技术领域,Linux操作系统以其稳定性和灵活性而广受欢迎。它不仅是服务器和开发者的首选平台,也是探索计算机科学和系统编程的宝库。在这个强大的操作系统中,环境变量与本地变量扮演着至关重要的角色,它们是管理…...
【完-网络安全】Windows防火墙及出入站规则
文章目录 防火墙入站和出站的区别域网络、专用网络、公用网络的区别 防火墙 防火墙默认状态一般是出站允许,入站阻止。 入站和出站的区别 入站就是别人来访问我们的主机,也就是正向shell的操作 出站就是反向shell,主机需要主动连接kali&am…...
Vue学习记录之十七 css中样式穿透及新特征介绍
一、scoped原理 在vue页面的css中,有一个设置为scoped,使用以后dom的节点会出现下面的规则。其实我们打完包就是一个html页面,如果不做处理,将会导致css混乱。 给HTML的DOM节点加一个不重复data属性(形如:data-v-123)来表示他的唯一性在每句css选择器的末尾(编译后的生成的…...
Nature 正刊丨海洋涡旋中常见的地下热浪和寒潮
01摘要 由于全球变暖,极端海洋温度事件变得越来越普遍,造成了灾难性的生态和社会经济影响1,2,3,4,5。尽管基于卫星观测对表层海洋热浪(MHW)和海洋寒潮(MCS)进行了广泛的研究6,7,但我们对这些极…...
代码随想录算法训练营第六十二天| prim算法,kruskal算法
训练营六十二天打卡,图论比较难,坚持下来胜利就在眼前! 53.卡码网【寻宝】 题目链接 解题过程 没做过类似的题目,跟着答案敲了一遍最小生成树 可以使用 prim算法 也可以使用 kruskal算法计算出来。prim算法 是从节点的角度 采用…...
Newstar_week1_week2_wp
week1 wp crypto 一眼秒了 n费马分解再rsa flag: import libnum import gmpy2 from Crypto.Util.number import * p 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297…...
今天我们研究一段代码(异或位运算)
let a 18 // 甲 let b 20 // 乙a a ^ b b a ^ b a a ^ b console.log("a",a) // a 20 console.log("b",b) // b 18今天我们就研究上面这一段代码,简单解释一下,初始化一个a 18 b 20, 中间经过了三次的异或之后…...
pycharm中使用ctrl+鼠标滚轮改变字体大小
文章目录 pycharm使用ctrl鼠标滚轮改变字体大小1.打开pycharm选择file2.选择setting4.选择keymap,然后再右边的输入框中输入increase进行增大字体4.鼠标选择后,点击添加鼠标快捷方式,然后设置鼠标滚轮往上增大字体。5.设置缩小字体࿰…...
【算法-动态规划】打家劫舍专题
文章目录 1.打家劫舍1.1一维数组1.2三变量法1.3双数组法 2.打家劫舍22.1双数组法2.2 三变量法 3.打家劫舍33.1动态规划3.2双变量法 4.删除相邻数字的最大分数4.1双状态数组4.2一维数组4.3三变量法 1.打家劫舍 198. 打家劫舍 - 力扣(LeetCode) 1.1一维数…...
关于技术管理者的一些思考
前 言 在软件开发领域,当一名资深工程师有机会成为一名技术管理者的时候,通常他/她的反应是什么?兴奋、担扰、无奈还是推托,具体是什么心情也许对结果并不重要,更加重要是在一刻,我们一定要问问我们内心的…...
Alpha-CLIP: A CLIP Model Focusing on Wherever You Want CVPR 2024
在原始的接受RGB三通道输入的CLIP模型的上额外增加了一个alpha通道。在千万量级的RGBA-region的图像文本对上进行训练后,Alpha-CLIP可以在保证CLIP原始感知能力的前提下,关注到任意指定区域。 GitHub - SunzeY/AlphaCLIP: [CVPR 2024] Alpha-CLIP: A CLI…...
Golang | Leetcode Golang题解之第495题提莫攻击
题目: 题解: func findPoisonedDuration(timeSeries []int, duration int) (ans int) {expired : 0for _, t : range timeSeries {if t > expired {ans duration} else {ans t duration - expired}expired t duration}return }...
04 go语言(golang) - 变量和赋值过程
变量 在Go语言中,变量的定义和初始化是编程的基础部分。Go提供了多种方式来声明和初始化变量,以适应不同的使用场景。 基本变量声明 使用var关键字: 使用var关键字可以在函数内部或外部声明变量。如果在函数外部声明,该变量为全…...
在软件开发中正确使用MySQL日期时间类型的深度解析
在日常软件开发场景中,时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志,到供应链系统的物流节点时间戳,时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库,其日期时间类型的…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
Spring Boot+Neo4j知识图谱实战:3步搭建智能关系网络!
一、引言 在数据驱动的背景下,知识图谱凭借其高效的信息组织能力,正逐步成为各行业应用的关键技术。本文聚焦 Spring Boot与Neo4j图数据库的技术结合,探讨知识图谱开发的实现细节,帮助读者掌握该技术栈在实际项目中的落地方法。 …...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
Linux 内存管理实战精讲:核心原理与面试常考点全解析
Linux 内存管理实战精讲:核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用,还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
【免费数据】2005-2019年我国272个地级市的旅游竞争力多指标数据(33个指标)
旅游业是一个城市的重要产业构成。旅游竞争力是一个城市竞争力的重要构成部分。一个城市的旅游竞争力反映了其在旅游市场竞争中的比较优势。 今日我们分享的是2005-2019年我国272个地级市的旅游竞争力多指标数据!该数据集源自2025年4月发表于《地理学报》的论文成果…...
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑
精益数据分析(98/126):电商转化率优化与网站性能的底层逻辑 在电子商务领域,转化率与网站性能是决定商业成败的核心指标。今天,我们将深入解析不同类型电商平台的转化率基准,探讨页面加载速度对用户行为的…...
