当前位置: 首页 > 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…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

简易版抽奖活动的设计技术方案

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

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

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

均衡后的SNRSINR

本文主要摘自参考文献中的前两篇&#xff0c;相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程&#xff0c;其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt​ 根发送天线&#xff0c; n r n_r nr​ 根接收天线的 MIMO 系…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

【笔记】WSL 中 Rust 安装与测试完整记录

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