代码随想录第49天|121. 买卖股票的最佳时机 122.买卖股票的最佳时机II

2024-04-28 03:52

本文主要是介绍代码随想录第49天|121. 买卖股票的最佳时机 122.买卖股票的最佳时机II,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 121. 买卖股票的最佳时机 

121. 买卖股票的最佳时机 - 力扣(LeetCode)

代码随想录 (programmercarl.com)

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

给定一个数组 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。

动规五部曲

1、确定dp数组以及下标的含义:dp[i][0] 表示第i天持有股票所得最多现金;

2、确定递推公式:

第i天持有股票为dp[i][0],这种状态可能由头一天的两种状态推出:

①、第i-1天就持有股票,头一天:dp[i - 1][0];

②、第i天就买如股票:所得现金:-price[i];

第i天不持有股票,即dp[i][1],这种状态也可能由头一天的两种状态推出:
①、第i-1天就不持有股票, 头一天:dp[i - 1][1]

②、第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金即:prices[i] + dp[i - 1][0]

3、dp数组如何初始化:

由递推公式基础都是要从dp[0][0]和dp[0][1]推导出来。那么dp[0][0]表示第0天持有股票,此时的持有股票就一定是买入股票了,因为不可能有前一天推出来,所以dp[0][0] -= prices[0];

dp[0][1]表示第0天不持有股票,不持有股票那么现金就是0,所以dp[0][1] = 0;

4、确定遍历顺序:从前向后遍历

5、举例推导dp数组:

综合代码:

class Solution {public int maxProfit(int[] prices) {int len = prices.length;// 定义一个二维数组 dp,大小为 len 行 2 列// dp[i][0] 表示第 i 天持有股票时的最大收益// dp[i][1] 表示第 i 天不持有股票时的最大收益int[][] dp = new int[len][2];// 初始化第一天的状态dp[0][0] = -prices[0]; // 第一天持有股票的收益为买入股票当天的价格的相反数dp[0][1] = 0; // 第一天不持有股票的收益为 0for (int i = 1; i < len; i++) {// 计算第 i 天持有股票的最大收益,取决于上一天持有股票的收益和当前买入股票的收益的较大者dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);// 计算第 i 天不持有股票的最大收益,取决于上一天不持有股票的收益和当前卖出股票的收益的较大者dp[i][1] = Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}// 返回最后一天不持有股票的收益return dp[len - 1][1];}
}

122.买卖股票的最佳时机II

122. 买卖股票的最佳时机 II - 力扣(LeetCode)

代码随想录 (programmercarl.com)

动态规划,股票问题第二弹 | LeetCode:122.买卖股票的最佳时机II_哔哩哔哩_bilibili

给定一个数组,它的第 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数组的含义:

  • dp[i][0] 表示第i天持有股票所得现金。
  • dp[i][1] 表示第i天不持有股票所得最多现金。

如果第i天持有股票即dp[i][0], 那么可以由两个状态推出来:

①、第i-1天就持有股票,那么就保持现状,所得现金就是昨天持有股票的所得现金 即:dp[i - 1][0]

②、第i天买入股票,所得现金就是昨天不持有股票的所得现金减去 今天的股票价格 即:dp[i - 1][1] - prices[i]

如果第i天不持有股票即dp[i][1]的情况, 依然可以由两个状态推出来

①、第i-1天就不持有股票,那么就保持现状,所得现金就是昨天不持有股票的所得现金 即:dp[i - 1][1]

②、第i天卖出股票,所得现金就是按照今天股票价格卖出后所得现金即:prices[i] + dp[i - 1][0]

综合代码:

class Solution {// 实现1:二维数组存储// 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储// 时间复杂度:O(n),空间复杂度:O(n)public int maxProfit(int[] prices) { // 定义一个名为 Solution 的类,包含一个方法 maxProfit,接受一个整数数组 prices 作为参数,返回一个整数int n = prices.length; // 获取价格数组的长度int[][] dp = new int[n][2]; // 创建一个二维数组 dp 来存储状态,行数为价格数组的长度,列数为 2(0 表示不持有股票,1 表示持有股票)dp[0][0] = 0; // 初始化第一天不持有股票的收益为 0dp[0][1] = -prices[0]; // 初始化第一天持有股票的收益为买入股票当天的价格的相反数for (int i = 1; i < n; ++i) { // 遍历价格数组,从第二天开始dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]); // 计算第 i 天不持有股票的最大收益,取决于上一天不持有股票的收益和当前卖出股票的收益的较大者dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 计算第 i 天持有股票的最大收益,取决于上一天持有股票的收益和当前买入股票的收益的较大者}return dp[n - 1][0]; // 返回最后一天不持有股票的收益}
}

 

这篇关于代码随想录第49天|121. 买卖股票的最佳时机 122.买卖股票的最佳时机II的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/942269

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

使用C#代码在PDF文档中添加、删除和替换图片

《使用C#代码在PDF文档中添加、删除和替换图片》在当今数字化文档处理场景中,动态操作PDF文档中的图像已成为企业级应用开发的核心需求之一,本文将介绍如何在.NET平台使用C#代码在PDF文档中添加、... 目录引言用C#添加图片到PDF文档用C#删除PDF文档中的图片用C#替换PDF文档中的图片引言在当

C#使用SQLite进行大数据量高效处理的代码示例

《C#使用SQLite进行大数据量高效处理的代码示例》在软件开发中,高效处理大数据量是一个常见且具有挑战性的任务,SQLite因其零配置、嵌入式、跨平台的特性,成为许多开发者的首选数据库,本文将深入探... 目录前言准备工作数据实体核心技术批量插入:从乌龟到猎豹的蜕变分页查询:加载百万数据异步处理:拒绝界面

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

java之Objects.nonNull用法代码解读

《java之Objects.nonNull用法代码解读》:本文主要介绍java之Objects.nonNull用法代码,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录Java之Objects.nonwww.chinasem.cnNull用法代码Objects.nonN

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

在C#中调用Python代码的两种实现方式

《在C#中调用Python代码的两种实现方式》:本文主要介绍在C#中调用Python代码的两种实现方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C#调用python代码的方式1. 使用 Python.NET2. 使用外部进程调用 Python 脚本总结C#调

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时