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已升级,新版Elasticsearch keyword博客参考下面这篇【Elasticsearch教程8】Mapping字段类型之keyword_elasticsearch的keyword_亚瑟弹琴的博客-CSDN博客 1 前言 本文基于ES7.6,如果是之前版本,是有区别的。 ES支持的字段类型很…...
LeetCode算法复杂度分析(时间复杂度空间复杂度)
文章目录前言时间复杂度1.概述2.大O记法3.常见类型空间复杂度1.概述2.常见类型典型算法的复杂度分析1.递归算法2.哈希表前言 我们知道,研究算法的最终目的就是如何花更少的时间,如何占用更少的内存去完成相同的需求。 时间复杂度 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.排序算法之一:冒泡排序
排序算法稳定性假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]r[j],且r[i]在r[j]之前,而在排序后的序列中,r[…...
python自学之《21天学通Python》(16)——第19章 用Pillow库处理图片
Pillow是Python2.X时代比较流行的Python ImagingLibrary(简称Pillow)图像处理库的分支,并修复了一些bug。Pillow提供了对Python3的支持,为Python3解释器提供了图像处理的功能。和Pillow库一样提供了广泛的文件格式支持、高效的内部…...
发布依赖到maven仓库
maven中央仓库是一个开放的仓库,所以我们也可以把自己开发的jar推送到远程仓库,这样可以直接引入pom依赖使用我们的库。 准备工作 ● 需要一个github账号(程序员必备) ● 网络代理(涉及到的网站通常没版本在国内直接访…...
Laravel-admin之自定义操作日志
laravel-admin是封装性极好的框架,自带的就有操作日志的记录,但是对于非开发人员可能看不懂这个日志,所以就想着给修改一下,以谁修改了什么,谁删除了什么,谁审核了什么,谁添加了什么类似&#x…...
用Python做了一个法律查询小工具,非常好用
用Python做了一个法律查询小工具,非常好用效果展示准备工作不会的话可以点我直达代码和视频讲解,我都准备好了主要代码哈喽兄弟,今天给大家分享一个Python tkinter制作法律查询小工具。 光爬虫大家也只能自己用用,就算打包了exe&…...
工作篇:触摸屏原理介绍
一、触摸屏概述 触摸屏作为一种新的输入设备,它是目前最简单、方便、自然的一种人机交互方式。 当接触了屏幕上的图形按钮时,屏幕上的触觉反馈系统可根据预先编程的程式驱动各种连结装置,可用以取代机械式的按钮面板,并借由液晶…...
Ep_操作系统面试题-操作系统的分类
答案 单体系统 整个操作系统是以程序集合来编写的,链接在一块形成一个二进制可执行程序,这种系统称为单体系统。 分层系统 每一层都使用下面的层来执行其功能。 微内核 微内核架构的内核只保留最基本的能力,把一些应用放到了用户空间 客户-…...
iframe或document监听滚动事件不起作用
有时候我们会遇到监听iframe或document的滚动事件不起作用的情况,在排除代码写错的情况下,我们应该考虑此时的document是否可以滑动。 1、为什么document不能监听滑动? 就很奇怪,明明页面时有滚动条的,为什么说document不可滑动…...
基频估计算法简介
基频估计算法 F0 estimate methods 估计F0的方法可以分为三类:基于时域、基于频域、或混合方法。本文详细介绍了这些方法。 所有的算法都包含如下三个主要步骤: 1.预处理:滤波,加窗分帧等 2.搜寻:可能的基频值F0(候选…...
linux修改DNS 系统版本Kylin V10桌面版
配置DNS在银河麒麟桌面操作系统V10 SP1 中修改DNS信息,直接修改/etc/resolv.conf文件中的DNS信息,不能生效。应该参考如下步骤:一、首先修改 /etc/systemd/resolved.conf文件,在其中添加DNS信息在终端中执行以下命令:s…...
如何使用 AWS Lambda 运行 selenium
借助 AWS Lambda 运行 selenium 来爬取网络数据。 简介 与手动从网站收集数据相比,爬虫可以为我们节省很多时间,对于爬虫的每次请求而言,这相当于 AWS Lambda 的每次函数的运行。 AWS Lambda 是一种将脚本部署到云的简单且价格低廉的服务&…...
认识Cesium旋转大小变量
前文代码中有如下;矩阵乘以旋转大小,还放入mat; Cesium.Matrix4.multiply(mat, rotationX, mat); 初看以为rotationX是一个数值,因为矩阵可以和数相乘; 但是看它的代码,rotationX是由一长串代码获得的&a…...
异响加持、吐槽声不断,小鹏G9难解困局
小鹏汽车的烦恼就好比红尘中的三千青丝,小鹏G9“惊魂48小时”的恐慌还未平息,车门异响等问题就已经层出不穷,再次将小鹏汽车推上风口浪尖。 可以毫不客气的说,G9承载着小鹏汽车盈利的希望,但在原本处于上升之势的G9却…...
【react】react18的学习
一、安装 $ create-react-app [Project name]默认支持sass 二、核心依赖 react:react 核心 react-dom:用于开发渲染web 应用; react-scripts:封装webpack服务; "start": "react-scripts start&quo…...
Ep_操作系统面试题-什么是线程,线程和进程的区别
1. 一个进程中可以有多个线程,多个线程共享进程的堆和方法区 (JDK1.8 之后的元空间),但是每个线程有自己的程序计数器、虚拟机栈和 本地方法栈。 2.进程是资源分配的最小单位,线程是CPU调度的最小单位 视频讲解: https://edu.csdn.net/course/detail/38090 点我…...
深入解析ZYNQ启动流程:从Boot引脚到FSBL的完整路径
1. ZYNQ启动流程全景概览 当你第一次拿到一块ZYNQ开发板时,按下电源键后究竟发生了什么?这个问题困扰过很多嵌入式开发者。作为Xilinx推出的经典SoC芯片,ZYNQ的启动流程就像一场精心编排的交响乐,每个环节都环环相扣。我当年调试第…...
Tree of Thoughts详解:思维树搜索算法
🌳 多路径探索 | 广度优先 深度优先搜索 | 自我评估 回溯机制 | LangChain实现 | 完整项目代码 📖 什么是Tree of Thoughts? 核心思想 ToT Tree of Thoughts(思维树) 传统LLM: 输入 → 线性思考 → 输出…...
终极指南:如何用decimal.js解决JavaScript高精度计算难题
终极指南:如何用decimal.js解决JavaScript高精度计算难题 【免费下载链接】decimal.js An arbitrary-precision Decimal type for JavaScript 项目地址: https://gitcode.com/gh_mirrors/de/decimal.js 你知道吗?JavaScript在处理小数计算时有一个…...
深耕高性价比多模型聚合平台赛道,这些企业值得重点关注
随着AI大模型的普及,单一模型的适配局限、高成本问题逐渐凸显,多模型聚合平台成为企业降本增效的核心选择。行业报告显示,近6个月国内多模型聚合平台的企业付费用户增速超40%,其中高性价比赛道更是成为竞争焦点。一、高性价比的核…...
HBM高带宽内存:从立体堆叠到2.5D封装的性能革命
1. 从平面到立体:HBM如何重塑内存性能天花板在半导体行业里,我们常把“摩尔定律”挂在嘴边,仿佛性能提升的唯一路径就是晶体管越做越小。但大约十年前,当工艺微缩的红利开始放缓,功耗墙和信号完整性问题日益严峻时&…...
AwaDB:纯Python实现的轻量级本地向量数据库实践指南
1. 项目概述:当向量数据库遇上本地化与轻量化最近在折腾一些AI应用的原型,特别是RAG(检索增强生成)和智能问答系统,发现向量数据库的选择是个绕不开的话题。市面上有Pinecone、Weaviate这样的云服务,也有Mi…...
植物大战僵尸95版下载2026最新版及与原本区别介绍
一、游戏版本简介 植物大战僵尸95版是基于官方原版修改优化的经典改版,也是国内玩家知名度最高、流传最广的怀旧改版之一。该版本保留原版全部关卡、场景、背景音乐以及基础玩法,没有大幅度颠覆原作设定,仅对植物属性、僵尸数值、判定机制进…...
企业级Angular微前端架构中,Claude如何安全介入模块拆分与契约校验(含TS类型推导审计日志)
更多请点击: https://intelliparadigm.com 第一章:企业级Angular微前端架构中Claude介入的边界与安全基线 在企业级 Angular 微前端系统中,将 Claude 类大语言模型(LLM)作为辅助开发工具引入时,必须严格界…...
RC 滤波截止频率与滤波原理详解
一、先搞懂最核心的问题:滤波到底 "滤" 的是什么?滤波不是 "切掉" 某个频率的信号,而是对不同频率的信号进行选择性衰减 **。**我们想要的信号(有用信号):让它尽可能无衰减地通过电路我…...
热成像与计算机视觉融合:打造免提可穿戴交互新范式
1. 项目概述:从一次“意外”到可穿戴交互新范式 在实验室里摆弄新到的热成像相机,这原本只是一个打发时间的“快乐意外”。我的咖啡杯、显示器,甚至是我自己的脸,在热成像镜头下都呈现出有趣的温度图案。但真正让我停下手中咖啡的…...
