day-49 代码随想录算法训练营(19) 动态规划 part 10
121.买卖股票的最佳时机
思路一:贪心
- 不断更新最小买入值
- 不断更新当前值和最小买入值的差值最大值
思路二:动态规划(今天自己写出来了哈哈哈哈哈哈哈)
- 1.dp存储:dp[i][0] 表示当前持有 dp[i][1]表示当前不持有
- 2.状态转移方程(递推式)
- dp[i][0]=max ( dp [ i - 1 ] [ 0 ] , - prices [ i ] ) 之前就持有/当前买入
- dp[i][1]=max ( dp [ i - 1 ] [ 1 ] , dp [ i - 1 ] [ 0 ] + prices [ i ] ) 之前就没持有/当前卖出
- dp[i][0]=max ( dp [ i - 1 ] [ 0 ] , - prices [ i ] ) 之前就持有/当前买入
- 3.初始化:dp[0][0]=-prices[0] dp[0][1] =0
- 4.遍历顺序:1-n
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(2));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[n-1][1];//最后肯定不持有利润最大}
};
122.买卖股票的最佳时机||(拿捏)
思路一:贪心
- 只要有利润增长就卖出,最后一定获得最大利润
思路二:动态规划
1.dp存储:dp[i][0]为持有 dp[i][1]为不持有
2.状态转移方程(递推式):
- dp [ i ] [ 0 ] = max ( dp [ i - 1 ] [ 0 ] , dp [ i - 1 ] [ 1 ] - prices [ i ] ) 之前持有/现在买入(上一次不持有的金额 - 买入的金额)
- dp [ i ] [ 1 ] = max ( dp [ i - 1 ] [ 1 ] , dp [ i - 1 ] [ 0 ] + prices [ i ] ) 之前没持有/现在卖出(上一次持有的金额 + 卖出的金额)
3.初始化:dp[0][0]=-prices[0] dp[0][1]=0
4.遍历顺序:1-n
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(2));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[n-1][1];}
};
123.买卖股票的最佳时机|||
思路:动态规划(5个状态)
class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>>dp(n,vector<int>(5,0));dp[0][1]=-prices[0];dp[0][3]=-prices[0];for(int i=1;i<n;i++){dp[i][0]=dp[i-1][0]; //第一天不持有dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]); //第一天买入dp[i][2]=max(dp[i-1][2],dp[i-1][1]+prices[i]); //第一天卖出dp[i][3]=max(dp[i-1][3],dp[i-1][2]-prices[i]); //第二天买入dp[i][4]=max(dp[i-1][4],dp[i-1][3]+prices[i]);}return dp[n-1][4];}
};
相关文章:
day-49 代码随想录算法训练营(19) 动态规划 part 10
121.买卖股票的最佳时机 思路一:贪心 不断更新最小买入值不断更新当前值和最小买入值的差值最大值 思路二:动态规划(今天自己写出来了哈哈哈哈哈哈哈) 1.dp存储:dp[i][0] 表示当前持有 dp[i][1]表示当前不持有2.状…...
检查文件名是否含不可打印字符的C++代码源码
本篇文章属于《518抽奖软件开发日志》系列文章的一部分。 我在开发《518抽奖软件》(www.518cj.net)的时候,有时候需要检查输入的是否是合法的文件名,文件名是否含不可打印字符等。代码如下: //----------------------…...
学习笔记-正则表达式
https://www.runoob.com/regexp/regexp-tutorial.html 正则表达式re(Regular Expression)是一种文本模式,包括普通字符(例如,a 到 z 之间的字母)和特殊字符(称为"元字符"),可以用来描…...
Wireshark TS | 网络路径不一致传输丢包问题
问题背景 网络路径不一致,或者说是网络路径来回不一致,再专业点可以说是网络路径不对称,以上种种说法,做网络方向的工程师肯定会更清楚些,用简单的描述就是: A 与 B 通讯场景,C 和 D 代表中间…...
CMake高级用法实例分析(学习paddle官方的CMakeLists)
cmake基础学习教程 https://juejin.cn/post/6844903557183832078 官方完整CMakeLists cmake_minimum_required(VERSION 3.0) project(PaddleObjectDetector CXX C)option(WITH_MKL "Compile demo with MKL/OpenBlas support,defaultuseMKL." ON) o…...
数据采集: selenium 自动翻页接口调用时的验证码处理
写在前面 工作中遇到,简单整理理解不足小伙伴帮忙指正 对每个人而言,真正的职责只有一个:找到自我。然后在心中坚守其一生,全心全意,永不停息。所有其它的路都是不完整的,是人的逃避方式,是对大…...
IDEA安装翻译插件
IDEA安装翻译插件 File->Settings->Plugins 在Marketplace中,找到Translation,点击Install 更换翻译引擎 勾选自动翻译文档 翻译 鼠标右击->点击Translate...
DBeaver使用
一、导出表结构 二、导出数据CSV 导出数据时DBeaver并没有导出表结构,所以表结构需要额外保存; 导入数据CSV 导入数据时会因外键、字段长度导致失败;...
Nougat:一种用于科学文档OCR的Transformer 模型
随着人工智能领域的不断进步,其子领域,包括自然语言处理,自然语言生成,计算机视觉等,由于其广泛的用例而迅速获得了大量的普及。光学字符识别(OCR)是计算机视觉中一个成熟且被广泛研究的领域。它有许多用途,…...
redis八股1
参考Redis连环60问(八股文背诵版) - 知乎 (zhihu.com) 1.是什么 本质上是一个key-val数据库,把整个数据库加载到内存中操作,定期通过异步操作把数据flush到硬盘持久化。因为纯内存操作,所以性能很出色,每秒可以超过10…...
人工智能基础-趋势-架构
在过去的几周里,我花了一些时间来了解生成式人工智能基础设施的前景。在这篇文章中,我的目标是清晰概述关键组成部分、新兴趋势,并重点介绍推动创新的早期行业参与者。我将解释基础模型、计算、框架、计算、编排和矢量数据库、微调、标签、合…...
Date日期工具类(数据库日期区间问题)
文章目录 前言DateUtils日期工具类总结 前言 在我们日常开发过程中,当涉及到处理日期和时间的操作时,字符串与Date日期类往往要经过相互转换,且在SQL语句的动态查询中,往往月份的格式不正确,SQL语句执行的效果是不同的…...
为什么需要 TIME_WAIT 状态
还是用一下上一篇文章画的图 TCP 的 11 个状态,每一个状态都缺一不可,自然 TIME_WAIT 状态被赋予的意义也是相当重要,咱们直接结论先行 上文我们提到 tcp 中,主动关闭的一边会进入 TIME_WAIT 状态, 另外 Tcp 中的有 …...
Linux——(第七章)文件权限管理
目录 一、基本介绍 二、文件/目录的所有者 1.查看文件的所有者 2.修改文件所有者 三、文件/目录的所在组 1.修改文件/目录所在组 2.修改用户所在组 四、权限的基本介绍 五、rwx权限详解 1.rwx作用到文件 2.rwx作用到目录 六、修改权限 一、基本介绍 在Linux中&…...
Scala在大数据领域的崛起:当前趋势和未来前景
文章首发地址 Scala在大数据领域有着广阔的前景和现状。以下是一些关键点: Scala是一种具有强大静态类型系统的多范式编程语言,它结合了面向对象编程和函数式编程的特性。这使得Scala非常适合处理大数据,因为它能够处理并发、高吞吐量和复杂…...
前端面试经典题--页面布局
题目 假设高度已知,请写出三栏布局,其中左、右栏宽度各为300px,中间自适应。 五种解决方式代码 浮动解决方式 绝对定位解决方式 flexbox解决方式 表格布局 网格布局 源代码 <!DOCTYPE html> <html lang"en"> <…...
【webrtc】接收/发送的rtp包、编解码的VCM包、CopyOnWriteBuffer
收到的rtp包RtpPacketReceived 经过RtpDepacketizer 解析后变为ParsedPayloadRtpPacketReceived 分配内存,执行memcpy拷贝:然后把 RtpPacketReceived 给到OnRtpPacket 传递:uint8_t* media_payload = media_packet.AllocatePayload(rtx_payload.size());RTC...
Bash常见快捷键
生活在 Bash Shell 中,熟记以下快捷键,将极大的提高你的命令行操作效率。 编辑命令 Ctrl a :移到命令行首Ctrl e :移到命令行尾Ctrl f :按字符前移(右向)Ctrl b :按字符后移&a…...
软件验收测试
1. 服务流程 验收测试 2. 服务内容 测试过程中,根据合同要求制定测试方案,验证工程项目是否满足用户需求,软件质量特性是否达到系统的要求。 3. 周期 10-15个工作日 4. 报告用途 可作为进行地方、省级、国家、部委项目的验收࿰…...
Java 与零拷贝
零拷贝是由操作系统实现的,使用 Java 中的零拷贝抽象类库在支持零拷贝的操作系统上运行才会实现零拷贝,如果在不支持零拷贝的操作系统上运行,并不会提供零拷贝的功能。 简述内核态和用户态 Linux 的体系结构分为内核态(内核空间…...
渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止
<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet: https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...
《基于Apache Flink的流处理》笔记
思维导图 1-3 章 4-7章 8-11 章 参考资料 源码: https://github.com/streaming-with-flink 博客 https://flink.apache.org/bloghttps://www.ververica.com/blog 聚会及会议 https://flink-forward.orghttps://www.meetup.com/topics/apache-flink https://n…...
Spring数据访问模块设计
前面我们已经完成了IoC和web模块的设计,聪明的码友立马就知道了,该到数据访问模块了,要不就这俩玩个6啊,查库势在必行,至此,它来了。 一、核心设计理念 1、痛点在哪 应用离不开数据(数据库、No…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
通过MicroSip配置自己的freeswitch服务器进行调试记录
之前用docker安装的freeswitch的,启动是正常的, 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...
保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...
《Offer来了:Java面试核心知识点精讲》大纲
文章目录 一、《Offer来了:Java面试核心知识点精讲》的典型大纲框架Java基础并发编程JVM原理数据库与缓存分布式架构系统设计二、《Offer来了:Java面试核心知识点精讲(原理篇)》技术文章大纲核心主题:Java基础原理与面试高频考点Java虚拟机(JVM)原理Java并发编程原理Jav…...
如何把工业通信协议转换成http websocket
1.现状 工业通信协议多数工作在边缘设备上,比如:PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发,当设备上用的是modbus从站时,采集设备数据需要开发modbus主站;当设备上用的是西门子PN协议时…...
