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

算法练习Day49|● 121. 买卖股票的最佳时机 ● 122.买卖股票的最佳时机II

LeetCode: 121. 买卖股票的最佳时机 

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

1.思路

暴力解法、贪心也算比较符合思维,动规不容易想到,且状态处理不易处理
股票每天的状态为持有或不持有:声明dp数组:int[][] dp = new int[prices.length][2];

确定含义:dp[i][0] 表示第i天持有股票的最大收益,dp[i][1] 表示第i天不持有股票的最大收益。

初始化:dp[0][0] = -prices[0];dp[0][1] = 0;

2.代码实现

 1// 动规2class Solution {3    public int maxProfit(int[] prices) {4        if (prices.length == 0 || prices == null) {5            return 0;6        }7        // dp[i][0] 表示第i天持有股票的最大收益8        // dp[i][1] 表示第i天不持有股票的最大收益9        int[][] dp = new int[prices.length][2];
10        dp[0][0] = -prices[0];
11        dp[0][1] = 0;
12        for (int i = 1; i < prices.length; i++) {
13            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
14            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
15        }
16        return dp[prices.length - 1][1];
17    }
18}
19
 1// 暴力解法2class Solution {3    public int maxProfit(int[] prices) {4        int profit = 0;5        for (int i = 0; i < prices.length; i++) {6            for (int j = i + 1; j < prices.length; j++) {7                profit = Math.max(profit, prices[j] - prices[i]);8            }9        }
10        return profit;
11    }
12}
13// 贪心算法
14class Solution {
15    public int maxProfit(int[] prices) {
16        int low = Integer.MAX_VALUE;
17        int res = 0;
18        for (int i = 0; i < prices.length; i++) {
19            low = Math.min(prices[i], low);
20            res = Math.max(prices[i] - low, res);
21        }
22        return res;
23    }
24}

3.时间复杂度

时间复杂度:O(n).
空间复杂度:O(1).

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

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

1.思路

动规真香,可以一个套路解决多题
和上一题类似,每天股票有两种状态,持有或不持有。
递推公式:
第i天持有,有两种情况:①第i-1天就持有;②第i天买入持有;
第i天不持有,有两种情况:①第i-1天就不持有;②第i天卖出,说明第i-1天持有(包含了当天买入卖出)

2.代码实现

 1class Solution {2    public int maxProfit(int[] prices) {3        if (prices.length == 0 || prices == null) {4            return 0;5        }6        int[][] dp = new int[prices.length][2];7        // 8        // 9        dp[0][0] = -prices[0];
10        dp[0][1] = 0;
11        for (int i = 1; i < prices.length; i++) {
12            // 第 i 天持有股票:①当天买入且前一天不持有;②前一天持有
13            dp[i][0] = Math.max(dp[i - 1][1] - prices[i], dp[i - 1][0]);
14            // 第 i 天不持有股票:①第 i 天卖出;②第i-1天就不持有
15            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
16        }
17        return dp[prices.length - 1][1];
18    }
19}
20

3.时间复杂度

时间复杂度:O(n).
空间复杂度:O(1).

http://www.lryc.cn/news/129671.html

相关文章:

  • 【Android Framework (十二) 】- 智能硬件设备开发
  • 若依框架给字典字段新增color值,并且实现下拉列表选项进行颜色设置
  • JDK 8 升级 JDK 17 全流程教学指南
  • Docker 网络之 ipvlan 和 macvlan
  • 【Rust】Rust学习 第十三章Rust 中的函数式语言功能:迭代器与闭包
  • 【Linux操作系统】详解Linux系统编程中的管道进程通信
  • 【Redis从头学-4】Redis中的String数据类型实战应用场景之验证码、浏览量、点赞量、Json格式存储
  • linux 统计命令
  • docker部署springboot应用
  • YOLO v5、v7、v8 模型优化
  • 回归预测 | MATLAB实现SSA-BP麻雀搜索算法优化BP神经网络多输入单输出回归预测(多指标,多图)
  • QT的mysql(数据库)最佳实践和常见问题解答
  • 使用PyMuPDF库的PDF合并和分拆程序
  • 2023/8/18 - You need to rely on yourself to achieve the life you want
  • Data Abstract for .NET and Delphi Crack
  • Eclipse集成MapStruct
  • 采用pycharm在虚拟环境使用pyinstaller打包python程序
  • Rx.NET in Action 中文介绍 前言及序言
  • Azure Blob存储使用
  • mysql、redis面试题
  • 22、touchGFX学习Model-View-Presenter设计模式
  • Python Opencv实践 - 图像高斯滤波(高斯模糊)
  • 使用 Qt 生成 Word 和 PDF 文档的详细教程
  • ssm+vue校园美食交流系统源码
  • 电力系统基础知识(一)—电力系统概述
  • spring(15) SpringBoot启动过程
  • 耕地单目标语义分割实践——Pytorch网络过程实现理解
  • 画质提升+带宽优化,小红书音视频团队端云结合超分落地实践
  • 【傅里叶级数与傅里叶变换】数学推导——3、[Part4:傅里叶级数的复数形式] + [Part5:从傅里叶级数推导傅里叶变换] + 总结
  • 第二章MyBatis入门程序