当前位置: 首页 > news >正文

LeetCode——动态规划(五)

刷题顺序及思路来源于代码随想录,网站地址:https://programmercarl.com 

目录

121. 买卖股票的最佳时机 - 力扣(LeetCode)

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

123. 买卖股票的最佳时机 III - 力扣(LeetCode)


121. 买卖股票的最佳时机 - 力扣(LeetCode)

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 

输入:[7,1,5,3,6,4]
输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。

/*** @author light* @Description 买股票的最佳时机。** (思路:分为持有和不持有状态:(持有不代表当天买入,持有是一种状态,同理不持有也是* 1.持有:以前就持有或者当天才持有* 2.不持有:以前就不持有或者当天卖出不持有* @create 2023-10-13 13:48*/
public class MaxProfitTest {public int maxProfit(int[] prices) {//dp[i][0]:第i天不持有股票,所获得的最大利润//dp[i][1]:第i天持有股票,所获得的最大利润int[][] dp=new int[prices.length][2];dp[0][0]=0;dp[0][1]=-prices[0];for (int i =1; i <prices.length; i++) {dp[i][0]= Math.max(dp[i-1][0],dp[i-1][1]+prices[i]); //不持有:以前不持有/现在卖出dp[i][1]= Math.max(dp[i-1][1],-prices[i]);  //持有:以前持有/现在买入}return dp[prices.length-1][0];}
}

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

输入:prices = [7,1,5,3,6,4]
输出:7
解释:在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。总利润为 4 + 3 = 7 。

/*** @author light* @Description 买股票的最佳时机II** (两种情况:分为持有和不持有* 1.持有:以前就持有/以前不持有现在持有* 2.不持有:以前就不持有/以前持有现在不持有* @create 2023-10-13 15:11*/
public class MaxProfit2Test {public int maxProfit(int[] prices) {//dp[i][0]:第i天持有股票,所获得的最大利润//dp[i][1]:第i天不持有股票,所获得的最大利润int[][] dp=new int[prices.length][2];dp[0][0]=-prices[0];dp[0][1]=0;for (int i = 0; i < prices.length; i++) {//持有:区别于买股票的最佳时机那道题,注意这里题干是每一天,意思是持有情况可能在前一天有利润情况下持有本次股票dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]= Math.max(dp[i-1][1],dp[i-1][0]+prices[i]); //不持有}return dp[prices.length-1][1];}
}

123. 买卖股票的最佳时机 III - 力扣(LeetCode)

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

输入:prices = [3,3,5,0,0,3,1,4]
输出:6
解释:在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
/*** @author light* @Description 买股票的最佳时机III** (思路:最多能买两只股票则有共有5个状态* 0.没有操作* 1.第一次持有股票--第一次一直持有/之前不持有,现在持有* 2.第一次不持有股票--第一次一直不持有/之前持有,现在不持有* 3.第二次持有股票--第二次一直持有/第一次后不持有,现在持有* 4.第二次不持有股票--第一次后一直不持有/第一次后不持有,现在持有* @create 2023-10-13 16:11*/
public class MaxProfit3Test {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][0]-prices[i],dp[i-1][1]);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];}}

相关文章:

LeetCode——动态规划(五)

刷题顺序及思路来源于代码随想录&#xff0c;网站地址&#xff1a;https://programmercarl.com 目录 121. 买卖股票的最佳时机 - 力扣&#xff08;LeetCode&#xff09; 122. 买卖股票的最佳时机 II - 力扣&#xff08;LeetCode&#xff09; 123. 买卖股票的最佳时机 III …...

与HTTP相关的各种概念

网络世界 网络世界中最重要的一个名词就是互联网&#xff08;Internet&#xff09;,它以TCP/IP协议族为基础&#xff0c;构建成了一望无际的信息传输网络。而我们通常所说的“上网”&#xff0c;主要就是访问互联网的一个子集——万维网&#xff08;World Wide Web&#xff09…...

CentOS 7 编译安装Boost

1、前提条件 linux平台/CentOS 7 下要编译安装Boost除gcc和gcc-c之外&#xff0c;还需要两个开发库&#xff1a;bzip2-devel 和python-devel &#xff0c;因此在安装前应该先保证这两个库已经安装。 安装指令: yum install bzip2 bzip2-devel bzip2-libs python-devel Cent…...

vue图表制作

Vue.js是一个非常流行的JavaScript框架&#xff0c;可以用于开发交互式Web应用程序。Vue.js的优点之一是它的灵活性和可扩展性。因此&#xff0c;可以使用Vue.js与许多其他库和框架集成&#xff0c;包括图表库。 下面是使用Vue.js制作图表的一些步骤&#xff1a; 1.选择一个适…...

使用 GitHub Action 自动更新 Sealos 集群的应用镜像

在 IT 领域&#xff0c;自动化无疑已成为提高工作效率和减少人为错误的关键。Sealos 作为一个强大的云操作系统&#xff0c;已经为许多企业和开发者提供了稳定可靠的服务。与此同时&#xff0c;随着技术不断发展&#xff0c;集成更多的功能和服务变得尤为重要。考虑到这一点&am…...

windows频繁更新问题解决方案

解决方案&#xff1a;将更新策略增加到无穷大 1.windowsr 输入regedit 2.找到&#xff1a;HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\WindowsUpdate\UX\Settings 3.右键新建DWORD32 4.命名&#xff1a;FlightSettingsMaxPauseDays 5.双击&#xff1a;数值数据改为4321 基数&#…...

day05-前后端项目上传到gitee、后端多方式登录接口、发送短信功能、发送短信封装、短信验证码接口、短信登录接口

1 前后端项目上传到gitee 2 后端多方式登录接口 2.1 序列化类 2.2 视图类 2.3 路由 3 发送短信功能 4 发送短信封装 4.0 目录结构 4.1 settings.py 4.2 sms.py 5 短信验证码接口 6 短信登录接口 6.1 视图类 6.2 序列化类 1 前后端项目上传到gitee # 我们看到好多开源项目…...

046:mapboxGL加载天地图路网图+标记(wmts方式)

第046个 点击查看专栏目录 本示例的目的是介绍演示如何在vue+mapbox中加载天地图路网图+标记(wmts方式)。瓦片中的url地址引用的是天地图的wmts的形式。 直接复制下面的 vue+mapbox源代码,操作2分钟即可运行实现效果 文章目录 示例效果配置方式示例源代码(共99行)相关AP…...

【ICer的脚本练习】tcl语法熟悉和工具tcl的实例

系列的目录说明请见:ICer的脚本练习专栏介绍与全流程目录_尼德兰的喵的博客-CSDN博客 前言 TCL(Tool Command Language)是一种简单但功能强大的脚本语言,它经常用于自动化任务、测试和快速原型开发。你看这个名字就能知道,这个语言最主要的作用就是用来操作工具,尤其我们…...

uniapp+vue3+ts+uview-plus搭建项目步骤

创建项目 使用Vue3/Vite版&#xff0c;创建以 typescript 开发的工程 下载仓库 DCloud/uni-preset-vue - Gitee.com node版本&#xff1a;v16.18.0 npm版本&#xff1a; v8.19.2 依赖下载 解压之后&#xff0c;在vscode打开 通过终端运行 npm 命令下载依赖&#xff1a;npm ins…...

在PHP中,可以使用不同的加密算法(如MD5、SHA1、SHA256)结合RSA算法进行公钥加密和私钥解密。

下面是使用这三种算法进行加密和解密的示例代码&#xff1a; // 生成RSA密钥对 $keyPair openssl_pkey_new(array(private_key_bits > 2048,private_key_type > OPENSSL_KEYTYPE_RSA, ));// 获取私钥和公钥 openssl_pkey_export($keyPair, $privateKey); $publicKey o…...

第六章:路由交换机及操作系统

路由交换机及操作系统 一、路由器与交换机的作用与特点1.路由器1.1 作用1.2 特点 2.交换机2.1 作用2.2 特点 二、H3C路由器与交换机介绍1. 路由器2. 交换机 三、 H3C网络设备操作系统Comware1. 介绍2. 特点![在这里插入图片描述](https://img-blog.csdnimg.cn/2b24103028654878…...

Kafka SASL认证授权(六)全方位性能测试

Kafka SASL认证授权(六)全方位性能测试。 官网地址:https://kafka.apache.org/ 一、场景 线上已经有kafka集群,服务运行稳定。但是因为产品升级,需要对kakfa做安全测试,也就是权限验证。 但是增加权限验证,会不会对性能有影响呢?影响大吗?不知道呀! 因此,本文就此…...

基于nodejs+vue校园失物招领平台设计与实现

科学技术日新月异的如今&#xff0c;计算机在生活各个领域都占有重要的作用&#xff0c;尤其在信息管理方面&#xff0c;在这样的大背景下&#xff0c;学习计算机知识不仅仅是为了掌握一种技能&#xff0c;更重要的是能够让它真正地使用到实目 录 摘 要 I ABSTRACT II 目 录 II…...

Open Winding-PMSM-开绕组永磁同步电机基本介绍

文章目录 前言简介Open Widing电机数学模型零序模型 双逆变器调制零序电流抑制基本思路 前言 最近看了些Open Winding永磁同步电机及其控制策略的文献资料&#xff0c;现做个总结。未来的研究方向也大概率围绕Open Winding开展&#xff0c;期待同行交流学习。 简介 开绕组(O…...

uniapp 一次性上传多条视频 u-upload accept=“video“ uni.chooseMedia uni.uploadFile

方式 一 部分安卓机 只能一条一条传视频 文档地址 uview 2.0 Upload 上传组件 html <view class"formupload"><u-upload accept"video":fileList"fileList3" afterRead"afterRead" delete"deletePic" name"…...

CentOS7卸载硬盘报错:umount: /data: target is busy.

问题描述 umount: /data: target is busy. 问题分析 硬盘正在被使用&#xff0c;不能被卸载。 解决方案 查看哪些程序在使用硬盘 [rootlocalhost ~]# lsof /data/ COMMAND PID USER FD TYPE DEVICE SIZE/OFF NODE NAME mysqld 15655 polkitd cwd …...

Chrome插件精选 — 鼠标手势插件

Chrome实现同一功能的插件往往有多款产品&#xff0c;逐一去安装试用耗时又费力&#xff0c;在此为某一类型插件记录下比较好用的一款或几款&#xff0c;便于节省尝试的时间和精力。 下面是两款比较好用的鼠标手势插件&#xff0c;支持很多设置选项&#xff0c;可以自定义手势&…...

JMeter分布式

一 分布式注意事项 关闭防火墙控制机和代理机在同一子网控制机和代理机上安装的jmeter和JDK版本要一样关闭jmeter的RMI SSL开关 二 代理机&#xff08;agent&#xff09;的配置 修改服务端口 打开bin/jmeter.properties文件&#xff0c;修改’server_port’ 将RMI SSL设备…...

[华为杯研究生创新赛 2023] 初赛 REV WP

前言 一年没打比赛了, 差一题进决赛, REV当时lin的第三个challenge没看出来是凯撒, 想得复杂了, 结果错失一次线下机会 >_< T4ee 动态调试, nop掉反调试代码 发现处理过程为 置换sub_412F20处理(这里看其他师傅的wp知道应该是rc4, 我是直接en逆的buf字符串中每一位和…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

Linux 内存管理实战精讲:核心原理与面试常考点全解析

Linux 内存管理实战精讲&#xff1a;核心原理与面试常考点全解析 Linux 内核内存管理是系统设计中最复杂但也最核心的模块之一。它不仅支撑着虚拟内存机制、物理内存分配、进程隔离与资源复用&#xff0c;还直接决定系统运行的性能与稳定性。无论你是嵌入式开发者、内核调试工…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

android13 app的触摸问题定位分析流程

一、知识点 一般来说,触摸问题都是app层面出问题,我们可以在ViewRootImpl.java添加log的方式定位;如果是touchableRegion的计算问题,就会相对比较麻烦了,需要通过adb shell dumpsys input > input.log指令,且通过打印堆栈的方式,逐步定位问题,并找到修改方案。 问题…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

k8s从入门到放弃之HPA控制器

k8s从入门到放弃之HPA控制器 Kubernetes中的Horizontal Pod Autoscaler (HPA)控制器是一种用于自动扩展部署、副本集或复制控制器中Pod数量的机制。它可以根据观察到的CPU利用率&#xff08;或其他自定义指标&#xff09;来调整这些对象的规模&#xff0c;从而帮助应用程序在负…...

boost::filesystem::path文件路径使用详解和示例

boost::filesystem::path 是 Boost 库中用于跨平台操作文件路径的类&#xff0c;封装了路径的拼接、分割、提取、判断等常用功能。下面是对它的使用详解&#xff0c;包括常用接口与完整示例。 1. 引入头文件与命名空间 #include <boost/filesystem.hpp> namespace fs b…...

Python爬虫实战:研究Restkit库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的有价值数据。如何高效地采集这些数据并将其应用于实际业务中,成为了许多企业和开发者关注的焦点。网络爬虫技术作为一种自动化的数据采集工具,可以帮助我们从网页中提取所需的信息。而 RESTful API …...