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

相关文章:

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

LeetCode: 121. 买卖股票的最佳时机 121. 买卖股票的最佳时机 - 力扣&#xff08;LeetCode&#xff09; 1.思路 暴力解法、贪心也算比较符合思维&#xff0c;动规不容易想到&#xff0c;且状态处理不易处理 股票每天的状态为持有或不持有&#xff1a;声明dp数组&#xff1a…...

【Android Framework (十二) 】- 智能硬件设备开发

文章目录 前言智能硬件的定义与应用智能硬件产品开发流程智能硬件开发所涉及的技术体系概述关于主板选型主板CPU芯片的选择关于串口通信 总结 前言 针对我过往工作经历&#xff0c;曾在一家智能科技任职Android开发工程师&#xff0c;简单介绍下关于任职期间接触和开发过的一些…...

若依框架给字典字段新增color值,并且实现下拉列表选项进行颜色设置

首先获取所要新增的字典&#xff0c;并且根据字典的value值选取对应的颜色参数 this.getDicts("risk_level").then(response > {const color {mild:#F1F4BD,moderate:#EEC920,severe:#FF6C0D,very_severe:#FF0000,no_harm:green};const res response.data.map(…...

JDK 8 升级 JDK 17 全流程教学指南

JDK 8 升级 JDK 17 首先已有项目升级是会经历一个较长的调试和自测过程来保证允许和兼容没有问题。先说几个重要的点 遇到问题别放弃仔细阅读报错&#xff0c;精确到每个单词每一行&#xff0c;不是自己项目的代码也要点进去看看源码到底是为啥报错明确你项目引入的包&#x…...

Docker 网络之 ipvlan 和 macvlan

Docker ipvlan 和 macvlan 引言 本文讲解了Docker 网络模式中的 ipvlan 和 macvlan 的区别,目前自己在生产环境中使用的 ipvlan 模式非常问题.也解决了实际业务问题. IPvlan L2 mode example ipvlan 无需网卡混杂模式 , 运行如下命令后可以生成一个 vlan 子接口 , 会和主网卡…...

【Rust】Rust学习 第十三章Rust 中的函数式语言功能:迭代器与闭包

Rust 的设计灵感来源于很多现存的语言和技术。其中一个显著的影响就是 函数式编程&#xff08;functional programming&#xff09;。函数式编程风格通常包含将函数作为参数值或其他函数的返回值、将函数赋值给变量以供之后执行等等。 更具体的&#xff0c;我们将要涉及&#…...

【Linux操作系统】详解Linux系统编程中的管道进程通信

在Linux系统编程中&#xff0c;管道是一种常用的进程间通信方式。它可以实现父子进程之间或者兄弟进程之间的数据传输。本文将介绍如何使用管道在Linux系统中进行进程通信&#xff0c;并给出相应的代码示例。 文章目录 1. 管道的概念2. 管道的创建和使用2.1 原型2.2 示例 3. 父…...

【Redis从头学-4】Redis中的String数据类型实战应用场景之验证码、浏览量、点赞量、Json格式存储

&#x1f9d1;‍&#x1f4bb;作者名称&#xff1a;DaenCode &#x1f3a4;作者简介&#xff1a;啥技术都喜欢捣鼓捣鼓&#xff0c;喜欢分享技术、经验、生活。 &#x1f60e;人生感悟&#xff1a;尝尽人生百味&#xff0c;方知世间冷暖。 &#x1f4d6;所属专栏&#xff1a;Re…...

linux 统计命令

统计命令 使用wc来进行统计 # wc [选项] 文件名wc -l a 2 awc -w a 8 a---------------l 统计行数-w 统计单词数-m 统计字符数-c 统计字节数 https://zhhll.icu/2021/linux/基础/统计命令/ 本文由 mdnice 多平台发布...

docker部署springboot应用

一、下载安装docker curl -fsSL https://get.docker.com | bash -s docker --mirror Aliyun 启动&#xff1a;systemctl start docker 二、配置国内镜像源 &#xff08;1&#xff09;在/etc/docker目录中添加daemon.json文件&#xff0c;内容如下&#xff1a; { …...

YOLO v5、v7、v8 模型优化

YOLO v5、v7、v8 模型优化 魔改YOLOyaml 文件解读模型选择在线做数据标注 YOLO算法改进YOLOv5yolo.pyyolov5.yaml更换骨干网络之 SwinTransformer更换骨干网络之 EfficientNet优化上采样方式&#xff1a;轻量化算子CARAFE 替换 传统&#xff08;最近邻 / 双线性 / 双立方 / 三线…...

回归预测 | MATLAB实现SSA-BP麻雀搜索算法优化BP神经网络多输入单输出回归预测(多指标,多图)

回归预测 | MATLAB实现SSA-BP麻雀搜索算法优化BP神经网络多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09; 目录 回归预测 | MATLAB实现SSA-BP麻雀搜索算法优化BP神经网络多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09;效果一览基本…...

QT的mysql(数据库)最佳实践和常见问题解答

涉及到数据库&#xff0c;首先安利一个软件Navicat Premium&#xff0c;用来查询数据库很方便 QMysql驱动是Qt SQL模块使用的插件&#xff0c;用于与MySQL数据库进行通信。要编译QMysql驱动&#xff0c;您需要满足以下条件&#xff1a; 您需要安装MySQL的客户端库和开发头文件…...

使用PyMuPDF库的PDF合并和分拆程序

PDF工具应用程序是一个使用wxPython和PyMuPDF库编写的简单工具&#xff0c;用于合并和分拆PDF文件。它提供了一个用户友好的图形界面&#xff0c;允许用户选择源文件夹和目标文件夹&#xff0c;并对PDF文件进行操作。 C:\pythoncode\blog\pdfmergandsplit.py 功能特点 选择文…...

2023/8/18 - You need to rely on yourself to achieve the life you want

...

Data Abstract for .NET and Delphi Crack

Data Abstract for .NET and Delphi Crack .NET和Delphi的数据摘要是一套或RAD工具&#xff0c;用于在.NET、Delphi和Mono中编写多层解决方案。NET和Delphi的数据摘要是一个套件&#xff0c;包括RemObjects.NET和Delphi版本的数据摘要。RemObjects Data Abstract允许您创建访问…...

Eclipse集成MapStruct

Eclipse集成MapStruct 在Eclipse中添加MapStruct依赖配置Eclipse支持MapStruct①安装 m2e-aptEclipse Marketplace的方式安装Install new software的方式安装&#xff08;JDK8用到&#xff09; ②添加到pom.xml 今天拿到同事其他项目的源码&#xff0c;导入并运行的时候抛出了异…...

采用pycharm在虚拟环境使用pyinstaller打包python程序

一年多以前&#xff0c;我写过一篇博客描述了如何虚拟环境打包&#xff0c;这一次有所不同&#xff0c;直接用IDE pycharm构成虚拟环境并运行pyinstaller打包 之前的博文&#xff1a; 虚拟环境venu使用pyinstaller打包python程序_伊玛目的门徒的博客-CSDN博客 第一步&#xf…...

Rx.NET in Action 中文介绍 前言及序言

Rx 处理器目录 (Catalog of Rx operators) 目标可选方式Rx 处理器(Operator)创建 Observable Creating Observables直接创建 By explicit logicCreate Defer根据范围创建 By specificationRangeRepeatGenerateTimerInterval Return使用预设 Predefined primitivesThrow …...

Azure Blob存储使用

创建存储账户,性能选择标准即可&#xff0c;冗余选择本地冗余存储即可 容器选择类别选择专用即可 可以上传文件到blob中 打开文件可以看到文件的访问路径 4.编辑中可以修改文件 复制链接&#xff0c;尝试访问&#xff0c;可以看到没有办法访问&#xff0c;因为创建容器的时候选…...

智慧医疗能源事业线深度画像分析(上)

引言 医疗行业作为现代社会的关键基础设施,其能源消耗与环境影响正日益受到关注。随着全球"双碳"目标的推进和可持续发展理念的深入,智慧医疗能源事业线应运而生,致力于通过创新技术与管理方案,重构医疗领域的能源使用模式。这一事业线融合了能源管理、可持续发…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

Java数值运算常见陷阱与规避方法

整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者&#xff1a;来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布&#xff0c;Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明&#xff0c;Elastic 作为 …...