代码随想录算法训练营第四十九天|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 ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。 你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最…...
Rust教程6:并发编程和线程通信
文章目录 线程初步join方法线程通信 Rust系列:初步⚙所有权⚙结构体和枚举类⚙函数进阶⚙泛型和特征 线程初步 在Rust中,开启多线程进行并发编程,只需调用thread::spawn,但这里有一个坑点,即spawn函数只有一个传入参…...
JVM在线分析-监控工具(jps, jstat, jstatd)
参考官方文档(jdk11) 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,但很多小伙伴反映按照视频里的配置后不成功。今天就结合小伙伴们反映的问题来跟大家详细介绍一下。 Console LDAP 完整的配置参数如下: 名称类型说明hoststringLDAP 服务器地址portintLDAP 服务器端口…...
node插件MongoDB(三)—— 库mongoose 的使用和数据类型(一)
前言 提示:使用mongoose 的前提是你安装了node和 MongoDB。 mongoose 官网文档:http://mongoosejs.net/docs/index.html 文章目录 前言一、安装二、基本使用1. 打开bin目录的mongod.exe文件2. 基本使用的代码(连接mongodb 服务)3.…...
基础(二)
基础(二) 字符串型 C风格:char 变量名[] “字符串值”; C风格:string 变量名 “字符串值” #include <iostream> using namespace std; #include <string>int main() {// C风格char str1[] "h…...
思维模型 目标效应
本系列文章 主要是 分享 思维模型,涉及各个领域,重在提升认知。明确目标,激发内在动机。 1 目标效应的应用 1.1 目标效应在教育领域的应用-棉花糖实验 美国斯坦福大学心理学系的教授米歇尔(Walter Mischel)曾经进行了…...
【从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、显示指定行之后的代码(自动记录最后一条指令)2、断点1、打印断点2、查看断点3、删除断点4、使能(禁用/开启&#…...
advanced-css: No.1
本套教程学习来自视频:https://www.bilibili.com/video/BV1n94y1o7yS/?p7&spm_id_frompageDriver&vd_sourceb79be8283df9418cb45941cc0bd583c6 案例 实现效果图 代码 HTML: <!DOCTYPE html> <html lang"en"><head><meta c…...
最新宝塔面板第三方云端站点程序源码/第三方宝塔面板PHP源码/全开源ThinkPHP框架
源码简介: 实现宝塔面板第三方云端站点程序源码,这个是第三方宝塔面板 btcloud PHP源码,它还有云端使用记录、IP黑白名单、定时任务等功能。 这是一个使用PHP开发的宝塔面板第三方云端站点程序。 您可以利用此程序搭建属于自己的宝塔面板第三方云端&a…...
【Unity之UI编程】玩法面板的实现
👨💻个人主页:元宇宙-秩沅 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 秩沅 原创 👨💻 收录于专栏:UI_…...
栈和队列:栈
栈的概念: 栈: 一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端 称为栈顶,另一端称为栈底。 栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。…...
由浅入深学习统计学 - 常用统计图形学习
学习笔记 第一章- 信息图形化 图形化(可视化) 在一堆数据中,自己发现了这些数据的规律,但是无法表述给其他人知道,图形化就是便于他人理解数据的规律的展示的手段。 或者说我们也可以从统计的数据图形中发现某些没有…...
【java进阶】集合的三种遍历(迭代器、增强for、Lambda)
目录 一、先谈集合: 二、单列集合的三种遍历方式 迭代器遍历 增强for遍历 Lambda表达式遍历 一、先谈集合: 🔥那我们平常用for循环依赖下标遍历不行嘛,这就与集合的分类有关了。 集合的体系结构: collection是单…...
Qt实现动态桌面小精灵(含源码)
目录 一、设计思路 二、部分源码演示 三、源码地址 🌈write in front🌈 🧸大家好,我是三雷科技.希望你看完之后,能对你有所帮助,不足请指正!共同学习交流. 🆔本文由三雷科技原创 CSDN首发🐒 如需转载还请通知⚠️ 📝个人主页:三雷科技🧸—CSDN博客 🎁欢…...
Qt 自定义分页控件
目录 前言1、功能描述2、代码实现2.1 ui文件2.1 头文件2.2 源码文件2.3 设计思路 4、示例5、总结 前言 在应用程序开发时经常会遇到数据分页的需求,每一页展示特定数量的数据,通过点击按钮翻页或者输入页码跳转到指定页。 本文介绍一个自定义分页控件&a…...
Java中的7大设计原则
在面向对象的设计过程中,首先需要考虑的是如何同时提高一个软件系统的可维护性和可复用性。这时,遵从面向对象的设计原则,可以在进行设计方案时减少错误设计的产生,从不同的角度提升一个软件结构的设计水平。 1、单一职责 一个类…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
高防服务器价格高原因分析
高防服务器的价格较高,主要是由于其特殊的防御机制、硬件配置、运营维护等多方面的综合成本。以下从技术、资源和服务三个维度详细解析高防服务器昂贵的原因: 一、硬件与技术投入 大带宽需求 DDoS攻击通过占用大量带宽资源瘫痪目标服务器,因此…...
Vue 3 + WebSocket 实战:公司通知实时推送功能详解
📢 Vue 3 WebSocket 实战:公司通知实时推送功能详解 📌 收藏 点赞 关注,项目中要用到推送功能时就不怕找不到了! 实时通知是企业系统中常见的功能,比如:管理员发布通知后,所有用户…...
高抗扰度汽车光耦合器的特性
晶台光电推出的125℃光耦合器系列产品(包括KL357NU、KL3H7U和KL817U),专为高温环境下的汽车应用设计,具备以下核心优势和技术特点: 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计,确保在…...
SFTrack:面向警务无人机的自适应多目标跟踪算法——突破小尺度高速运动目标的追踪瓶颈
【导读】 本文针对无人机(UAV)视频中目标尺寸小、运动快导致的多目标跟踪难题,提出一种更简单高效的方法。核心创新在于从低置信度检测启动跟踪(贴合无人机场景特性),并改进传统外观匹配算法以关联此类检测…...
Redis专题-实战篇一-基于Session和Redis实现登录业务
GitHub项目地址:https://github.com/whltaoin/redisLearningProject_hm-dianping 基于Session实现登录业务功能提交版本码:e34399f 基于Redis实现登录业务提交版本码:60bf740 一、导入黑马点评后端项目 项目架构图 1. 前期阶段2. 后续阶段导…...
CKA考试知识点分享(2)---ingress
CKA 版本:1.32 第二题是涉及ingress相关。本文不是题目,只是为了学习相关知识点做的实验。 1. 环境准备 需要准备一套K8S集群。 1.1 安装ingress-nginx 下载deploy文件: wget -O controller-v1.12.2.yaml https://raw.githubusercontent…...
【人工智能 | 项目开发】Python Flask实现本地AI大模型可视化界面
文末获取项目源码。 文章目录 项目背景项目结构app.py(后端服务)index.html(前端界面)项目运行项目图示项目源码项目背景 随着人工智能技术的快速发展,大语言模型在智能交互领域展现出巨大潜力。本项目基于 Qwen3-1.7B 模型,搭建一个轻量化的智能聊天助手,旨在为用户提…...
从入门到实战:AI学习路线全解析——避坑指南
分享一下阿里的人工智能学习路线,为感兴趣系统学习的小伙伴们探路。 一、谁适合学这门AI课程?五类人群的精准定位 无论你是零基础小白还是职场转型者,这套系统化课程都能为你量身定制成长路径: 零基础爱好者(无编程/数学背景) 课程提供Python和数学前置学习建议,先补基…...
