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…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...

学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...

视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...

3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...