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

Day49|leetcode 121. 买卖股票的最佳时机、122.买卖股票的最佳时机II

leetcode 121. 买卖股票的最佳时机

题目链接:121. 买卖股票的最佳时机 - 力扣(LeetCode)

视频链接:动态规划之 LeetCode:121.买卖股票的最佳时机1_哔哩哔哩_bilibili

 题目概述

给定一个数组 ,它的第  个元素  表示一支给定股票第 天的价格。pricesiprices[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数组:

121.买卖股票的最佳时机

 

代码实现(动规)

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. 买卖股票的最佳时机 题目链接&#xff1a;121. 买卖股票的最佳时机 - 力扣&#xff08;LeetCode&#xff09; 视频链接&#xff1a;动态规划之 LeetCode&#xff1a;121.买卖股票的最佳时机1_哔哩哔哩_bilibili 题目概述 给定一个数组 &#xff0c;它的第 个元…...

【项目经验】:elementui表格中表头的多选框换成文字

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

【LeetCode】剑指 Offer <二刷>(4)

目录 题目&#xff1a;剑指 Offer 09. 用两个栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;剑指 Offer 10- I. 斐波那契数列 - 力扣&am…...

CentOS7查看和关闭防火墙

CentOS 7.0默认使用的是firewall作为防火墙 查看防火墙状态 firewall-cmd --state1 停止firewall systemctl stop firewalld.service1 禁止firewall开机启动 systemctl disable firewalld.service 1 转自&#xff1a;CentOS 6和CentOS 7防火墙的关闭 Centos7开放及查看…...

LeetCode 无重复字符的最长子串 打败100%的人

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

Spring Boot中通过maven进行多环境配置

上文 java Spring Boot将不同配置拆分入不同文件管理 中 我们说到了&#xff0c;多环境的多文件区分管理 说到多环境 其实不止我们 Spring Boot有 很多的东西都有 那么 这就有一个问题 如果 spring 和 maven 都配置了环境 而且他们配的不一样 那么 会用谁的呢&#xff1f; 此…...

python自动化Selenium的使用

python自动化Selenium的使用 Selenium是一个自动化测试框架&#xff0c;用于模拟和控制浏览器操作&#xff0c;支持多种编程语言。它可以模拟人类用户在浏览器上的操作&#xff08;如点击、滚动、输入等&#xff09;&#xff0c;并检查网页内容和元素的属性。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中自定义类加载器&#xff0c;并将双亲委派改为逆向双亲委派 自定义类加载器JarLoader&#xff1a; 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

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

Vlan和Trunk

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

java 批量下载将多个文件(minio中存储)压缩成一个zip包

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

nnUNet v2数据准备及格式转换 (二)

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

ant-vue1.78版监听a-modal遮罩层的滚动事件

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

MATLAB中residue函数用法

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

攻防世界-Caesar

原题 解题思路 没出现什么特殊字符&#xff0c;可能是个移位密码。凯撒密码加密解密。偏移12位就行。...

嵌入式开发-lin总线介绍 一.概述

1.1lin总线定义和历史 LIN总线&#xff08;Local Interconnect Network&#xff09;是一种基于UART/SCI&#xff08;Universal Asynchronous Receiver-Transmitter/Serial Communication Interface&#xff09;的低成本串行通信协议。它主要用于汽车、家电、办公设备等多种领域…...

羊城杯-2023-Crypto

文章目录 Danger_RSA题目描述&#xff1a;题目分析&#xff1a; Easy_3L题目描述&#xff1a;题目分析&#xff1a; XOR贯穿始终题目描述&#xff1a;题目分析&#xff1a; MCeorpkpleer题目描述&#xff1a;题目分析&#xff1a; SigninCrypto题目描述&#xff1a;题目分析&am…...

RabbitMQ快速上手及讲解

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

[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?

&#x1f9e0; 智能合约中的数据是如何在区块链中保持一致的&#xff1f; 为什么所有区块链节点都能得出相同结果&#xff1f;合约调用这么复杂&#xff0c;状态真能保持一致吗&#xff1f;本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里&#xf…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:

一、属性动画概述NETX 作用&#xff1a;实现组件通用属性的渐变过渡效果&#xff0c;提升用户体验。支持属性&#xff1a;width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项&#xff1a; 布局类属性&#xff08;如宽高&#xff09;变化时&#…...

学校招生小程序源码介绍

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

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

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

3-11单元格区域边界定位(End属性)学习笔记

返回一个Range 对象&#xff0c;只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意&#xff1a;它移动的位置必须是相连的有内容的单元格…...