代码随想录算法训练营day47
题目:188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费
参考链接:代码随想录
188.买卖股票的最佳时机IV
思路:本题和上题的最多两次买卖相比,改成了最多k次,使用类似思路,需要设计1+2k个状态,第一个不设置也可以。dp五部曲:dp数组,dp[i][0-2k],dp[i][0]表示无操作,dp[i][1]表示第一次持有的最大现金,dp[i][2]表示第一次不持有…dp[i][2k-1]表示第k次持有,dp[i][2k]表示第k次不持有;递推公式,类似上题,第i天第j次持有时,考虑第i-1天持有或不持有,dp[i][2j-1]=max(dp[i-1][2j-1],dp[i-1][2j-2]-prices[i]),第i天第j次不持有时,dp[i][2j]=max(dp[i-1][2j],dp[i-1][2j-1]+prices[i]);初始化,首先全部初始化为0,dp[i][0]始终为0,然后dp[0][2j-1]初始化为-prices[0],dp[0][2j]初始化为0,类似上题;遍历顺序,顺序遍历;举例略。时间复杂度O(nk)。
class Solution {
public:int maxProfit(int k, vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));for(int j=0;j<k;j++){//初始化dp[0][2*j+1]=-prices[0];}for(int i=1;i<prices.size();i++){for(int j=1;j<=k;j++){//第j次持有和第j次不持有dp[i][2*j-1]=max(dp[i-1][2*j-1],dp[i-1][2*j-2]-prices[i]);dp[i][2*j]=max(dp[i-1][2*j],dp[i-1][2*j-1]+prices[i]);}}return dp[prices.size()-1][2*k];}
};
注意cpp中数字和字母之间的乘号不能省略!否则报错。
309.最佳买卖股票时机含冷冻期
思路:本题可以多次买卖,加入了一天冷冻期,卖出后第二天不能买,需要仔细分析状态,有四个状态,状态一为持有股票,然后对于不持有股票的情况,要分开讨论,状态二为保持卖出股票(两天前就卖掉了已经度过冷冻期,或者一直就没操作),即可以随时买入股票,度过了冷冻期,状态三为当天卖出股票,状态四为冷冻期,即前一天卖出股票。如图所示:

和前几题相比,本题增加了一个今天卖出股票的状态,之前都没有,因为冷冻期之前一天只能是当天卖出的状态,需要和普通的不持有股票状态区分开来。dp五部曲:dp数组:dp[i][0-4]分别表示持有股票、保持卖出股票、当天卖出股票、冷冻期的最大现金;递推公式:dp[i][0],持有股票,前一天有三种情况,首先是本来就持有的dp[i-1][0],然后是冷冻状态或者保持卖出状态下买入,dp[i-1][1]-prices[i],dp[i-1][3]-prices[i],取max,dp[i][1]卖出状态,前一天要么本来就是保持卖出,dp[i-1][1],或者冷冻状态,dp[i-1][3],取max,注意不是当天卖的,故不需要+prices[i],dp[i][2]当天卖出,前一天必定是持有,dp[i][2]=dp[i-1][0]+prices[i],dp[i][3]冷冻期,前一天必定是卖出股票,dp[i][3]=dp[i-1][2];初始化,首先全部初始化为0,dp[0][0]=-prices[i],dp[0][1]直接思考想不出设置为什么合适,所以直接根据递推公式算,经过几次递推后必定为0,dp[0][2]和dp[0][3]也为0;遍历顺序,顺序遍历;举例略。时间复杂度O(n)。最后返回值为状态1,2,3取max。
class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(4,0));dp[0][0]=-prices[0];for(int i=1;i<prices.size();i++){dp[i][0]=max(dp[i-1][0],max(dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]));dp[i][1]=max(dp[i-1][1],dp[i-1][3]);dp[i][2]=dp[i-1][0]+prices[i];dp[i][3]=dp[i-1][2];}return max(dp[prices.size()-1][1],max(dp[prices.size()-1][2],dp[prices.size()-1][3]));}
};
714.买卖股票的最佳时机含手续费
思路:本题又是无限次交易,只不过添加了手续费,因此比较容易,只需要在交易的时候计算现金的时候减去手续费就OK。dp五部曲:dp数组,dp[i][0]表示持有股票最大现金,dp[i][1]表示不持有股票最大现金;递推公式,dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]-fee),对于交易手续费,我们在买的时候扣除就行了,dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);初始化,dp[0][0]=-prices[i]-fee,其他都初始化为0;遍历顺序,顺序遍历;举例略。时间复杂度O(n)。手续费在卖的时候扣也可以。
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<vector<int>> dp(prices.size(),vector<int>{0,0});dp[0][0]=-prices[0]-fee;for(int i=1;i<prices.size();i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]-fee);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[prices.size()-1][1];}
};
相关文章:
代码随想录算法训练营day47
题目:188.买卖股票的最佳时机IV、309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费 参考链接:代码随想录 188.买卖股票的最佳时机IV 思路:本题和上题的最多两次买卖相比,改成了最多k次,使用类似思路&…...
【Android面试八股文】Kotlin内置标准函数apply的原理是什么?
文章目录 一、原理解析二、 示例代码2.1 具体示例应用场景2.2 为什么使用 `apply`?apply 是 Kotlin 标准库中的一个高阶函数,它的作用是在对象上执行一个代码块,并返回这个对象本身。其原理涉及到函数类型和接收者对象的结合使用。 一、原理解析 函数类型与接收者对象的结合…...
RegionClip环境安装踩坑指南
RegionClip环境安装 RegionClip环境安装)问题1问题2问题3问题4问题5 RegionClip环境安装) 特别强调,不要单独去安装detectron2,会出现model.clip不存在的错误,通过python -m pip install -e RegionCLIP就可以问题1 问题:torch-c…...
MySQL数据类型、运算符以及常用函数
MySQL数据类型 MySQL数据类型定义了数据的大小范围,因此使用时选择合适的类型,不仅会降低表占用的磁盘空间, 间接减少了磁盘I/O的次数,提高了表的访问效率,而且索引的效率也和数据的类型息息相关。 数值类型 浮点类型…...
算法设计与分析:动态规划法求扔鸡蛋问题 C++
目录 一、实验目的 二、问题描述 三、实验要求 四、算法思想和实验结果 1、动态规划法原理: 2、解决方法: 2.1 方法一:常规动态规划 2.1.1 算法思想: 2.1.2 时间复杂度分析 2.1.3 时间效率分析 2.2 方法二:动态规划加…...
Java项目:基于SSM框架实现的电子竞技管理平台【ssm+B/S架构+源码+数据库+毕业论文】
一、项目简介 本项目是一套基于SSM框架实现的电子竞技管理平台 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,eclipse或者idea 确保可以运行! 该系统功能完善、界面美观、操作简单、功能…...
Scala入门介绍
Scala 是一种强大的多范式编程语言,旨在融合面向对象编程和函数式编程的特性。它运行在 Java 虚拟机(JVM)上,因此可以无缝地与 Java 库进行交互。以下是对 Scala 的入门介绍,并附带了一些基本代码示例。 环境设置 首先…...
品牌策划背后的秘密:我为何对此工作情有独钟?
你是否曾有过一个梦想,一份热爱,让你毫不犹豫地投身于一个行业? 我就是这样一个对品牌策划充满热情的人。 从选择职业到现在,我一直在广告行业里“混迹”,一路走来,也见证了许多对品牌策划一知半解的求职…...
超越招聘技术人才目标的最佳技术招聘统计数据
研究发现,难以找到的人才比以往任何时候都更难找到:根据新人才委员会招聘调查报告:2024年难以找到的人才的战略和战略,60%的受访者表示,熟练人才的招聘时间比一年前长。调查进一步揭示了以下关于招聘技术的关键事实&am…...
cocos creator 调试插件
适用 Cocos Creator 3.4 版本,cocos creator 使用google浏览器调试时,我们可以把事实运行的节点以节点树的形式显示在浏览器上,支持运行时动态调整位置等、、、 将下载的preview-template插件解压后放在工程根目录下,然后重新运行…...
Clickhouse监控_监控的指标以及Grafana配置Clickhouse指标异常时触发报警
使用PrometheusGrafana来监控Clickhouse服务和性能指标 Clickhouse监控指标的官方文档https://clickhouse.com/docs/zh/operations/monitoring 建议使用PrometheusGrafana组合监控Clickhouse服务和性能指标,数据流向:Prometheus的clickhouse_exporter组件…...
动手学深度学习(Pytorch版)代码实践 -卷积神经网络-27含并行连结的网络GoogLeNet
27含并行连结的网络GoogLeNet import torch from torch import nn from torch.nn import functional as F import liliPytorch as lp import matplotlib.pyplot as pltclass Inception(nn.Module):# c1--c4是每条路径的输出通道数def __init__(self, in_channels, c1, c2, c3, …...
fastadmin多语言切换设置
fastadmin版本:1.4.0.20230711 以简体,繁体,英文为例 一,在application\config.php 里开启多语言 // 是否开启多语言lang_switch_on > true, // 允许的语言列表allow_lang_list > [zh-cn, en,zh-tw], 二…...
如何清理docker build的缓存
在使用 Docker 构建镜像时,Docker 会利用构建缓存来加速后续的构建过程。如果某一层及其所有上层未发生变化,Docker 就会重用这一层的缓存。虽然这可以显著提升构建速度,但有时你可能希望强制 Docker 忽略缓存,以确保从头开始重新…...
OceanBase v4.2 特性解析:如何用分页保序功能解决MySQL模式分页查询不稳定
导言 在MySQL业务迁移OceanBase过程中,经常遇到的一个问题是分页查询结果的不稳定性,这通常需要数据库DBA介入绑定执行计划。下面简单举个例子,以便大家更好地理解为什么有的分页查询,在原来的MySQL数据库下运行没有问题…...
RK3588/算能/Nvidia智能盒子:加速山西铝业智能化转型,保障矿业皮带传输安全稳定运行
近年来,各类矿山事故频发,暴露出传统矿业各环节的诸多问题。随着全国重点产煤省份相继出台相关政策文件,矿业智能化建设进程加快。皮带传输系统升级是矿业智能化的一个重要环节,同时也是降本增效的一个重点方向。 △各省份智能矿山…...
2024.6.24 IDEA中文乱码问题(服务器 控制台 TOMcat)实测已解决
1.问题产生原因: 1.文件编码不一致:如果文件的编码方式与IDEA设置的编码方式不一致,就会产生乱码。确保文件和IDEA使用相同的编码,通常是UTF-8。2.IDEA设置问题:检查IDEA的全局编码设置和项目编码设置是否正确。3.终端…...
桌面编辑器ONLYOFFICE 功能多样性快来试试吧!
目录 ONLYOFFICE 桌面编辑器 8.1 ONLYOFFICE介绍 主要功能和特点 使用场景 1.PDF编辑器 2.幻灯片版式 3.编辑,审阅和查看模式 4.隐藏连接到云版块 5.RTL语言支持和本地化选项 6.媒体播放器 7、其他新功能 8.下载 总结 ONLYOFFICE 桌面编辑器 8.1 官网地…...
三维渲染中的散光圆
三维渲染中的散光圆 散光圆(Circle of Confusion,CoC)是三维渲染和摄影中的一个重要概念,尤其在景深(Depth of Field,DoF)效果的生成中起着关键作用。它描述了在成像过程中,焦点前后…...
Vue3 + Ant-Design 中 a-date-picke 实现选择切换年份 没有鼠标光标,输入框内自带‘年’
效果图: 效果图 <a-date-picker ref"datePicker" v-model:value"year" picker"year" value-format"YYYY年" format"YYYY年" :bordered"false" :allowClear"false" inputReadOnly change&…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
自然语言处理——Transformer
自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效,它能挖掘数据中的时序信息以及语义信息,但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN,但是…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
libfmt: 现代C++的格式化工具库介绍与酷炫功能
libfmt: 现代C的格式化工具库介绍与酷炫功能 libfmt 是一个开源的C格式化库,提供了高效、安全的文本格式化功能,是C20中引入的std::format的基础实现。它比传统的printf和iostream更安全、更灵活、性能更好。 基本介绍 主要特点 类型安全:…...
LLaMA-Factory 微调 Qwen2-VL 进行人脸情感识别(二)
在上一篇文章中,我们详细介绍了如何使用LLaMA-Factory框架对Qwen2-VL大模型进行微调,以实现人脸情感识别的功能。本篇文章将聚焦于微调完成后,如何调用这个模型进行人脸情感识别的具体代码实现,包括详细的步骤和注释。 模型调用步骤 环境准备:确保安装了必要的Python库。…...
