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 的体系结构分为内核态(内核空间…...
内存分配函数malloc kmalloc vmalloc
内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...
UDP(Echoserver)
网络命令 Ping 命令 检测网络是否连通 使用方法: ping -c 次数 网址ping -c 3 www.baidu.comnetstat 命令 netstat 是一个用来查看网络状态的重要工具. 语法:netstat [选项] 功能:查看网络状态 常用选项: n 拒绝显示别名&#…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
基于 TAPD 进行项目管理
起因 自己写了个小工具,仓库用的Github。之前在用markdown进行需求管理,现在随着功能的增加,感觉有点难以管理了,所以用TAPD这个工具进行需求、Bug管理。 操作流程 注册 TAPD,需要提供一个企业名新建一个项目&#…...
安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
