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

代码随想录算法训练营Day 50 || 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费

309.最佳买卖股票时机含冷冻期

力扣题目链接

给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):

  • 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
  • 卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

  • 输入: [1,2,3,0,2]
  • 输出: 3
  • 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

这个问题的特别之处在于引入了一个“冷冻期”的概念,即在卖出股票的次日,不能进行股票的买入。

解题思路:

动态规划是解决这个问题的一个有效方法。考虑到冷冻期的存在,我们需要维护三个状态:

  1. 持有股票(hold): 当天结束时持有股票的最大利润。
  2. 不持有股票,处于冷冻期(freeze): 当天结束时,处于冷冻期的最大利润。
  3. 不持有股票,不处于冷冻期(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.

解题思路:

  1. 状态定义:

    • hold[i]:表示第 i 天结束时持有股票的最大利润。
    • cash[i]:表示第 i 天结束时不持有股票的最大利润。
  2. 状态转移:

    • 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 天不持有股票的最大利润是由前一天不持有股票和前一天持有但在今天卖出股票(扣除手续费)中的较大者决定的。
  3. 初始化:

    • hold[0] = -prices[0]:第一天买入股票的情况。
    • cash[0] = 0:第一天不持有股票的情况。
  4. 计算最终结果:

    • 最后返回 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.最佳买卖股票时机含冷冻期 力扣题目链接 给定一个整数数组&#xff0c;其中第 i 个元素代表了第 i 天的股票价格 。 设计一个算法计算出最大利润。在满足以下约束条件下&#xff0c;你可以尽可能地完成更多的交易&#xff08;多次买卖一支股票&#xff09;: 你不能同时…...

【C语言】【数据结构】【环形链表判断是否带环并返回进环节点】有数学推导加图解

1.判断是否带环&#xff1a; 用快慢指针 slow指针一次走一步&#xff0c;fast指针一次走两步 当两个指针相遇时&#xff0c;链表带环&#xff1b;两个指针不能相遇时&#xff0c;当fast走到倒数第一个节点或为空时&#xff0c;跳出循环返回空指针。 那么slow指针一次走一步&a…...

漏洞扫描-nuclei-poc编写

0x00 nuclei Nuclei是一款基于YAML语法模板的开发的定制化快速漏洞扫描器。它使用Go语言开发&#xff0c;具有很强的可配置性、可扩展性和易用性。 提供TCP、DNS、HTTP、FILE 等各类协议的扫描&#xff0c;通过强大且灵活的模板&#xff0c;可以使用Nuclei模拟各种安全检查。 …...

SpringBoot 自动配置

Condition 自定义条件&#xff1a; 定义条件类&#xff1a;自定义类实现Condition接口&#xff0c;重写 matches 方法&#xff0c;在 matches 方法中进行逻辑判断&#xff0c;返回boolean值 。 matches 方法两个参数&#xff1a; context&#xff1a;上下文对象&#xff0c;可…...

IP-guard WebServer 远程命令执行漏洞

IP-guard WebServer 远程命令执行漏洞 免责声明漏洞描述漏洞影响漏洞危害网络测绘Fofa: app"ip-guard" 漏洞复现1. 构造poc2. 访问文件3. 执行命令 免责声明 仅用于技术交流,目的是向相关安全人员展示漏洞利用方式,以便更好地提高网络安全意识和技术水平。 任何人不…...

每次重启完IDEA,application.properties文件里的中文变成?

出现这种情况&#xff0c;在IDEA打开Settings-->Editor-->File Encodings 然后&#xff0c;你需要将问号改为你需要的汉字。 重启IDEA&#xff0c;再次查看你的.properties文件就会发现再没有变成问号了...

【Truffle】四、通过Ganache部署连接

目录 一、下载安装 Ganache&#xff1a; 二、在本地部署truffle 三、配置ganache连接truffle 四、交易发送 除了用Truffle Develop&#xff0c;还可以选择使用 Ganache, 这是一个桌面应用&#xff0c;他同样会创建一个个人模拟的区块链。 对于刚接触以太坊的同学来说&#x…...

React 其他常用Hooks

1. useImperativeHandle 在react中父组件可以通过forwardRef将ref转发到子组件&#xff1b;子组件拿到父组件创建的ref&#xff0c;绑定到自己的某个元素&#xff1b; forwardRef的做法本身没有什么问题&#xff0c;但是我们是将子组件的DOM直接暴露给了父组件&#xff0c;某下…...

将 ONLYOFFICE 文档编辑器与 С# 群件平台集成

在本文中&#xff0c;我们会向您展示 ONLYOFFICE 文档编辑器与其自有的协作平台集成。 ONLYOFFICE 是一款开源办公套件&#xff0c;包括文本文档、电子表格和演示文稿编辑器。这款套件支持用户通过文档编辑组件扩展第三方 web 应用的功能&#xff0c;可直接在应用的界面中使用。…...

使用电脑时提示msvcp140.dll丢失的5个解决方法

“计算机中msvcp140.dll丢失的5个解决方法”。在我们日常使用电脑的过程中&#xff0c;有时会遇到一些错误提示&#xff0c;其中之一就是“msvcp140.dll丢失”。那么&#xff0c;什么是msvcp140.dll呢&#xff1f;它的作用是什么&#xff1f;丢失它会对电脑产生什么影响呢&…...

VR全景如何应用在房产行业,VR看房有哪些优势

导语&#xff1a; 在如今的数字时代&#xff0c;虚拟现实&#xff08;VR&#xff09;技术的迅猛发展为许多行业带来了福音&#xff0c;特别是在房产楼盘行业中。通过利用VR全景技术&#xff0c;开发商和销售人员可以为客户提供沉浸式的楼盘浏览体验&#xff0c;从而带来诸多优…...

11月份 四川汽车托运报价已经上线

中国人不骗中国人!! 国庆小长假的高峰期过后 放假综合症的你还没痊愈吧 今天给大家整理了9条最新线路 广州到四川的托运单价便宜到&#x1f4a5; 核算下来不过几毛钱&#x1f4b0; 相比起自驾的漫长和疲惫&#x1f697; 托运不得不说真的很省事 - 赠送保险 很多客户第一次运车 …...

springcloud图书借阅管理系统源码

开发说明&#xff1a; jdk1.8&#xff0c;mysql5.7&#xff0c;nodejs&#xff0c;idea&#xff0c;nodejs&#xff0c;vscode springcloud springboot mybatis vue elementui 功能介绍&#xff1a; 用户端&#xff1a; 登录注册 首页显示搜索图书&#xff0c;轮播图&…...

主题模型LDA教程:LDA主题数选取:困惑度preplexing

文章目录 LDA主题数困惑度1.概率分布的困惑度2.概率模型的困惑度3.每个分词的困惑度 LDA主题数 LDA作为一种无监督学习方法&#xff0c;类似于k-means聚类算法&#xff0c;需要给定超参数主题数K&#xff0c;但如何评价主题数的优劣并无定论&#xff0c;一般采取人为干预、主题…...

Docker快速入门

Docker是一个用来快速构建、运行和管理应用的工具。 Docker技术能够避免对服务器环境的依赖&#xff0c;减少复杂的部署流程&#xff0c;有了Docker以后&#xff0c;可以实现一键部署&#xff0c;项目的部署如丝般顺滑&#xff0c;大大减少了运维工作量。 即使你对Linux不熟…...

36 Gateway网关 快速入门

3.Gateway服务网关 Spring Cloud Gateway 是 Spring Cloud 的一个全新项目&#xff0c;该项目是基于 Spring 5.0&#xff0c;Spring Boot 2.0 和 Project Reactor 等响应式编程和事件流技术开发的网关&#xff0c;它旨在为微服务架构提供一种简单有效的统一的 API 路由管理方式…...

MyBatis的知识点和简单用法

MyBatis 是一个半ORM&#xff08;对象关系映射&#xff09;框架&#xff0c;它内部封装了JDBC&#xff0c;开发时只需要关注SQL语句本身&#xff0c;不需要花费精力去处理加载驱动、创建连接、创建statement等繁杂的过程。程序员直接编写原生态sql&#xff0c;可以严格控制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、总结 正如我们在上一篇介绍电路分析基本定律的文章中所看到的&#xff0c;基尔霍夫电路定律 (KCL) 是计算任何电路中未知电压和电流的强大…...

jenkins通知

构建失败邮件通知 配置自己的邮箱 配置邮件服务&#xff0c;密码是授权码 添加构建后操作 扩展 配置流水线 添加扩展 钉钉通知 Jenkins安装钉钉插件 钉钉添加机器人 加签 https://oapi.dingtalk.com/robot/send?access_token98437f84ffb6cd64fa2d7698ef44191d49a11…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略

本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装&#xff1b;只需暴露 19530&#xff08;gRPC&#xff09;与 9091&#xff08;HTTP/WebUI&#xff09;两个端口&#xff0c;即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践

前言&#xff1a;本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中&#xff0c;跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南&#xff0c;你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案&#xff0c;并结合内网…...

基于单片机的宠物屋智能系统设计与实现(论文+源码)

本设计基于单片机的宠物屋智能系统核心是实现对宠物生活环境及状态的智能管理。系统以单片机为中枢&#xff0c;连接红外测温传感器&#xff0c;可实时精准捕捉宠物体温变化&#xff0c;以便及时发现健康异常&#xff1b;水位检测传感器时刻监测饮用水余量&#xff0c;防止宠物…...

高端性能封装正在突破性能壁垒,其芯片集成技术助力人工智能革命。

2024 年&#xff0c;高端封装市场规模为 80 亿美元&#xff0c;预计到 2030 年将超过 280 亿美元&#xff0c;2024-2030 年复合年增长率为 23%。 细分到各个终端市场&#xff0c;最大的高端性能封装市场是“电信和基础设施”&#xff0c;2024 年该市场创造了超过 67% 的收入。…...

Java中栈的多种实现类详解

Java中栈的多种实现类详解&#xff1a;Stack、LinkedList与ArrayDeque全方位对比 前言一、Stack类——Java最早的栈实现1.1 Stack类简介1.2 常用方法1.3 优缺点分析 二、LinkedList类——灵活的双端链表2.1 LinkedList类简介2.2 常用方法2.3 优缺点分析 三、ArrayDeque类——高…...

【动态规划】B4336 [中山市赛 2023] 永别|普及+

B4336 [中山市赛 2023] 永别 题目描述 你做了一个梦&#xff0c;梦里有一个字符串&#xff0c;这个字符串无论正着读还是倒着读都是一样的&#xff0c;例如&#xff1a; a b c b a \tt abcba abcba 就符合这个条件。 但是你醒来时不记得梦中的字符串是什么&#xff0c;只记得…...