代码随想录第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

相关文章

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip

D4代码AC集

贪心问题解决的步骤: (局部贪心能导致全局贪心)    1.确定贪心策略    2.验证贪心策略是否正确 排队接水 #include<bits/stdc++.h>using namespace std;int main(){int w,n,a[32000];cin>>w>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int i=1

从0到1,AI我来了- (7)AI应用-ComfyUI-II(进阶)

上篇comfyUI 入门 ,了解了TA是个啥,这篇,我们通过ComfyUI 及其相关Lora 模型,生成一些更惊艳的图片。这篇主要了解这些内容:         1、哪里获取模型?         2、实践如何画一个美女?         3、附录:               1)相关SD(稳定扩散模型的组成部分)               2)模型放置目录(重要)

html css jquery选项卡 代码练习小项目

在学习 html 和 css jquery 结合使用的时候 做好是能尝试做一些简单的小功能,来提高自己的 逻辑能力,熟悉代码的编写语法 下面分享一段代码 使用html css jquery选项卡 代码练习 <div class="box"><dl class="tab"><dd class="active">手机</dd><dd>家电</dd><dd>服装</dd><dd>数码</dd><dd

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图