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

Leetcode DAY 49~50:买卖股票的最佳时机 1 2 3 4

  • 121. 买卖股票的最佳时机

1、贪心算法

class Solution {
public:int maxProfit(vector<int>& prices) {//贪心int low = INT_MAX;int res = 0;for(int i = 0; i < prices.size(); i++) {low = min(low, prices[i]); //左最小价格res = max(res, prices[i] - low); //当前-左最小的max}return res;}
};

2、动态规划

dp[i][0]表示第i天持有股票最大现金 -> max(前一天持有股票的最大现金, 前一天买入股票的现金)
dp[i][1]表示第i天不持有股票最大现金 -> max(前一天不持有股票最大现金, 前一天持有第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], -prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);}return dp[prices.size() - 1][1];}
};

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

1、dp

dp[i][0]表示第i天持有股票时的所的现金

dp[i][1]表示第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])

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2,0));dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1; i < n; 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[n - 1][1];}
};

2、其他

class Solution:def maxProfit(self, prices: List[int]) -> int:res = 0for i in range(1, len(prices)):if prices[i] - prices[i - 1] > 0:res += prices[i] - prices[i - 1]return res
  • 123.买卖股票的最佳时机III

!最多可以完成两笔交易!

1、递推公式

dp[i][0] 第一次持有的现金 <--- dp[i - 1][0]     - prices[i] 

dp[i][1] 第一次不持有的现金 <--- dp[i - 1][1]     dp[i - 1][0] + prices[i]

dp[i][2] 第二次持有的现金  <---  dp[i - 1][2]    dp[i - 1][1] - prices[i]

dp[i][3] 第二次不持有的现金 <--- dp[i - 1][3]    dp[i - 1][2] + prices[i]

2、初始化

dp[0][0] = -prices[0]

dp[0][1] = 0

dp[0][2] = -prices[0]

dp[0][3] = 0

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if(n == 0)return 0;vector<vector<int>> dp(n, vector<int>(4, 0));dp[0][0] = -prices[0];dp[0][2] = -prices[0];for(int i = 1; i < n; i++) {dp[i][0] = max(dp[i - 1][0], -prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] - prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] + prices[i]);}return dp[n - 1][3];}
};
  • 188.买卖股票的最佳时机IV

通过上一题 类比得到

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2 * k + 1, 0));for(int i = 1; i <= 2*k; i += 2){dp[0][i] = - prices[0];}for(int i = 1; i < n; i++) {for(int j = 1; j <= 2 * k; j++) {dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + (1 - 2 * (j % 2)) * prices[i]);//1 - 2 * (j % 2)用来区分 奇数和偶数}}return dp[n - 1][2 *k];}
};

相关文章:

Leetcode DAY 49~50:买卖股票的最佳时机 1 2 3 4

121. 买卖股票的最佳时机 1、贪心算法 class Solution { public:int maxProfit(vector<int>& prices) {//贪心int low INT_MAX;int res 0;for(int i 0; i < prices.size(); i) {low min(low, prices[i]); //左最小价格res max(res, prices[i] - low); //当前…...

Android Handler机制(二) Handler 实现原理

一. 前言 接上一篇文章为什么设计Handler , 我们来继续讲解一下Handler的实现原理, 俗话说一个好汉三个帮, 接下来一步一步引入各个主角,并说明它们在Handler机制中扮演的角色和作用. 二. Handler实现原理 首先我们先确定一个结论: 使用 Handler 是希望它被实例化在哪个线程&a…...

Elasticsearch教程(19) 详解mapping之keyword

Elasticsearch已升级&#xff0c;新版Elasticsearch keyword博客参考下面这篇【Elasticsearch教程8】Mapping字段类型之keyword_elasticsearch的keyword_亚瑟弹琴的博客-CSDN博客 1 前言 本文基于ES7.6&#xff0c;如果是之前版本&#xff0c;是有区别的。 ES支持的字段类型很…...

LeetCode算法复杂度分析(时间复杂度空间复杂度)

文章目录前言时间复杂度1.概述2.大O记法3.常见类型空间复杂度1.概述2.常见类型典型算法的复杂度分析1.递归算法2.哈希表前言 我们知道&#xff0c;研究算法的最终目的就是如何花更少的时间&#xff0c;如何占用更少的内存去完成相同的需求。 时间复杂度 1.概述 我们要计算算…...

Android OpenCV(七十三):吊打高斯模糊的StackBlur Android 实践

前言 OpenCV 4.7.0 2022年12月28日Release,ChangeLog中提到 Stackblur algorithm implementation. Stackblur是一种高斯模糊的快速近似,由Mario Klingemann发明。其计算耗时不会随着kernel size的增大而增加,专为大kernel size的模糊滤波场景量身定制。 使用建议:当kerne…...

4.排序算法之一:冒泡排序

排序算法稳定性假定在待排序的记录序列中&#xff0c;存在多个具有相同的关键字的记录&#xff0c;若经过排序&#xff0c;这些记录的相对次序保持不变&#xff0c;即在原序列中&#xff0c;r[i]r[j]&#xff0c;且r[i]在r[j]之前&#xff0c;而在排序后的序列中&#xff0c;r[…...

python自学之《21天学通Python》(16)——第19章 用Pillow库处理图片

Pillow是Python2.X时代比较流行的Python ImagingLibrary&#xff08;简称Pillow&#xff09;图像处理库的分支&#xff0c;并修复了一些bug。Pillow提供了对Python3的支持&#xff0c;为Python3解释器提供了图像处理的功能。和Pillow库一样提供了广泛的文件格式支持、高效的内部…...

发布依赖到maven仓库

maven中央仓库是一个开放的仓库&#xff0c;所以我们也可以把自己开发的jar推送到远程仓库&#xff0c;这样可以直接引入pom依赖使用我们的库。 准备工作 ● 需要一个github账号&#xff08;程序员必备&#xff09; ● 网络代理&#xff08;涉及到的网站通常没版本在国内直接访…...

Laravel-admin之自定义操作日志

laravel-admin是封装性极好的框架&#xff0c;自带的就有操作日志的记录&#xff0c;但是对于非开发人员可能看不懂这个日志&#xff0c;所以就想着给修改一下&#xff0c;以谁修改了什么&#xff0c;谁删除了什么&#xff0c;谁审核了什么&#xff0c;谁添加了什么类似&#x…...

用Python做了一个法律查询小工具,非常好用

用Python做了一个法律查询小工具&#xff0c;非常好用效果展示准备工作不会的话可以点我直达代码和视频讲解&#xff0c;我都准备好了主要代码哈喽兄弟&#xff0c;今天给大家分享一个Python tkinter制作法律查询小工具。 光爬虫大家也只能自己用用&#xff0c;就算打包了exe&…...

工作篇:触摸屏原理介绍

一、触摸屏概述 触摸屏作为一种新的输入设备&#xff0c;它是目前最简单、方便、自然的一种人机交互方式。 当接触了屏幕上的图形按钮时&#xff0c;屏幕上的触觉反馈系统可根据预先编程的程式驱动各种连结装置&#xff0c;可用以取代机械式的按钮面板&#xff0c;并借由液晶…...

Ep_操作系统面试题-操作系统的分类

答案 单体系统 整个操作系统是以程序集合来编写的&#xff0c;链接在一块形成一个二进制可执行程序&#xff0c;这种系统称为单体系统。 分层系统 每一层都使用下面的层来执行其功能。 微内核 微内核架构的内核只保留最基本的能力&#xff0c;把一些应用放到了用户空间 客户-…...

iframe或document监听滚动事件不起作用

有时候我们会遇到监听iframe或document的滚动事件不起作用的情况&#xff0c;在排除代码写错的情况下&#xff0c;我们应该考虑此时的document是否可以滑动。 1、为什么document不能监听滑动? 就很奇怪&#xff0c;明明页面时有滚动条的&#xff0c;为什么说document不可滑动…...

基频估计算法简介

基频估计算法 F0 estimate methods 估计F0的方法可以分为三类:基于时域、基于频域、或混合方法。本文详细介绍了这些方法。 所有的算法都包含如下三个主要步骤&#xff1a; 1.预处理&#xff1a;滤波&#xff0c;加窗分帧等 2.搜寻&#xff1a;可能的基频值F0&#xff08;候选…...

linux修改DNS 系统版本Kylin V10桌面版

配置DNS在银河麒麟桌面操作系统V10 SP1 中修改DNS信息&#xff0c;直接修改/etc/resolv.conf文件中的DNS信息&#xff0c;不能生效。应该参考如下步骤&#xff1a;一、首先修改 /etc/systemd/resolved.conf文件&#xff0c;在其中添加DNS信息在终端中执行以下命令&#xff1a;s…...

如何使用 AWS Lambda 运行 selenium

借助 AWS Lambda 运行 selenium 来爬取网络数据。 简介 与手动从网站收集数据相比&#xff0c;爬虫可以为我们节省很多时间&#xff0c;对于爬虫的每次请求而言&#xff0c;这相当于 AWS Lambda 的每次函数的运行。 AWS Lambda 是一种将脚本部署到云的简单且价格低廉的服务&…...

认识Cesium旋转大小变量

前文代码中有如下&#xff1b;矩阵乘以旋转大小&#xff0c;还放入mat&#xff1b; Cesium.Matrix4.multiply(mat, rotationX, mat); 初看以为rotationX是一个数值&#xff0c;因为矩阵可以和数相乘&#xff1b; 但是看它的代码&#xff0c;rotationX是由一长串代码获得的&a…...

异响加持、吐槽声不断,小鹏G9难解困局

小鹏汽车的烦恼就好比红尘中的三千青丝&#xff0c;小鹏G9“惊魂48小时”的恐慌还未平息&#xff0c;车门异响等问题就已经层出不穷&#xff0c;再次将小鹏汽车推上风口浪尖。 可以毫不客气的说&#xff0c;G9承载着小鹏汽车盈利的希望&#xff0c;但在原本处于上升之势的G9却…...

【react】react18的学习

一、安装 $ create-react-app [Project name]默认支持sass 二、核心依赖 react&#xff1a;react 核心 react-dom&#xff1a;用于开发渲染web 应用&#xff1b; react-scripts&#xff1a;封装webpack服务&#xff1b; "start": "react-scripts start&quo…...

Ep_操作系统面试题-什么是线程,线程和进程的区别

1. 一个进程中可以有多个线程,多个线程共享进程的堆和方法区 (JDK1.8 之后的元空间),但是每个线程有自己的程序计数器、虚拟机栈和 本地方法栈。 2.进程是资源分配的最小单位&#xff0c;线程是CPU调度的最小单位 视频讲解: https://edu.csdn.net/course/detail/38090 点我…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

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

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文全面剖析RNN核心原理&#xff0c;深入讲解梯度消失/爆炸问题&#xff0c;并通过LSTM/GRU结构实现解决方案&#xff0c;提供时间序列预测和文本生成…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

JDK 17 序列化是怎么回事

如何序列化&#xff1f;其实很简单&#xff0c;就是根据每个类型&#xff0c;用工厂类调用。逐个完成。 没什么漂亮的代码&#xff0c;只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...