html中音乐网站怎么做/百度广告公司
文章目录
- 前言
- 一、买卖股票的最佳时机III(力扣123)
- 二、买卖股票的最佳时机IV(力扣188)
- 三、最佳买卖股票时机含冷冻期(力扣309)
- 四、买卖股票的最佳时机含手续费(力扣714)
- 股票买卖问题总结
前言
1、买卖股票的最佳时机III
2、买卖股票的最佳时机IV
3、最佳买卖股票时机含冷冻期
4、买卖股票的最佳时机含手续费
一、买卖股票的最佳时机III(力扣123)
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
8888
分析:
与之前的区别在于最多可以买卖两次
动规五部曲
1、dp[]数组以及下标含义
dp[i][0]:不操作
dp[i][1]:第一次持有
dp[i][2]:第一次不持有
dp[i][3]:第二次持有
dp[i][4]:第二次不持有
2、递推公式
dp[i][0] = dp[i-1][0]
dp[i][1] = Math.max(dp[i-1][1],-price[i])
dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+price[i])
dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-price[i])
dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+price[i])
3、初始化
dp[0][0] = 0;
dp[0][1] = -price[0];
dp[0][2] = 0;
dp[0][3] = -price[0];
dp[0][4] = 0;
4、遍历顺序
从前向后遍历,因为dp[i],依靠dp[i - 1]的数值。
二维dp数组
class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.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<prices.length;i++){dp[i][1] = Math.max(dp[i-1][1],-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[prices.length-1][4];}
}
优化版:(滚动数组):
class Solution {public int maxProfit(int[] prices) {int[] dp = new int[5];dp[0] = 0;dp[1] = -prices[0];dp[2] = 0;dp[3] = -prices[0];dp[4] = 0;for(int i=1;i<prices.length;i++){dp[1] = Math.max(dp[1],-prices[i]);dp[2] = Math.max(dp[2],dp[1]+prices[i]);dp[3] = Math.max(dp[3],dp[2]-prices[i]);dp[4] = Math.max(dp[4],dp[3]+prices[i]);}return dp[4];}
}
二、买卖股票的最佳时机IV(力扣188)
给定一个整数数组 prices ,它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
分析:
与之前的区别在于最多可以买卖k次
根据上一题所表现出来的规律:
1、dp[]数组以及下标含义
dp[i][0]:不操作
dp[i][1]:第一次持有
dp[i][2]:第一次不持有
dp[i][3]:第二次持有
dp[i][4]:第二次不持有
……
当有k次买卖时,奇数表示买入,偶数表示卖出。
初始化
for(int j=0;j<2*k+1;j++){if(j%2==1){dp[0][j] = -prices[0];}
}
递推公式
dp[i][0] = dp[i-1][0]
dp[i][1] = Math.max(dp[i-1][1],-price[i])
dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]+price[i])
dp[i][3] = Math.max(dp[i-1][3],dp[i-1][2]-price[i])
dp[i][4] = Math.max(dp[i-1][4],dp[i-1][3]+price[i])
for(int i = 1; i<prices.length; i++){for(int j=1; j<2*k+1;j=j+2){dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);dp[i][j+1] = Math.max(dp[i-1][j+1],dp[i-1][j]+prices[i]);}
}
class Solution {public int maxProfit(int k, int[] prices) {int[][] dp = new int[prices.length][2*k+1];for(int j=1;j<2*k+1;j++){if(j%2==1) dp[0][j] = -prices[0];}for(int i=1;i<prices.length;i++){for(int j=0;j<2*k-1;j=j+2){dp[i][j+1] = Math.max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2] = Math.max(dp[i-1][j+2],dp[i-1][j+1]+prices[i]);}}return dp[prices.length-1][2*k];}
}
三、最佳买卖股票时机含冷冻期(力扣309)
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):
你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
动规五部曲:
1、dp[]数组以及下标含义
dp[i][0]:持有股票的状态
dp[i][1]:保持卖出股票的状态
dp[i][2]:卖出股票状态
dp[i][3]:冷冻期
为什么要把 不持有股票状态拆分为两个部分【保持卖出股票的状态、卖出股票状态】,因为有冷冻期。必须前一天是卖出股票的状态,那么下一天才能是冷冻期
2、递推公式
持有股票状态:
1、i-1天就持有:dp[i][0] = dp[i-1][0];
2、冷冻期之后买入股票:dp[i][0] = dp[i-1][3] - prices[i];
3、冷冻期之后一直没有操作,一直都是保持卖出股票状态,直到第i天买入:dp[i][0] = dp[i-1][1] - prices[i];
因此:dp[i][0] = Math.max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i][0] = dp[i-1][1] - prices[i])
保持卖出股票状态:
1、前一天就是保持卖出股票的状态:dp[i][1] = dp[i-1][1];
2、前一天是冷冻期,dp[i][1] = dp[i-1][3]
因此:dp[i][1] = Math.max(dp[i-1][1] , dp[i-1][3])
卖出股票状态:
1、前i-1天持有股票状态,第i天卖出股票.dp[i][2] = dp[i-1][0]+prices[i];
因此:dp[i][2]=dp[i-1][0]+prices[i];
冷冻期状态
1、前一天卖出股票状态,第i天就是冷冻期 dp[i][3] = dp[i-1][2]
因此:dp[i][3] = dp[i-1][2];
3、初始化
dp[0][0] = -prices[0];
dp[0][1] 在dp[i][0] = Math.max(dp[i-1][0], dp[i-1][3] - prices[i], dp[i][0] = dp[i-1][1] - prices[i]) 这个状态下会用到,假设i=1带入之后:
dp[1][0] = max(dp[0][0],dp[0][3]-prices[1], dp[0][1]-prices[1]);
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
4、遍历顺序
从前向后遍历,因为dp[i],依靠dp[i - 1]的数值。
class Solution {public int maxProfit(int[] prices) {int[][] dp = new int[prices.length][4];//初始化dp[0][0] = -prices[0];dp[0][1] = 0;dp[0][2] = 0;dp[0][3] = 0;//遍历for(int i=1;i<prices.length;i++){//持有股票的状态dp[i][0] = Math.max(Math.max(dp[i-1][0],dp[i-1][1]-prices[i]),dp[i-1][3]-prices[i]);//保持卖出股票的状态dp[i][1] = Math.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 Math.max(Math.max(dp[prices.length-1][3],dp[prices.length-1][2]),dp[prices.length-1][1]);}
}
四、买卖股票的最佳时机含手续费(力扣714)
给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。
注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。
在之前有用贪心算法进行求解:
贪心算法求解
分析:
买卖股票的最佳时机II 可以进行多次买卖,但多了手续费
dp[i][0]:表示第i天持有股票所得现金。
dp[i][1]:表示第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]);
class Solution {public int maxProfit(int[] prices, int fee) {int[][] dp = new int[prices.length][2];dp[0][0] = -prices[0]-fee;for(int i=1;i<prices.length;i++){dp[i][0] = Math.max(dp[i-1][0],dp[i-1][1]-prices[i]-fee);dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[prices.length-1][1];}
}
优化后(一维滚动数组)
class Solution {public int maxProfit(int[] prices, int fee) {int[] dp = new int[2];dp[0] = -prices[0]-fee;for(int i=1;i<prices.length;i++){dp[0] = Math.max(dp[0],dp[1]-prices[i]-fee);dp[1] = Math.max(dp[1],dp[0]+prices[i]);}return dp[1];}
}
股票买卖问题总结
买卖股票的最佳时机(力扣121) 只能买卖一次
dp[i][0]:持有股票的状态
dp[i][1]:不持有股票的状态
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[i][0] = max(dp[i-1][0], -prices[i])
dp[i][1] = max(dp[i-1][1] , dp[i-1][0]+prices[i])
买卖股票的最佳时机||(力扣122)可以买卖多次
dp[i][0]:持有股票的状态
dp[i][1]:不持有股票的状态
dp[0][0] = -prices[0];
dp[0][1] = 0;
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])
细微变化在于持有股票状态的递推过程
买卖股票的最佳时机|||(力扣123)最多买卖2次
dp[i][0] 不操作
dp[i][1]:第一次持有股票状态
dp[i][2]:第一次不持有股票状态
dp[i][3]:第二次持有股票状态
dp[i][4]:第二次不持有股票状态
初始化
dp[0][0]= 0
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[i][0] = dp[i-1][0]
dp[i][1] = max(dp[i-1][1],-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])
买卖股票的最佳时机IV(力扣188) 最多买卖k次
dp[i][0] 不操作
dp[i][1]:第一次持有股票状态
dp[i][2]:第一次不持有股票状态
dp[i][3]:第二次持有股票状态
dp[i][4]:第二次不持有股票状态
……
0 ----- 2*k
奇数是持有股票状态
偶数是卖出股票状态
初始化时:
if(j%2==1) dp[0][j] = -prices[0];
奇数时:dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] - prices[i])
偶数时:dp[i][j+1] = max(dp[i-1][j+1], dp[i-1][j] +prices[i])
最佳买卖股票时机含冷冻期(力扣309) 买卖多次,卖出后有一天是冷冻期
dp[i][0]:持有股票的状态
dp[i][1]:保持卖出股票的状态
dp[i][2]:卖出股票的状态
dp[i][3]:冷冻期
初始化
dp[0][0] = -prices[0];
dp[i][0] = max(dp[i-1][0], 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]
买卖股票的最佳时机含手续费(力扣714)买卖多次,每次都有手续费
dp[i][0]:持有股票的状态
dp[i][1]:不持有股票的状态
dp[0][0] = -prices[0]-fee;
dp[0][1] = 0;
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])
细微变化在于多减去手续费
相关文章:

day47【代码随想录】动态规划之买卖股票的最佳时机III、买卖股票的最佳时机IV、最佳买卖股票时机含冷冻期、买卖股票的最佳时机含手续费
文章目录前言一、买卖股票的最佳时机III(力扣123)二、买卖股票的最佳时机IV(力扣188)三、最佳买卖股票时机含冷冻期(力扣309)四、买卖股票的最佳时机含手续费(力扣714)股票买卖问题总…...

网络数据包接收流程
1. 网络数据包接收流程简述 典型的以太网卡网络包接收流程如下: 1.网络包通过物理介质传到接收端的phy芯片; 2.phy芯片通过RGMII协议传到MAC芯片rx queue fifo中; 3.MAC芯片通过专用DMA将网络包搬运到网卡驱动程序预先分配好的rx ringbuffer中…...

CSAPP学习笔记——虚拟内存(二)
案例研究 Intel Core i7 该处理底层的Haswell微体系结构允许64位的虚拟和物理地址空间,而现在的Core i7实现支持48位(256TB)虚拟地址空间和52位(4PB)物理地址空间,这对目前来说已经完全够用了。ÿ…...

面试sql
创建表 create table Student ( Sno varchar(20) primary key,Sname varchar(20) UNIQUE,Ssex varchar(2),Sbirthday date,class varchar(20) )create table Course ( Cno varchar(20) primary key,Cname varchar(20) UNIQUE,Tno varchar(20) )create table Score ( …...

Python编程自动化办公案例(2)
作者简介:一名在校计算机学生、每天分享Python的学习经验、和学习笔记。 座右铭:低头赶路,敬事如仪 个人主页:网络豆的主页 目录 前言 一.前期代码 二.实现批量读取 1.os库 2.实现思路 (1&#…...

Vulnhub 渗透练习(七)—— FRISTILEAKS: 1.3
环境搭建 下载链接 virtualbox 打开靶机设置为 host-only,攻击机同样。 具体可点此处 信息收集 开了个 80 端口。 用的是 apache 2.2.15 ,这个版本有个解析漏洞。 目录 根据首页的图片猜测 /fristi/ 目录(不过我没想到 -_-&#x…...

阶段二10_面向对象高级_分类分包思想和案例环境搭建
一.分类思想 1.分类思想概念: 分工协作,专人干专事 2.信息管理系统分类[案例] Student 类-------------------->标准学生类,封装键盘录入的学生信息(id , name , age , birthday) StudentDao 类-----------------&…...

关于打印工具print-js的使用
https://www.jianshu.com/p/f6f09dd9f7db第一步 安装组件//安装print-js npm install print-js --save //删除print-js npm uninstall print-js //安装固定版本 npm install print-js版本号 --save // 全局安装 npm install print-js --save -g第二步 引入组件安装成功后&#…...

Doxygen使用
文章目录简介Doxygen的安装Doxygen的配置生成配置文件常用配置Doxygen注释头文件注释:函数的注释:Doxygen文档生成reference简介 Doxygen 是一个流行的用于生产代码文档的工具,关于它的介绍可以参考官网:https://www.doxygen.nl/index.html。 我使用Dox…...

MySQL数据库调优————表结构设计优化
三范式 第一范式 字段具有原子性,即数据库表的每一个字段都是不可分割的原子数据项,不能是集合、数组、记录等非原子数据项当实体中的每个属性有多个值时,必须拆分为不同的属性 第二范式 满足第一范式的基础上,要求每一行数据…...

set对象和map对象
1 Set对象 介绍: Set数据结构类似数组,但所有成员的值唯一。 Set本身为一个构造函数,用来生成 Set数据结构,使用 add方法来添加新成员。 let a new Set(); [1,2,2,1,3,4,5,4,5].forEach(x>a.add(x)); for(let k of a){ console.log(k…...

stream()流的使用
文章目录引入流流的操作中间操作终端操作流的使用谓词筛选筛选各异的元素流的切片截断流跳过元素映射流的扁平化查找和匹配归约元素求和、最大值和最小值数值流构建流由值构建流由数组创建流引入流 java api提供的一种利用声明式的方式处理数据集合的一个东西,可以…...

C++学习笔记-常量
在程序执行过程中,其值不能改变的量称为常量(Constant)。普通常量的类型是根据数据的书写形式来决定的。如 100 是整型常量,0.5 是实型常量,‘q’ 是字符型常量,“qianfeng” 是字符串常量。 常量是固定值,在程序执行期…...

JavaScript系列之实现继承的几种方式
文章の目录一、借助父构造函数继承属性1、实现方式2、优点3、缺点二、原型链继承1、实现方式2、优点3、缺点三、组合继承四、ES6继承的实现方式参考写在最后一、借助父构造函数继承属性 1、实现方式 先定义一个父构造函数(this指向为window);再定义一个子构造函数…...

java面试准备
1.自我介绍: 2.基础 : 1.集合 : java容器中分为collection 和map两大类 collection 分为list集合(有序且重复的),set集合(无序,不可重复) list集合分为arrayList集合 : 查询快,增删慢,它是基于数组结构的,对数据的增删是在数组的尾部进行添加或删除的,其效率相对于LinkedList…...

kafka-6-python单线程操作kafka
使用Python操作Kafka:KafkaProducer、KafkaConsumer Python kafka-python API的帮助文档 1 kafka tools连接 (1)/usr/local/kafka_2.13-3.4.0/config/server.properties listeners PLAINTEXT://myubuntu:9092 advertised.listenersPLAINTEXT://192.168.1.8:2909…...

【Spring教程】1.Spring概述
1、概述 1.1、Spring是什么? Spring 是一款主流的 Java EE 轻量级开源框架 ,Spring 由“Spring 之父”Rod Johnson 提出并创立,其目的是用于简化 Java 企业级应用的开发难度和开发周期。Spring的用途不仅限于服务器端的开发。从简单性、可测…...

设计模式-代理模式
控制和管理访问 玩过扮白脸,扮黑脸的游戏吗?你是一个白脸,提供很好且很友善的服务,但是你不希望每个人都叫你做事,所以找了黑脸控制对你的访问。这就是代理要做的:控制和管理对象。 监视器编码 需求&…...

DPDK — MALLOC(librte_malloc,Memory Manager,内存管理组件)
目录 文章目录 目录MALLOC(librte_malloc,Memory Manager,内存管理组件)rte_malloc() 接口malloc_heap 结构体malloc_elem 结构体内存初始化流程内存申请流程内存释放流程MALLOC(librte_malloc,Memory Manager,内存管理组件) MALLOC 库基于 hugetlbfs 内核文件系统来实…...

【Java开发】Spring 12 :Spring IOC控制反转和依赖注入(解决单接口多实现类调用)
IOC 是 Inversion of Control 的简写,译为“控制反转”,Spring 通过 IOC 容器来管理所有 Java 对象的实例化和初始化,控制对象与对象之间的依赖关系。我们将由 IOC 容器管理的 Java 对象称为 Spring Bean,它与使用关键字 new 创建…...

【C++学习】基础语法(三)
众所周知C语言是面向过程的编程语言,关注的是过程;解决问题前,需要分析求解的步骤,然后编辑函数逐步解决问题。C是基于面向对象的,关注的是对象,将一件事拆分成不同的对象,不同对象间交互解决问…...

k8s自动化安装脚本(kubeadm-1.23.7)
文章目录介绍软件架构版本介绍更新内容2023-02-192023-02-152023-02-142023-02-102022-10-202022-08-06准备部署包操作步骤环境准备结构备注解压部署包修改host文件脚本使用方式初始化环境验证ansible配置安装k8s集群登录master的节点添加node节点master节点状态检查组件安装安…...

面试题记录
Set与Map的区别 map是键值对,set是值的集合。键,值可以是任何类型map可以通过get获取,map不能。都能通过迭代器进行for…of遍历set的值是唯一的,可以做数组去重,map,没有格式限制,可以存储数据…...

链式前向星介绍以及原理
1 链式前向星 1.1 简介 链式前向星可用于存储图,本质上是一个静态链表。 一般来说,存储图常见的两种方式为: 邻接矩阵邻接表 邻接表的实现一般使用数组实现,而链式前向星就是使用链表实现的邻接表。 1.2 出处 出处可参考此…...

jenkins 安装 -适用于在线安装 后续写个离线安装的
jenkins安装1.下载jenkins2.安装启动3.附件卸载jdk的命令4.配置jenkins一、在jenkins配置文件中配置jdk环境变量二、修改jenkins默认的操作用户1.下载jenkins jenkins官网下载 https://www.jenkins.io/ 点击下载 我是centos系统所以选择centos,点击后按着官方提供…...

【C++】再谈vscode界面调试C++程序(linux) - 知识点目录
再谈vscode界面调试C程序(linux) 配套文档:vscode界面调试C程序(linux) 命令解释 g -g ../main.cpp 编译main.cpp文件; -g:生成调试信息。编译器会在可执行文件中嵌入符号表和源代码文件名&…...

蚂蚁感冒---第五届蓝桥杯真题
目录 题目链接 题目描述 分析: 代码: y总综合 666 题目链接 1211. 蚂蚁感冒 - AcWing题库 题目描述 分析: y总真牛逼,掉头等价于穿过,以第一个点为分界点,分别判断 代码: (自…...

常见排序算法--Java实现
常见排序算法--Java实现插入排序直接插入排序折半插入排序希尔排序交换排序冒泡排序快速排序选择排序直接选择排序堆排序归并排序基数排序各种排序方法比较在网上找了些排序算法的资料。此篇笔记本人总结比较,简单注释,觉得比较好理解,且相对…...

算法笔记(九)—— 暴力递归
暴力递归(尝试) 1. 将问题转化为规模缩小了的同类问题子问题 2. 有明确的不需要的继续递归的条件 3. 有当得到子问题结果之后的决策过程 4. 不记录每一个子问题的解 Question:经典汉诺塔问题 1. 理解清楚,基础三个圆盘的移动…...

Flask框架学习记录
Flask项目简要 项目大致结构 flaskDemo1 ├─static ├─templates └─app.py app.py # 从flask这个包中导入Flask类 from flask import Flask# 使用Flask类创建一个app对象 # __name__:代表当前app.py这个模块 # 1.以后出现bug,可以帮助快速定位 # 2.对于寻找…...