代码随想录算法训练营第五十天 | 123.买卖股票的最佳时机III 188. 买卖股票的最佳时机 IV
1. 买卖股票的最佳时机 III
123. 买卖股票的最佳时机 III - 力扣(LeetCode)
* 定义 5 种状态:
* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
class Solution {public int maxProfit(int[] prices) {int length =prices.length;int[][] dp = new int[length][5];dp[0][0] = 0;dp[0][1] = -prices[0]; // 第一次持仓dp[0][2] = 0;dp[0][3] = -prices[0]; // 第二次持仓dp[0][4] = 0;for(int i = 1; i < length; i++){dp[i][0] = dp[i-1][0];dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] + prices[i]);dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] - prices[i]);dp[i][4] = Math.max(dp[i-1][4], dp[i-1][3] + prices[i]);}return dp[length-1][4];}
}
滚动数组(当前天直接用前一天)
不操作的状态可以省略,因为一定为0
class Solution {public int maxProfit(int[] prices) {int length =prices.length;int[] dp = new int[4];dp[0] = -prices[0]; // 第一次持仓dp[1] = 0;dp[2] = -prices[0]; // 第二次持仓dp[3] = 0;for(int i = 1; i < length; i++){dp[0] = Math.max(dp[0], 0 - prices[i]);dp[1] = Math.max(dp[1], dp[0] + prices[i]);dp[2] = Math.max(dp[2], dp[1] - prices[i]);dp[3] = Math.max(dp[3], dp[2] + prices[i]);}return dp[3];}
}
2. 买卖股票的最佳时机 IV
188. 买卖股票的最佳时机 IV - 力扣(LeetCode)
和 III 一个道理,只不过状态数变成了 2*k 个
注意遍历状态的时候, 第一个状态要单独拿出来(因为前面没有状态了),或者从第二个状态开始遍历
class Solution {public int maxProfit(int k, int[] prices) {int[] dp = new int[2*k];for(int j = 0; j < k; j++){dp[2*j] = -prices[0];}for(int i = 1; i < prices.length; i++){for(int j = 0; j < k; j++){if(j == 0){dp[0] = Math.max(dp[0], 0 - prices[i]); // 第1次持仓dp[1] = Math.max(dp[1], dp[0] + prices[i]); // 第1次不持仓}else{dp[2*j] = Math.max(dp[2*j], dp[2*j-1] - prices[i]); // 持仓dp[2*j + 1] = Math.max(dp[2*j + 1], dp[2*j] + prices[i]); // 不持仓}}}return dp[2*k-1];}
}
相关文章:
代码随想录算法训练营第五十天 | 123.买卖股票的最佳时机III 188. 买卖股票的最佳时机 IV
1. 买卖股票的最佳时机 III 123. 买卖股票的最佳时机 III - 力扣(LeetCode) * 定义 5 种状态: * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出 class Solution {public int maxProfit(int[] prices) {int length prices.l…...
详解window.print(),实现长列表打印分页
相信大家平时做项目时,打印需求很常见,但想把打印做好,还是要花点时间的。特别是长列表要分页的情况。 我们知道浏览原生 API window.print() 可以用于印当前窗口(window.document)视图内容。调用此方法会产生一个打印…...
使用Chatgpt编写的PHP数据库pdo操作类(增删改查)
摘要 将PDO封装成PHP类进行调用有很多好处,包括: 1、封装性和抽象性: 通过将PDO封装到一个类中,您可以将数据库操作逻辑与应用程序的其他部分分离开来,提高了代码的组织性和可维护性。这样,您只需在一个地…...
蓝桥杯2023年第十四届省赛真题-异或和之和--题解
目录 蓝桥杯2023年第十四届省赛真题-异或和之和 题目描述 输入格式 输出格式 样例输入 样例输出 【代码实现】 大家觉得写得可以的话,可以加入QQ群907575059. 蓝桥杯2023年第十四届省赛真题-异或和之和 时间限制: 3s 内存限制: 320MB 提交: 241 解决: 66 …...
Linux 常用命令学习笔记
Linux 常用命令学习笔记 文件操作 ls:列出当前目录下的文件和文件夹。 ls -l:以长格式显示文件和文件夹的详细信息。ls -a:显示所有文件,包括隐藏文件。 cd [目录]:切换到指定目录。pwd:显示当前工作目录…...
支撑电动汽车规模化,特来电智能化升级群充产品
9月26日,中国领先的充电网生态运营商特来电重磅发布智能群充4.0产品,标志着特来电群充产品体系进一步升级,充电行业迎来更高质量、更高性能的设备与系统,充电网基础设施将更好地支撑大规模电动汽车的发展。 群充技术路线引领充电…...
本次CTF·泰山杯网络安全的基础知识部分
简记23年九月参加的泰山杯网络安全的部分基础知识的题目,随时补充 1. 国密算法哪个属于公钥? SM2 a. 国产密码算法(国密算法)是指国家密码局认定的国产商用密码算法,目前主要使用公开的SM2、SM3、SM4三类算法&#x…...
通信协议:Uart的Verilog实现(下)
4、UART接收器 UART接收器负责接收串行比特流,去除起始位和停止位,并以并行格式将数据保存到与主机数据总线相连的寄存器里。接收器无法获得发送时钟,因此尽管数据以标准比特率到达,但数据未必与接收主机内的时钟同步。同步问题可…...
嵌入式MCU都有什么高级用法?
嵌入式MCU都有什么高级用法? 您举的几个例子,确实是MCU外设的一些高端玩法。只是不知道您是否想过,既然这些机制是被 人设计出来的,那它就是种标准用法。从微控制器的发展历程来看,许多硬件机制都是有了实际 需求后才…...
热启动和冷启动是什么,区别
app冷启动: 当应用启动时,后台没有该应用的进程,这时系统会重新创建一个新的进程分配给该应用, 这个启动方式就叫做冷启动(后台不存在该应用进程)。冷启动因为系统会重新创建一个新的进程分配给它ÿ…...
每日一题 494目标和(0-1背包)(灵神笔记)
0-1背包模版 有n个物品,它们有各自的体积和价值,现有给定容量的背包,如何让背包里装入的物品具有最大的价值总和? 当前操作?枚举第i个物品选还是不选,不选容量不变,选容量减少 子问题ÿ…...
软件测试工作步骤详情
软件测试步骤按照研发阶段一般分为5个部分:单元测试、集成测试、确认测试、系统测试、验收测试,下面将不同阶段需要的一些工作内容做一下梳理希望可以帮助到大家。 一、单元测试的内容:(白盒为主,黑盒为辅)…...
java项目之列车票务信息管理系统(ssm源码+文档)
项目简介 列车票务信息管理系统实现了以下功能: 管理员:个人中心、用户管理、车票信息管理、购票指南管理、管理员管理、论坛管理、我的收藏管理、系统管理、订单管理。前台首页:首页、车票信息、购票指南、我的收藏管理、论坛信息、我的、…...
【Pytorch笔记】3.数学运算
深度之眼官方账号 - 01-03-mp4-张量操作与线性回归 torch.add() 功能:逐元素计算inputalphaother。 torch.add(input,alpha1,other,outNone)input:tensor; alpha:other的系数,是个实数; other࿱…...
MeterSphere 监控方案
前言:在部署MeterSphere之后,很多时候需要看下MeterSphere服务的监控信息,虽然有监控告警脚本,但还不是太直观,所以就结合 PrometheusExporterGrafana 部署一套完整的MeterSphere监控方案。 首先我们先罗列一下需要监控…...
elementui-plus+ts+axios使用el-upload组件自定义上传
1.前言: 使用element ui有很多便捷之处,但是由于是封装的组件和自己写还是有些许的不一样,这里主要解决几个问题。 1. 如何获取子组件实例 2. 如何自定义上传方法 2.两个问题: ⛺️ 获取子组件实例 实际上vue一般通过ref获取子组…...
【STM32单片机】u8g2智能风扇设计
文章目录 一、功能简介二、软件设计三、实验现象联系作者 一、功能简介 本项目使用STM32F103C8T6单片机控制器,使用按键、IIC OLED模块、DS18B20温度传感器、直流电机、红外遥控等。 主要功能: 初始化后进入温度显示界面,系统初始状态为手动…...
Java中的IO流的缓冲流
不爱生姜不吃醋⭐️ 如果本文有什么错误的话欢迎在评论区中指正 与其明天开始,不如现在行动! 文章目录 🌴IO流体系结构🌴缓冲流1.提高效率的原理2.缓冲流的类型3.字符缓冲流两个特有方法 🌴总结 🌴IO流体系…...
7、SpringBoot_高级配置
一、配置高级 1.临时属性设置 1.1引出问题 如果目标电脑上8080端口已经使用,再次使用该端口会出现端口占用问题 解决方式 重新更换配置文件修改端口打包通过临时属性配置新端口更换配置文件 1.2添加临时属性配置 通过临时属性修改8080端口 java -jar 项目.jar…...
cocos2dx查看版本号的方法
打开文件:项目根目录\frameworks\cocos2d-x\docs\RELEASE_NOTES.md 知道引擎版本号的意义: 1.面试中经常被问到(面试官想知道你会不会查版本号,你会查也不一定会去看,如果你去看了说明你是一个有心人,或者想深入研究下…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
Ubuntu系统下交叉编译openssl
一、参考资料 OpenSSL&&libcurl库的交叉编译 - hesetone - 博客园 二、准备工作 1. 编译环境 宿主机:Ubuntu 20.04.6 LTSHost:ARM32位交叉编译器:arm-linux-gnueabihf-gcc-11.1.0 2. 设置交叉编译工具链 在交叉编译之前&#x…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
FFmpeg:Windows系统小白安装及其使用
一、安装 1.访问官网 Download FFmpeg 2.点击版本目录 3.选择版本点击安装 注意这里选择的是【release buids】,注意左上角标题 例如我安装在目录 F:\FFmpeg 4.解压 5.添加环境变量 把你解压后的bin目录(即exe所在文件夹)加入系统变量…...
