代码随想录算法训练营Day 50 || 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费
309.最佳买卖股票时机含冷冻期
力扣题目链接
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
- 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
- 输入: [1,2,3,0,2]
- 输出: 3
- 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
这个问题的特别之处在于引入了一个“冷冻期”的概念,即在卖出股票的次日,不能进行股票的买入。
解题思路:
动态规划是解决这个问题的一个有效方法。考虑到冷冻期的存在,我们需要维护三个状态:
- 持有股票(hold): 当天结束时持有股票的最大利润。
- 不持有股票,处于冷冻期(freeze): 当天结束时,处于冷冻期的最大利润。
- 不持有股票,不处于冷冻期(no_hold): 当天结束时,既不持有股票也不处于冷冻期的最大利润。
状态转移方程:
-
持有股票(hold):
- 如果前一天也持有股票,则继续持有;
- 如果前一天不持有股票且不处于冷冻期,则今天买入。
hold[i] = max(hold[i-1], no_hold[i-1] - prices[i]) -
不持有股票,处于冷冻期(freeze):
- 只有在前一天卖出股票的情况下,今天才会进入冷冻期。
freeze[i] = hold[i-1] + prices[i] -
不持有股票,不处于冷冻期(no_hold):
- 如果前一天不持有股票,可以继续保持这个状态;
- 如果前一天处于冷冻期,今天将不再处于冷冻期。
no_hold[i] = max(no_hold[i-1], freeze[i-1])
class Solution:def maxProfit(self, prices: List[int]) -> int:if not prices:return 0n = len(prices)hold, freeze, no_hold = [0] * n, [0] * n, [0] * nhold[0] = -prices[0]for i in range(1, n):hold[i] = max(hold[i-1], no_hold[i-1] - prices[i])freeze[i] = hold[i-1] + prices[i]no_hold[i] = max(no_hold[i-1], freeze[i-1])return max(freeze[n-1], no_hold[n-1])
714.买卖股票的最佳时机含手续费
力扣题目链接
给定一个整数数组 prices,其中第 i 个元素代表了第 i 天的股票价格 ;非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
示例 1:
- 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
- 输出: 8
解释: 能够达到的最大利润:
- 在此处买入 prices[0] = 1
- 在此处卖出 prices[3] = 8
- 在此处买入 prices[4] = 4
- 在此处卖出 prices[5] = 9
- 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
注意:
- 0 < prices.length <= 50000.
- 0 < prices[i] < 50000.
- 0 <= fee < 50000.
解题思路:
-
状态定义:
hold[i]:表示第i天结束时持有股票的最大利润。cash[i]:表示第i天结束时不持有股票的最大利润。
-
状态转移:
hold[i]=max(hold[i-1], cash[i-1] - prices[i]):表示第i天持有股票的最大利润是由前一天持有股票和前一天不持有但在今天买入股票中的较大者决定的。cash[i]=max(cash[i-1], hold[i-1] + prices[i] - fee):表示第i天不持有股票的最大利润是由前一天不持有股票和前一天持有但在今天卖出股票(扣除手续费)中的较大者决定的。
-
初始化:
hold[0]=-prices[0]:第一天买入股票的情况。cash[0]=0:第一天不持有股票的情况。
-
计算最终结果:
- 最后返回
cash[n-1],即在最后一天不持有股票的最大利润。
- 最后返回
class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:n = len(prices)if n == 0:return 0hold = [0] * ncash = [0] * nhold[0] = -prices[0]for i in range(1, n):hold[i] = max(hold[i - 1], cash[i - 1] - prices[i])cash[i] = max(cash[i - 1], hold[i - 1] + prices[i] - fee)return cash[n - 1]
相关文章:
代码随想录算法训练营Day 50 || 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费
309.最佳买卖股票时机含冷冻期 力扣题目链接 给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票): 你不能同时…...
【C语言】【数据结构】【环形链表判断是否带环并返回进环节点】有数学推导加图解
1.判断是否带环: 用快慢指针 slow指针一次走一步,fast指针一次走两步 当两个指针相遇时,链表带环;两个指针不能相遇时,当fast走到倒数第一个节点或为空时,跳出循环返回空指针。 那么slow指针一次走一步&a…...
漏洞扫描-nuclei-poc编写
0x00 nuclei Nuclei是一款基于YAML语法模板的开发的定制化快速漏洞扫描器。它使用Go语言开发,具有很强的可配置性、可扩展性和易用性。 提供TCP、DNS、HTTP、FILE 等各类协议的扫描,通过强大且灵活的模板,可以使用Nuclei模拟各种安全检查。 …...
SpringBoot 自动配置
Condition 自定义条件: 定义条件类:自定义类实现Condition接口,重写 matches 方法,在 matches 方法中进行逻辑判断,返回boolean值 。 matches 方法两个参数: context:上下文对象,可…...
IP-guard WebServer 远程命令执行漏洞
IP-guard WebServer 远程命令执行漏洞 免责声明漏洞描述漏洞影响漏洞危害网络测绘Fofa: app"ip-guard" 漏洞复现1. 构造poc2. 访问文件3. 执行命令 免责声明 仅用于技术交流,目的是向相关安全人员展示漏洞利用方式,以便更好地提高网络安全意识和技术水平。 任何人不…...
每次重启完IDEA,application.properties文件里的中文变成?
出现这种情况,在IDEA打开Settings-->Editor-->File Encodings 然后,你需要将问号改为你需要的汉字。 重启IDEA,再次查看你的.properties文件就会发现再没有变成问号了...
【Truffle】四、通过Ganache部署连接
目录 一、下载安装 Ganache: 二、在本地部署truffle 三、配置ganache连接truffle 四、交易发送 除了用Truffle Develop,还可以选择使用 Ganache, 这是一个桌面应用,他同样会创建一个个人模拟的区块链。 对于刚接触以太坊的同学来说&#x…...
React 其他常用Hooks
1. useImperativeHandle 在react中父组件可以通过forwardRef将ref转发到子组件;子组件拿到父组件创建的ref,绑定到自己的某个元素; forwardRef的做法本身没有什么问题,但是我们是将子组件的DOM直接暴露给了父组件,某下…...
将 ONLYOFFICE 文档编辑器与 С# 群件平台集成
在本文中,我们会向您展示 ONLYOFFICE 文档编辑器与其自有的协作平台集成。 ONLYOFFICE 是一款开源办公套件,包括文本文档、电子表格和演示文稿编辑器。这款套件支持用户通过文档编辑组件扩展第三方 web 应用的功能,可直接在应用的界面中使用。…...
使用电脑时提示msvcp140.dll丢失的5个解决方法
“计算机中msvcp140.dll丢失的5个解决方法”。在我们日常使用电脑的过程中,有时会遇到一些错误提示,其中之一就是“msvcp140.dll丢失”。那么,什么是msvcp140.dll呢?它的作用是什么?丢失它会对电脑产生什么影响呢&…...
VR全景如何应用在房产行业,VR看房有哪些优势
导语: 在如今的数字时代,虚拟现实(VR)技术的迅猛发展为许多行业带来了福音,特别是在房产楼盘行业中。通过利用VR全景技术,开发商和销售人员可以为客户提供沉浸式的楼盘浏览体验,从而带来诸多优…...
11月份 四川汽车托运报价已经上线
中国人不骗中国人!! 国庆小长假的高峰期过后 放假综合症的你还没痊愈吧 今天给大家整理了9条最新线路 广州到四川的托运单价便宜到💥 核算下来不过几毛钱💰 相比起自驾的漫长和疲惫🚗 托运不得不说真的很省事 - 赠送保险 很多客户第一次运车 …...
springcloud图书借阅管理系统源码
开发说明: jdk1.8,mysql5.7,nodejs,idea,nodejs,vscode springcloud springboot mybatis vue elementui 功能介绍: 用户端: 登录注册 首页显示搜索图书,轮播图&…...
主题模型LDA教程:LDA主题数选取:困惑度preplexing
文章目录 LDA主题数困惑度1.概率分布的困惑度2.概率模型的困惑度3.每个分词的困惑度 LDA主题数 LDA作为一种无监督学习方法,类似于k-means聚类算法,需要给定超参数主题数K,但如何评价主题数的优劣并无定论,一般采取人为干预、主题…...
Docker快速入门
Docker是一个用来快速构建、运行和管理应用的工具。 Docker技术能够避免对服务器环境的依赖,减少复杂的部署流程,有了Docker以后,可以实现一键部署,项目的部署如丝般顺滑,大大减少了运维工作量。 即使你对Linux不熟…...
36 Gateway网关 快速入门
3.Gateway服务网关 Spring Cloud Gateway 是 Spring Cloud 的一个全新项目,该项目是基于 Spring 5.0,Spring Boot 2.0 和 Project Reactor 等响应式编程和事件流技术开发的网关,它旨在为微服务架构提供一种简单有效的统一的 API 路由管理方式…...
MyBatis的知识点和简单用法
MyBatis 是一个半ORM(对象关系映射)框架,它内部封装了JDBC,开发时只需要关注SQL语句本身,不需要花费精力去处理加载驱动、创建连接、创建statement等繁杂的过程。程序员直接编写原生态sql,可以严格控制sql执…...
KITTI数据集(.bin数据)转换为点云数据(.pcd文件)
目录 cmake代码 代码 cmake代码 cmake_minimum_required(VERSION 3.17) project(TEST2)set(CMAKE_CXX_STANDARD 14)# Find PCL find_package(PCL 1.8 REQUIRED)# If PCL was found, add its include directories to the project if(PCL_FOUND)include_directories(${PCL_INC…...
【电路笔记】-节点电压分析和网状电流分析
节点电压分析和网状电流分析 文章目录 节点电压分析和网状电流分析1、节点电压分析1.1 概述1.2 示例 2、网格电流分析2.1 概述2.2 示例 3、总结 正如我们在上一篇介绍电路分析基本定律的文章中所看到的,基尔霍夫电路定律 (KCL) 是计算任何电路中未知电压和电流的强大…...
jenkins通知
构建失败邮件通知 配置自己的邮箱 配置邮件服务,密码是授权码 添加构建后操作 扩展 配置流水线 添加扩展 钉钉通知 Jenkins安装钉钉插件 钉钉添加机器人 加签 https://oapi.dingtalk.com/robot/send?access_token98437f84ffb6cd64fa2d7698ef44191d49a11…...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
ubuntu搭建nfs服务centos挂载访问
在Ubuntu上设置NFS服务器 在Ubuntu上,你可以使用apt包管理器来安装NFS服务器。打开终端并运行: sudo apt update sudo apt install nfs-kernel-server创建共享目录 创建一个目录用于共享,例如/shared: sudo mkdir /shared sud…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...
屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!
5月28日,中天合创屋面分布式光伏发电项目顺利并网发电,该项目位于内蒙古自治区鄂尔多斯市乌审旗,项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站,总装机容量为9.96MWp。 项目投运后,每年可节约标煤3670…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
HBuilderX安装(uni-app和小程序开发)
下载HBuilderX 访问官方网站:https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本: Windows版(推荐下载标准版) Windows系统安装步骤 运行安装程序: 双击下载的.exe安装文件 如果出现安全提示&…...
如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...
优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台
🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...
