Day49|leetcode 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II
leetcode 121. 买卖股票的最佳时机
题目链接:121. 买卖股票的最佳时机 - 力扣(LeetCode)
视频链接:动态规划之 LeetCode:121.买卖股票的最佳时机1_哔哩哔哩_bilibili
题目概述
给定一个数组 ,它的第 个元素 表示一支给定股票第 天的价格。prices
iprices[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。
思路
1.确定dp数组含义:
dp[i][0] :第i天持有股票所得最多现金。
dp[i][1] :第i天不持有股票所得最多现金。
这里的“持有”和“不持有”不代表当天买入股票或者卖出股票,可能是前一天买的!!!
2.确定递推公式:(最开始现金为0元)
第i天持有股票:
1)当天就买进股票:-prices[i]
2)前一天买进股票:dp[i - 1][0]
所以dp[i][0] = max(dp[i - 1][0], -prices[i])
第i天不持有股票:
1)当天卖出股票:prices[i] + dp[i - 1][0]
2)前一天卖出股票:dp[i - 1][1]
所以dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
3.数组初始化:
dp[0][0] -= prices[0]
dp[0][1] = 0
4.确定遍历顺序:
从前向后
5.打印dp数组:
代码实现(动规)
class Solution {
public:int maxProfit(vector<int>& prices) {if(prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(),vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for(int i = 1;i < prices.size();i++) {dp[i][0] = max(-prices[i],dp[i - 1][0]);dp[i][1] = max(prices[i] + dp[i - 1][0],dp[i - 1][1]);} return dp[prices.size() - 1][1];}
};
代码实现(贪心)
class Solution {
public:int maxProfit(vector<int>& prices) {int low = INT_MAX;int result = 0;for (int i = 0; i < prices.size(); i++) {low = min(low, prices[i]); // 取最左最小价格result = max(result, prices[i] - low); // 直接取最大区间利润}return result;}
};
leetcode 122.买卖股票的最佳时机II
题目链接:122. 买卖股票的最佳时机 II - 力扣(LeetCode)
视频链接:动态规划,股票问题第二弹 | LeetCode:122.买卖股票的最佳时机II_哔哩哔哩_bilibili
题目概述
给你一个整数数组 prices
,其中 prices[i]
表示某支股票第 i
天的价格。
在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1:
输入: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 。
思路
本题和上一题没有多大区别,唯一区别就是本题可以多次买卖,在动规五部曲分析上也只有递归公式上有区别。
第i天持有股票:
1)当天就买进股票:dp[i - 1][1] - prices[i](这里是和上一题唯一不一样的区别,因为上道题最开始手里的钱是0元,所以是'0 - prices[i]'只不过把0给省略了,而这道题可以多次买卖股票,如果是当天买进股票的话,那么所得现金就是昨天不持有股票的所得现金 - 今天的股票价格)
2)前一天买进股票:dp[i - 1][0]
所以dp[i][0] = max(dp[i - 1][0], -prices[i])
第i天不持有股票:dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
代码实现(动规)
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();vector<vector<int>> dp(len, vector<int>(2, 0));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]); // 注意这里是和121. 买卖股票的最佳时机唯一不同的地方。dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[len - 1][1];}
};
代码实现(贪心)
class Solution {
public:int maxProfit(vector<int>& prices) {int result = 0;for(int i = 1;i < prices.size();i++) {result += max(prices[i] - prices[i - 1],0);}return result;}
};
相关文章:

Day49|leetcode 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II
leetcode 121. 买卖股票的最佳时机 题目链接:121. 买卖股票的最佳时机 - 力扣(LeetCode) 视频链接:动态规划之 LeetCode:121.买卖股票的最佳时机1_哔哩哔哩_bilibili 题目概述 给定一个数组 ,它的第 个元…...

【项目经验】:elementui表格中表头的多选框换成文字
一.项目需求 表格可以多选,表头都是汉字。。。。类似于这种 二.实现功能 用到的方法 Table Attributes 参数说明类型可选值默认值header-cell-class-name表头单元格的 className 的回调方法,也可以使用字符串为所有表头单元格设置一个固定的 className。…...

【LeetCode】剑指 Offer <二刷>(4)
目录 题目:剑指 Offer 09. 用两个栈实现队列 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 10- I. 斐波那契数列 - 力扣&am…...
CentOS7查看和关闭防火墙
CentOS 7.0默认使用的是firewall作为防火墙 查看防火墙状态 firewall-cmd --state1 停止firewall systemctl stop firewalld.service1 禁止firewall开机启动 systemctl disable firewalld.service 1 转自:CentOS 6和CentOS 7防火墙的关闭 Centos7开放及查看…...

LeetCode 无重复字符的最长子串 打败100%的人
😀前言 LeetCode上的“无重复字符的最长子串”问题要求我们找到给定字符串中不包含重复字符的最长子串的长度。这个问题是一个典型的滑动窗口技巧的应用,需要有效地处理字符出现的情况来找到解决方案。 . 在本解决方案中,我们将探讨两种不同的…...

Spring Boot中通过maven进行多环境配置
上文 java Spring Boot将不同配置拆分入不同文件管理 中 我们说到了,多环境的多文件区分管理 说到多环境 其实不止我们 Spring Boot有 很多的东西都有 那么 这就有一个问题 如果 spring 和 maven 都配置了环境 而且他们配的不一样 那么 会用谁的呢? 此…...
python自动化Selenium的使用
python自动化Selenium的使用 Selenium是一个自动化测试框架,用于模拟和控制浏览器操作,支持多种编程语言。它可以模拟人类用户在浏览器上的操作(如点击、滚动、输入等),并检查网页内容和元素的属性。Selenium可用于对…...

大数据课程K13——Spark的距离度量相似度度量
文章作者邮箱:yugongshiye@sina.cn 地址:广东惠州 ▲ 本章节目的 ⚪ 掌握Spark的距离度量和相似度度量; ⚪ 掌握Spark的欧氏距离; ⚪ 掌握Spark的曼哈顿距离; ⚪ 掌握Spark的切比雪夫距离; ⚪ 掌握Spark的最小二乘法; 一、距离度量和相似度度量 1. …...
Lambda表达式第四版
1、冗余的Runnbale代码 package com.lambda;public class Demo01Runnable {public static void main(String[] args) {RunnableImpl runnable new RunnableImpl();Thread thread new Thread(runnable);thread.start();//Lambda表达式} }class RunnableImpl implements Runnab…...
自定义类加载器
java中自定义类加载器,并将双亲委派改为逆向双亲委派 自定义类加载器JarLoader: package cn.ac.iscas.dmo.common.tools.core.classloader;import org.apache.commons.collections4.MapUtils;import java.io.*; import java.net.URL; import java.net.U…...

【Redis】Redis 的学习教程(七)之 SpringBoot 集成 Redis
在前几篇文章中,我们详细介绍了 Redis 的一些功能特性以及主流的 java 客户端 api 使用方法。 在当前流行的微服务以及分布式集群环境下,Redis 的使用场景可以说非常的广泛,能解决集群环境下系统中遇到的不少技术问题,在此列举几…...

Vlan和Trunk
文章目录 一、VLAN的定义与背景1. 传统以太网的问题(广播域)2. 用VLAN隔离广播域3. VLAN的优点与应用 二、VLAN的转发过程举例三、802.1Q标签:帧格式与作用四、VLAN工作原理交换机端口类型AccessTrunkHybrid PVID(Port VLAN ID&am…...

java 批量下载将多个文件(minio中存储)压缩成一个zip包
我的需求是将minio中存储的文件按照查询条件查询出来统一压成一个zip包然后下载下来。 思路:针对这个需求,其实可以有多个思路,不过也大同小异,一般都是后端返回流文件前端再处理下载,也有少数是压缩成zip包之后直接给…...

nnUNet v2数据准备及格式转换 (二)
如果你曾经使用过nnUNet V1,那你一定明白数据集的命名是有严格要求的,必须按照特定的格式来进行命名才能正常使用。 这一节的学习需要有数据,如果你有自己的数据,可以拿自己的数据来实验,如果没有,可以用十…...

ant-vue1.78版监听a-modal遮罩层的滚动事件
监听a-modal遮罩层的滚动事件 我们开发过程中经常有遇到监听页面滚动的事件需求,去做一些下拉加载或者是下拉分页的需求,我们直接在vue的生命周期中去绑定事件监听非常的方便,但如果是弹框的遮罩层的滚动监听呢?页面的监听完全是…...

MATLAB中residue函数用法
目录 语法 说明 示例 求解具有实根的部分分式展开式 展开具有复数根和同次分子及分母的分式 展开分子次数高于分母次数的分式 residue函数的功能是部分分式展开(部分分式分解)。 语法 [r,p,k] residue(b,a) [b,a] residue(r,p,k) 说明 [r,p…...

攻防世界-Caesar
原题 解题思路 没出现什么特殊字符,可能是个移位密码。凯撒密码加密解密。偏移12位就行。...
嵌入式开发-lin总线介绍 一.概述
1.1lin总线定义和历史 LIN总线(Local Interconnect Network)是一种基于UART/SCI(Universal Asynchronous Receiver-Transmitter/Serial Communication Interface)的低成本串行通信协议。它主要用于汽车、家电、办公设备等多种领域…...

羊城杯-2023-Crypto
文章目录 Danger_RSA题目描述:题目分析: Easy_3L题目描述:题目分析: XOR贯穿始终题目描述:题目分析: MCeorpkpleer题目描述:题目分析: SigninCrypto题目描述:题目分析&am…...

RabbitMQ快速上手及讲解
前言:在介绍RabbitMQ之前,我们先来看下面一个场景: 1.1.1.1 异步处理 场景说明: 用户注册后,需要发注册邮件和注册短信,传统的做法有两种 1.串行的方式 (1)串行方式:将注册信息写入数据库后&a…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...

简易版抽奖活动的设计技术方案
1.前言 本技术方案旨在设计一套完整且可靠的抽奖活动逻辑,确保抽奖活动能够公平、公正、公开地进行,同时满足高并发访问、数据安全存储与高效处理等需求,为用户提供流畅的抽奖体验,助力业务顺利开展。本方案将涵盖抽奖活动的整体架构设计、核心流程逻辑、关键功能实现以及…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)
文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...

【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...