121.买卖股票的最佳时机 122.买卖股票的最佳时机II
121.买卖股票的最佳时机 122.买卖股票的最佳时机II
121.买卖股票的最佳时机
力扣题目链接(opens new window)
给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。
- 示例 1:
- 输入:[7,1,5,3,6,4]
- 输出:5
解释:在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。 - 示例 2:
- 输入:prices = [7,6,4,3,1]
- 输出:0
解释:在这种情况下, 没有交易完成, 所以最大利润为 0。
思路:贪心
这道题目用贪心可以解决,回顾下贪心算法
需要定义局部最优解和整体最优解
题目只要求买卖一次股票,并获取最大利润
要找到股票左侧最低点,并在右侧最高点卖出
找最低点和最高点的流程可以用一个For循环来解决
遍历数组prices,假设遍历的元素就是右侧最高点,在遍历过的元素中找到最低点,即为左侧最低点
计算利润差值即可
局部最优解:找到当前左侧的最低点,计算当前利润最大值
整体最优解:这笔交易中获取的最大利润
时间复杂度o(n)
空间复杂度o(1)
代码如下
public int maxProfit(int[] prices) {if (prices == null || prices.length == 0)return 0;int low = Integer.MAX_VALUE;int maxProfit = 0;for (int i = 0; i < prices.length; i++) {low = Math.min(low, prices[i]);maxProfit = Math.max(maxProfit, prices[i] - low);}return maxProfit;
}
思路:动态规划
思路:动态规划 股票类问题,动态规划解法是通用解法 动态规划五部曲 1.dp数组以及下标代表含义 之前做惯了背包类题目,习惯定义一维数组解决问题。不是背包类题目,要根据题意具体分析 定义一维数组dp[i],表示第i天从这笔交易中获取的最大利润。但买和卖这两种状态无法表示 因此定义二维数组dp[i][j]。j = 0 表示第i天不持有股票利润 j = 1表示第i天持有股票的利润 要用持有和不持有股票作为状态,不用出售和不出售作为状态(因为还要定义【保持卖出状态】和【保持买入状态】) 2.确定递推公式 第i天不持有股票。 1.第i-1天不持有股票 dp[i][0] = dp[i-1][0] 2.第i-1天持有股票 dp[i][0] = prices[i] + dp[i-1][1] dp[i][0] = Math.max(dp[i-1][0],prices[i] + dp[i-1][1]) 第i天持有股票 1.第i-1天不持有股票dp[i][1] = -price[i] 2.第i-1天持有股票dp[i][1] = dp[i-1][1]dp[i][1] = Math.max( -prices[i],dp[i-1][1]) 3.dp数组初始化 dp[0][0] = 0 dp[0][1] = -prices[0] 4.遍历顺序,dp[i]由dp[i-1]推导,故正序 5.举例推导dp数组时间复杂度o(n) 空间复杂度o(n)
代码如下
public static void main(String[] args) {int[] prices = new int[]{7, 1, 5, 3, 6, 4};maxProfit(prices);
}public static int maxProfit(int[] prices) {if (prices == null || prices.length == 0)return 0;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], prices[i] + dp[i - 1][1]);dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);}return dp[prices.length - 1][0];// 最后一天肯定不持有
}
122.买卖股票的最佳时机II
力扣题目链接(opens new window)
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
- 示例 1:
- 输入: [7,1,5,3,6,4]
- 输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4。随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 - 示例 2:
- 输入: [1,2,3,4,5]
- 输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。 - 示例 3:
- 输入: [7,6,4,3,1]
- 输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
提示:
- 1 <= prices.length <= 3 * 10 ^ 4
- 0 <= prices[i] <= 10 ^ 4
思路
思路:动态规划 思路和买卖股票的最佳时机类似,区别在于递推公式 dp[i][0] j = 0表示未持有,此部分逻辑不变 i- 1 持有股票:dp[i][0] = prices[i] + dp[i-1][1] i- 1 未持有股票:dp[i][0] = dp[i-1][0] dp[i][1] j = 1表示持有。i-1未持有股票逻辑变化 i- 1 持有股票:dp[i][1] = dp[i-1][1] i- 1 未持有股票:dp[i][1] = dp[i-1][0] - prices[i] 变化在此处 因为股票可以买卖多次。当前未持有股票的利润,可能包含之前买卖股票的利润 所以需要用之前买卖股票的利润 - 当前持有股票的利润
代码如下
// 时间复杂度o(n)
// 空间复杂度o(n)
public int maxProfitII(int[] prices) {if (prices == null || prices.length == 0)return 0;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], prices[i] + dp[i - 1][1]);dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);}return dp[prices.length - 1][0];// 最后一天肯定不持有
}
相关文章:
121.买卖股票的最佳时机 122.买卖股票的最佳时机II
121.买卖股票的最佳时机 122.买卖股票的最佳时机II 121.买卖股票的最佳时机 力扣题目链接(opens new window) 给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一…...
Spring Boot整理-Spring Boot是什么?
Spring Boot 是一个开源的 Java 基础框架,它旨在简化基于 Spring 的应用开发。其核心特点在于“约定优于配置”的设计哲学,意味着它提供了一系列默认配置,从而帮助开发者更快地启动和运行新的 Spring 应用。Spring Boot 的主要特点包括: 自动配置:Spring Boot 可以根据项目…...
【pytorch】Pytorch 中的 grid 与 各种变换
Pytorch 中的 grid 与 各种变换 数学原理 **单应性(Homography) : 也就是透视变换。**单应性最初用来研究欧几里得几何中的透视和投影,而单应性一词,从词源学上来说,大致意思是“相似的绘图”。单应性的概念被引入来…...
【Linux】线程池实现
📗线程池实现(单例模式) 1️⃣线程池概念2️⃣线程池代码样例3️⃣部分问题与细节🔸类成员函数参数列表中隐含的this指针🔸单例模式🔸一个失误导致的bug 4️⃣调用线程池完成任务 1️⃣线程池概念 线程池是…...
使用Python批量上传本地maven库到nexus
背景:外包类项目开发时是调用的公司maven仓库进行开发,交付后需要将maven仓库转移到客户环境。 原理:1、打开idea运行源代码,将maven包下载到本地仓库, 2、下载包所在目录中执行脚本将本地仓库的maven包上传到客户nex…...
【Unity实战100例】Unity对Ini格式的配置文件管理和读写
目录 一.编写ini格式配置文件 二.读取解析ini文件 三.调用属性 INI 文件以文本形式存储,易于阅读和编辑。这种人可读的格式使得调整配置参数变得更加直观,不需要专门的工具。 INI 文件是一种轻量级的配置文件格式,不需要复杂的解析器或库。它的结构相对简单,适用于小到...
k8s存储卷和数据卷下
静态pv和pvc 运维负责pv:创建号持久化存储卷,申明好读写和挂载类型,以及可以提供的存储空间 Pvc开发做,要和开发沟通好,你期望的读写和挂载类型,以及存储空间 当我发布vc之后可以生成pv,还可以在…...
SQL Server 配置远程连接
Windows 安装好 SQL Server 的 SSMS,打开SSMS配置远程连接 找到 配置管理器 启用 TCP/IP 打开防火墙设置 新建入站规则 端口TCP - 特定本地端口 (1433)允许连接下一步名称完成 重启 SQL Server 服务...
vscode(visual studio code) 免密登陆服务器
1.生成密钥 首先,在本地,打开命令输入框: WinR–>弹出输入框,输入cmd,打开命令框。 然后,在命令框,输入 ssh-keygen -t rsa -C "love"按两次回车键,问你是否重写,选择…...
[redis] redis主从复制,哨兵模式和集群
一、redis的高可用 1.1 redis高可用的概念 在web服务器中,高可用是指服务器可以正常访问的时间,衡量的标准是在多长时间内可以提供正常服务(99.9%、99.99%、99.999%等等)。 高可用的计算公式是1-(宕机时间)/(宕机时…...
debian12部署Gitea服务
首先安装git、wget、sqlite,然后进行用户和组的相关设置 sudo apt install -y git wget sqlite3 新增一个git用户与一个git组 sudo adduser --system --group --disabled-password --shell /bin/bash --home /home/git --gecos Git Version Control git 给git用户设…...
js动态设置关键侦@keyframes
js动态设置关键侦keyframes 1.前置知识 关键侦keyframes规则通过在动画序列中定义关键侦的样式来控制CSS动画序列的中间步骤 keyframes slidein {from {transform: translateX(0%);}to {transform: translateX(100%);} } // from 等价于 0%;to 等价与 100% // 或…...
【WPF.NET开发】流文档
本文内容 什么是流文档?流文档类型创建流内容与流相关的类内容架构自定义文本 流文档旨在优化查看和可读性。 流文档根据运行时变量(例如,窗口大小、设备分辨率和可选的用户首选项)来动态调整和重新排列内容,而不是设…...
golang学习-结构体
1、定义 使用type 和struct 关键字来定义结构体,是值类型 格式如下: type 类型名 struct { 字段名 类型 字段名 类型 ... } 2、实例化 1、var 结构体实例 结构体类型 var p1 Person 2、使用new关键字 var p2 new(Person) 3、使用&对结构体…...
Python:enumerate() 函数
enumerate() 函数用于同时遍历索引和元素,常用于循环中。这个函数返回一个包含索引和元素的元组,可以通过解包的方式获取它们。 使用方法: enumerate(iterable, start0). iterable: 要遍历的可迭代对象。start: 索引起始值,默认…...
FPGA 移位运算与乘法
题目: 已知d为一个8位数,请在每个时钟周期分别输出该数乘1/3/7/8,并输出一个信号通知此时刻输入的d有效(d给出的信号的上升沿表示写入有效) 由题意可知: 复位信号高有效,低复位;在inpu_grant上升…...
网络安全B模块(笔记详解)- MYSQL信息收集
MYSQL信息收集 1.通过渗透机场景Kali中的渗透测试工具对服务器场景MySQL03进行服务信息扫描渗透测试(使用工具Nmap,使用必须要使用的参数),并将该操作显示结果中数据库版本信息作为Flag提交; Flag:MySQL 5.5.12 2.通过渗透机场景Kali中的渗透测试工具对服务器场景MySQL0…...
从JavaScript的角度上讲解一下xml
- XML(可扩展标记语言) XML(可扩展标记语言)是一种被设计用于存储和传输结构化数据的标记语言。它与HTML相似,但XML并没有预定义的标签,可以自定义标签及其属性。从JavaScript的角度来看,XML可以…...
Pandas实战100例 | 案例 13: 数据分类 - 使用 `cut` 对数值进行分箱
案例 13: 数据分类 - 使用 cut 对数值进行分箱 知识点讲解 在数据分析中,将连续的数值数据分类成不同的区间(或“分箱”)是一种常见的做法。Pandas 提供了 cut 函数,它可以根据你指定的分箱边界将数值数据分配到不同的类别中。 …...
python统计分析——操作案例(模拟抽样)
参考资料:用python动手学统计学 import numpy as np import pandas as pd from matplotlib import pyplot as plt import seaborn as snsdata_setpd.read_csv(r"C:\python统计学\3-4-1-fish_length_100000.csv")[length] #此处将文件路径改为自己的路…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...
Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
服务器--宝塔命令
一、宝塔面板安装命令 ⚠️ 必须使用 root 用户 或 sudo 权限执行! sudo su - 1. CentOS 系统: yum install -y wget && wget -O install.sh http://download.bt.cn/install/install_6.0.sh && sh install.sh2. Ubuntu / Debian 系统…...
在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案
这个问题我看其他博主也写了,要么要会员、要么写的乱七八糟。这里我整理一下,把问题说清楚并且给出代码,拿去用就行,照着葫芦画瓢。 问题 在继承QWebEngineView后,重写mousePressEvent或event函数无法捕获鼠标按下事…...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
Sklearn 机器学习 缺失值处理 获取填充失值的统计值
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 使用 Scikit-learn 处理缺失值并提取填充统计信息的完整指南 在机器学习项目中,数据清…...
FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...
