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

代码随想录算法训练营第四十九天|121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 II

第九章 动态规划part10

121. 买卖股票的最佳时机

给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润,返回 0 。

思路:记录当前的最低价格,使用当前价格与最低价格之差获取当前最大利润。(使用贪心法)

class Solution {
public:int maxProfit(vector<int>& prices) {int min=INT_MAX;int profit=INT_MIN;for(int i=0;i<prices.size();i++){if(prices[i]<=min)  min=prices[i];if(prices[i]-min>profit)  profit=prices[i]-min;}return profit;}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

 使用动态规划

感觉跟贪心法基本差不多,dp[i][0]其实也相当于找当前的最小买入价格,dp[i][1]则相当于找目前能够卖出的最大价格,只是采用了状态转移方式来解决。

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,0));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.size();i++){dp[i][0]=max(dp[i-1][0],-prices[i]);dp[i][1]=max(dp[i-1][1],prices[i]+dp[i-1][0]);}return dp[prices.size()-1][1];}
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(n)

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

给你一个整数数组 prices ,其中 prices[i] 表示某支股票第 i 天的价格。

在每一天,你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买,然后在 同一天 出售。

返回 你能获得的 最大 利润 。

本题思路与上一题基本一致,不同之处在于递推公式:

dp含义与上一题相同:

dp[i][0]:第i天持有股票所得最多现金;

dp[i][1]:第i天不持有股票所得最多现金;

递推公式推导:

dp[i][0]:第i天持有股票由两种状态转移可以得到:

①第i-1天持有股票且第i天不卖出;

②第i-1天不持有股票且第i天买入;

dp[i][1]:第i天持有股票可有两种状态转移得到:

①第i-1天不持有股票且第i天不买入,

②第i-1天持有股票且第i天卖出。

class Solution {
public:int maxProfit(vector<int>& prices) {vector<vector<int>> dp(prices.size(),vector<int>(2,0));dp[0][0]=-prices[0];dp[0][1]=0;for(int i=1;i<prices.size();i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);}return dp[prices.size()-1][1];}
};

 这两道题充分感受到了状态转移,使用动态规划一定要想好递推公式代表的是什么状态的转移。

 

相关文章:

代码随想录算法训练营第四十九天|121. 买卖股票的最佳时机、122. 买卖股票的最佳时机 II

第九章 动态规划part10 121. 买卖股票的最佳时机 给定一个数组 prices &#xff0c;它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票&#xff0c;并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最…...

Rust教程6:并发编程和线程通信

文章目录 线程初步join方法线程通信 Rust系列&#xff1a;初步⚙所有权⚙结构体和枚举类⚙函数进阶⚙泛型和特征 线程初步 在Rust中&#xff0c;开启多线程进行并发编程&#xff0c;只需调用thread::spawn&#xff0c;但这里有一个坑点&#xff0c;即spawn函数只有一个传入参…...

JVM在线分析-监控工具(jps, jstat, jstatd)

参考官方文档&#xff08;jdk11&#xff09; https://docs.oracle.com/en/java/javase/11/tools/troubleshooting-tools-and-commands.html#GUID-CB44BFBA-E5F9-4D80-8EE8-28E9F16BC451 1. 监控工具(jps, jstat, jstatd) jps -q Suppresses the output of the class name, J…...

Console LDAP 配置解密

之前通过短视频向大家介绍了 Console 如何集成 LDAP&#xff0c;但很多小伙伴反映按照视频里的配置后不成功。今天就结合小伙伴们反映的问题来跟大家详细介绍一下。 Console LDAP 完整的配置参数如下&#xff1a; 名称类型说明hoststringLDAP 服务器地址portintLDAP 服务器端口…...

node插件MongoDB(三)—— 库mongoose 的使用和数据类型(一)

前言 提示&#xff1a;使用mongoose 的前提是你安装了node和 MongoDB。 mongoose 官网文档&#xff1a;http://mongoosejs.net/docs/index.html 文章目录 前言一、安装二、基本使用1. 打开bin目录的mongod.exe文件2. 基本使用的代码&#xff08;连接mongodb 服务&#xff09;3.…...

基础(二)

基础&#xff08;二&#xff09; 字符串型 C风格&#xff1a;char 变量名[] “字符串值”&#xff1b; C风格&#xff1a;string 变量名 “字符串值” #include <iostream> using namespace std; #include <string>int main() {// C风格char str1[] "h…...

思维模型 目标效应

本系列文章 主要是 分享 思维模型&#xff0c;涉及各个领域&#xff0c;重在提升认知。明确目标&#xff0c;激发内在动机。 1 目标效应的应用 1.1 目标效应在教育领域的应用-棉花糖实验 美国斯坦福大学心理学系的教授米歇尔&#xff08;Walter Mischel&#xff09;曾经进行了…...

【从0到1设计一个网关】性能优化---Netty线程数配置与JVM参数配置

文章目录 Netty线程介绍Netty实战配置JVM参数与ZGCJVM与ZGC调优Netty线程介绍 在Netty中有两个比较重要的线程概念,一个是BOSS线程,一个是Woker线程。 Boss线程组: Boss线程组通常负责处理接受客户端连接的工作,即处理ServerSocketChannel的连接事件。 Boss线程会监听并接…...

node插件MongoDB(五)—— 库mongoose 的模块化(五)

文章目录 一、使用mongoose 模块化的原因二、准备工作2. 启动mongo.exe 和mongod.exe 两个程序连接数据库 三、基本模块的拆分1、基本逻辑2、代码3、代码图示说明 四、在index.js 中进一步的拆分1.拆分原因2.新建model文件夹存储文档的结构对象3.代码4.代码实际演示和注意点 一…...

Windows server 2008 R2 IIS搭建ASP网站教程

一、安装应用程序服务器 提示安装成功 二、添加角色服务asp 三、asp网站配置 放入源码 设置网站首页为index.asp: 设置应用程序池 四、设置网站目录属性 五、access数据库连接配置 Cd c:\Windows\System32\inetsrv appcmd list apppool /xml | appcmd set apppool /…...

Linux之基础开发工具gdb调试器的使用(三)

文章目录 一、Linux调试器-gdb使用1、安装gdb2、背景3、Debug和release4、区分Debug和release 二、Linux调试器-gdb命令演示1、显示指定行之后的代码&#xff08;自动记录最后一条指令&#xff09;2、断点1、打印断点2、查看断点3、删除断点4、使能&#xff08;禁用/开启&#…...

advanced-css: No.1

本套教程学习来自视频&#xff1a;https://www.bilibili.com/video/BV1n94y1o7yS/?p7&spm_id_frompageDriver&vd_sourceb79be8283df9418cb45941cc0bd583c6 案例 实现效果图 代码 HTML: <!DOCTYPE html> <html lang"en"><head><meta c…...

最新宝塔面板第三方云端站点程序源码/第三方宝塔面板PHP源码/全开源ThinkPHP框架

源码简介&#xff1a; 实现宝塔面板第三方云端站点程序源码,这个是第三方宝塔面板 btcloud PHP源码&#xff0c;它还有云端使用记录、IP黑白名单、定时任务等功能。 这是一个使用PHP开发的宝塔面板第三方云端站点程序。 您可以利用此程序搭建属于自己的宝塔面板第三方云端&a…...

【Unity之UI编程】玩法面板的实现

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;UI_…...

栈和队列:栈

栈的概念&#xff1a; 栈&#xff1a; 一种特殊的线性表&#xff0c;其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶&#xff0c;另一端称为栈底。 栈中的数据元素遵守后进先出LIFO&#xff08;Last In First Out&#xff09;的原则。…...

由浅入深学习统计学 - 常用统计图形学习

学习笔记 第一章- 信息图形化 图形化&#xff08;可视化&#xff09; 在一堆数据中&#xff0c;自己发现了这些数据的规律&#xff0c;但是无法表述给其他人知道&#xff0c;图形化就是便于他人理解数据的规律的展示的手段。 或者说我们也可以从统计的数据图形中发现某些没有…...

【java进阶】集合的三种遍历(迭代器、增强for、Lambda)

目录 一、先谈集合&#xff1a; 二、单列集合的三种遍历方式 迭代器遍历 增强for遍历 Lambda表达式遍历 一、先谈集合&#xff1a; &#x1f525;那我们平常用for循环依赖下标遍历不行嘛&#xff0c;这就与集合的分类有关了。 集合的体系结构&#xff1a; collection是单…...

Qt实现动态桌面小精灵(含源码)

目录 一、设计思路 二、部分源码演示 三、源码地址 🌈write in front🌈 🧸大家好,我是三雷科技.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由三雷科技原创 CSDN首发🐒 如需转载还请通知⚠️ 📝个人主页:三雷科技🧸—CSDN博客 🎁欢…...

Qt 自定义分页控件

目录 前言1、功能描述2、代码实现2.1 ui文件2.1 头文件2.2 源码文件2.3 设计思路 4、示例5、总结 前言 在应用程序开发时经常会遇到数据分页的需求&#xff0c;每一页展示特定数量的数据&#xff0c;通过点击按钮翻页或者输入页码跳转到指定页。 本文介绍一个自定义分页控件&a…...

Java中的7大设计原则

在面向对象的设计过程中&#xff0c;首先需要考虑的是如何同时提高一个软件系统的可维护性和可复用性。这时&#xff0c;遵从面向对象的设计原则&#xff0c;可以在进行设计方案时减少错误设计的产生&#xff0c;从不同的角度提升一个软件结构的设计水平。 1、单一职责 一个类…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件

今天呢&#xff0c;博主的学习进度也是步入了Java Mybatis 框架&#xff0c;目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学&#xff0c;希望能对大家有所帮助&#xff0c;也特别欢迎大家指点不足之处&#xff0c;小生很乐意接受正确的建议&…...

条件运算符

C中的三目运算符&#xff08;也称条件运算符&#xff0c;英文&#xff1a;ternary operator&#xff09;是一种简洁的条件选择语句&#xff0c;语法如下&#xff1a; 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true&#xff0c;则整个表达式的结果为“表达式1”…...

cf2117E

原题链接&#xff1a;https://codeforces.com/contest/2117/problem/E 题目背景&#xff1a; 给定两个数组a,b&#xff0c;可以执行多次以下操作&#xff1a;选择 i (1 < i < n - 1)&#xff0c;并设置 或&#xff0c;也可以在执行上述操作前执行一次删除任意 和 。求…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝

目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为&#xff1a;一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...