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

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

VM虚拟机网络配置(ubuntu24桥接模式):配置静态IP

编辑-虚拟网络编辑器-更改设置 选择桥接模式&#xff0c;然后找到相应的网卡&#xff08;可以查看自己本机的网络连接&#xff09; windows连接的网络点击查看属性 编辑虚拟机设置更改网络配置&#xff0c;选择刚才配置的桥接模式 静态ip设置&#xff1a; 我用的ubuntu24桌…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...