当前位置: 首页 > 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;因为创建容器的时候选…...

mysql、redis面试题

mysql 相关 1、数据库优化查询方法 外键、索引、联合查询、选择特定字段等等2、简述mysql和redis区别 redis&#xff1a; 内存型非关系数据库&#xff0c;数据保存在内存中&#xff0c;速度快mysql&#xff1a;关系型数据库&#xff0c;数据保存在磁盘中&#xff0c;检索的话&…...

22、touchGFX学习Model-View-Presenter设计模式

touchGFX采用MVP架构&#xff0c;如下所示&#xff1a; 本文界面如下所示&#xff1a; 本文将实现两个操作&#xff1a; 1、触摸屏点击开关按键实现打印开关显示信息&#xff0c;模拟开关灯效果 2、板载案按键控制触摸屏LED灯的显示和隐藏 一、触摸屏点击开关按键实现打印开…...

Python Opencv实践 - 图像高斯滤波(高斯模糊)

import cv2 as cv import numpy as np import matplotlib.pyplot as pltimg cv.imread("../SampleImages/pomeranian.png", cv.IMREAD_COLOR) rows,cols,channels img.shape print(rows,cols,channels)#为图像添加高斯噪声 #使用np.random.normal(loc0.0, scale1.0…...

使用 Qt 生成 Word 和 PDF 文档的详细教程

系列文章目录 文章目录 系列文章目录前言一、安装 Qt二、生成 Word 文档三、生成 PDF 文档四、运行代码并查看结果五、自定义文档内容总结 前言 Qt 是一个跨平台的应用程序开发框架&#xff0c;除了用于创建图形界面应用程序外&#xff0c;还可以用来生成 Word 和 PDF 文档。本…...

ssm+vue校园美食交流系统源码

ssmvue校园美食交流系统源码和论文026 开发工具&#xff1a;idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 技术&#xff1a;ssm 摘 要 随着现在网络的快速发展&#xff0c;网上管理系统也逐渐快速发展起来&#xff0c;网上管理模式很快融入到了许多商…...

电力系统基础知识(一)—电力系统概述

1、电压 也称作电势差或电位差&#xff0c;是衡量单位电荷在静电场中由于电势不同所产生的能量差的物理量。其大小等于单位正电荷因受电场力作用从A点移动到B点所做的功,电压的方向规定为从高电位指向低电位。其单位为伏特(V,简称伏),常用单位还有千伏(kV)、毫伏(mV)、微伏(uV…...

spring(15) SpringBoot启动过程

目录 一、过程简介二、过程流程图三、源码分析1、运行 SpringApplication.run() 方法2、确定应用程序类型3、加载所有的初始化器4、加载所有的监听器5、设置程序运行的主类6、开启计时器7、将 java.awt.headless 设置为 true8、获取并启用监听器9、设置应用程序参数10、准备环境…...

耕地单目标语义分割实践——Pytorch网络过程实现理解

一、卷积操作 &#xff08;一&#xff09;普通卷积&#xff08;Convolution&#xff09; &#xff08;二&#xff09;空洞卷积&#xff08;Atrous Convolution&#xff09; 根据空洞卷积的定义&#xff0c;显然可以意识到空洞卷积可以提取到同一输入的不同尺度下的特征图&…...

画质提升+带宽优化,小红书音视频团队端云结合超分落地实践

随着视频业务和短视频播放规模不断增长&#xff0c;小红书一直致力于研究&#xff1a;如何在保证提升用户体验质量的同时降低视频带宽成本&#xff1f; 在近日结束的音视频技术大会「LiveVideoStackCon 2023」上海站中&#xff0c;小红书音视频架构视频图像处理算法负责人剑寒向…...

【傅里叶级数与傅里叶变换】数学推导——3、[Part4:傅里叶级数的复数形式] + [Part5:从傅里叶级数推导傅里叶变换] + 总结

文章内容来自DR_CAN关于傅里叶变换的视频&#xff0c;本篇文章提供了一些基础知识点&#xff0c;比如三角函数常用的导数、三角函数换算公式等。 文章全部链接&#xff1a; 基础知识点 Part1&#xff1a;三角函数系的正交性 Part2&#xff1a;T2π的周期函数的傅里叶级数展开 P…...