leetcode-买卖股票问题
309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode)
动态规划解题思路:
1、暴力递归(难点如何定义递归函数)
2、记忆化搜索-傻缓存法(根据暴力递归可变参数确定缓存数组维度)
3、严格表结构依赖的动态规划
4、进一步优化(斜率优化、空间优化),非必须
一、分析:假设[0,index-1]之前的最大利润已经知道,现在计算到了index位置的最大利润。根据题意,到index位置后可能有三种状态,买入、卖出、冷冻。所以递归函数如下。
public int maxProfit(int[] prices) {return p(prices,0,0);}// 0-买入 1-卖出 2-冷冻// 递归函数表示 从index位置到prices.length-1位置的最大利润public int p(int[] prices, int index, int state) {if (index == prices.length) {return 0;}int res = 0;if (state == 0) {// 买入 当前indexint p1 = -prices[index] + p(prices, index + 1, 1);// 不买当前indexint p2 = p(prices, index + 1, 0);return Math.max(p1, p2);} else if (state == 1) {// 卖当前indexint p1 = prices[index] + p(prices, index + 1, 2);// 不卖当前indexint p2 = p(prices, index + 1, 1);return Math.max(p1, p2);} else {//冷冻return p(prices, index + 1, 0);}}
二、我们直接看表依赖,略过傻缓存法。根据暴力递归函数分析,有两个可变参数,所以申请一个二维数组即可,看递归的base case初始化dp数组;看依赖关系index位置只依赖于index+1位置的元素,所以填数组的顺序为index倒序。返回值看递归调用的参数值是什么,就返回dp数组哪个位置的值。
public int maxProfit2(int[] prices) {int N = prices.length;int[][] dp = new int[N + 1][3];for (int index = N - 1; index >= 0; index--) {dp[index][2] = dp[index + 1][0];dp[index][1] = Math.max(prices[index] + dp[index + 1][2], dp[index + 1][1]);dp[index][0] = Math.max(-prices[index] + dp[index][1], dp[index + 1][0]);}return dp[0][0];}
三、我们分析知道index位置只依赖于index+1位置的元素,也就是说index行的数据只依赖index+1行的数据,所以可以只用一个一维数组,循环更新即可。
public int maxProfit(int[] prices) {int N = prices.length;//空间优化int[] dp = new int[3];for (int index = N - 1; index >= 0; index--) {int temp = dp[0];dp[0] = Math.max(-prices[index] + dp[1], dp[0]);dp[1] = Math.max(prices[index] + dp[2], dp[1]);dp[2] = temp;}return dp[0];}
714. 买卖股票的最佳时机含手续费 - 力扣(LeetCode)
该题的解法和上题类似,只是多了手续费,少了冷冻期。
一、暴力递归
int f=0;public int maxProfit1(int[] prices, int fee) {f = fee;return p(prices, 0, 0);}// 0-买入 1-卖出public int p(int[] prices, int index, int state) {if (index == prices.length) {return 0;}int res = 0;if (state == 0) {// 买入 当前indexint p1 = -prices[index] - f + p(prices, index + 1, 1);// 不买当前indexint p2 = p(prices, index + 1, 0);return Math.max(p1, p2);} else {// 可以卖int p1 = prices[index] + p(prices, index + 1, 0);int p2 = p(prices, index + 1, 1);return Math.max(p1, p2);}}
二、表结构动态规划
public int maxProfit2(int[] prices, int fee) {int N = prices.length;int[][] dp = new int[N + 1][2];for (int index = N - 1; index >= 0; index--) {dp[index][1] = Math.max(prices[index] + dp[index + 1][0], dp[index + 1][1]);dp[index][0] = Math.max(-prices[index] - fee + dp[index][1], dp[index + 1][0]);}return dp[0][0];}
三、空间优化
public int maxProfit4(int[] prices, int fee) {int N = prices.length;// 空间优化int buy=0,sell=0;for (int index = N - 1; index >= 0; index--) {int temp = buy;buy = Math.max(-prices[index] - fee + sell, buy);sell = Math.max(prices[index] + temp, sell);}return buy;}public int maxProfit3(int[] prices, int fee) {int N = prices.length;// 空间优化int[] dp = new int[2];for (int index = N - 1; index >= 0; index--) {int temp = dp[0];dp[0] = Math.max(-prices[index] - fee + dp[1], dp[0]);dp[1] = Math.max(prices[index] + temp, dp[1]);}return dp[0];}
123. 买卖股票的最佳时机 III - 力扣(LeetCode)
该题的差异在于:没有冷冻期、没有手续费,但是限制了交易次数,也就是说我们的可变参数需要再加一个交易次数即可。
一、暴力递归
public int maxProfit1(int[] prices) {return p(prices, 0, 0, 0);}public int p(int[] prices, int index, int state, int count) {if (index == prices.length) {return 0;}if (count == 2) {return 0;}int p1 = 0, p2 = 0;if (state == 0) {// buyp1 = -prices[index] + p(prices, index + 1, 1, count);p2 = p(prices, index + 1, 0, count);} else {// 卖出p1 = prices[index] + p(prices, index + 1, 0, count + 1);p2 = p(prices, index + 1, 1, count);}return Math.max(p1, p2);}
二、动态规划
public int maxProfit2(int[] prices) {int N = prices.length;// state countint[][][] dp = new int[N + 1][2][3];for (int index = N - 1; index >= 0; index--) {for (int count = 1; count >= 0; count--) {dp[index][0][count] = Math.max(-prices[index] + dp[index + 1][1][count], dp[index + 1][0][count]);dp[index][1][count] = Math.max(prices[index] + (count + 1 == 2 ? 0 : dp[index + 1][0][count + 1]),dp[index + 1][1][count]);}}return dp[0][0][0];}
三、空间优化(从下至上逐步优化到最优的maxProfit5)
public int maxProfit5(int[] prices) {int N = prices.length;// state countint buy1 = 0;int sell1 = 0;int buy2 = 0;int sell2 = 0;for (int index = N - 1; index >= 0; index--) {buy2 = Math.max(-prices[index] + sell2, buy2);sell2 = Math.max(prices[index], sell2);buy1 = Math.max(-prices[index] + sell1, buy1);sell1 = Math.max(prices[index] + buy2, sell1);}return buy1;}public int maxProfit4(int[] prices) {int N = prices.length;// state count dp[0][0] 买1 dp[0][1]买2 dp[1][0]卖1 dp[1][1] 卖2int[][] dp = new int[2][3];for (int index = N - 1; index >= 0; index--) {dp[0][1] = Math.max(-prices[index] + dp[1][1], dp[0][1]);dp[1][1] = Math.max(prices[index], dp[1][1]);dp[0][0] = Math.max(-prices[index] + dp[1][0], dp[0][0]);dp[1][0] = Math.max(prices[index] + dp[0][1], dp[1][0]);}return dp[0][0];}public int maxProfit3(int[] prices) {int N = prices.length;// state countint[][] dp = new int[2][3];for (int index = N - 1; index >= 0; index--) {for (int count = 1; count >= 0; count--) {dp[0][count] = Math.max(-prices[index] + dp[1][count], dp[0][count]);dp[1][count] = Math.max(prices[index] + (count + 1 == 2 ? 0 : dp[0][count + 1]), dp[1][count]);}}return dp[0][0];}
188. 买卖股票的最佳时机 IV - 力扣(LeetCode)
该题解法和上题类似,只是交易次数为k。
一、暴力递归
int times=0;public int maxProfit1(int k, int[] prices) {times = k;return p(prices, 0, 0, 0);}public int p(int[] prices, int index, int state, int count) {if (index == prices.length) {return 0;}if (count == times) {return 0;}int p1 = 0, p2 = 0;if (state == 0) {// buyp1 = -prices[index] + p(prices, index + 1, 1, count);p2 = p(prices, index + 1, 0, count);} else {// 卖出p1 = prices[index] + p(prices, index + 1, 0, count + 1);p2 = p(prices, index + 1, 1, count);}return Math.max(p1, p2);}
二、动态规划
public int maxProfit(int k, int[] prices) {int N = prices.length;// state countint[][] dp = new int[2][k];for (int index = N - 1; index >= 0; index--) {for (int count = k - 1; count >= 0; count--) {dp[0][count] = Math.max(-prices[index] + dp[1][count], dp[0][count]);dp[1][count] = Math.max(prices[index] + (count + 1 == k ? 0 : dp[0][count + 1]), dp[1][count]);}}return dp[0][0];}
该题就没啥可空间优化,所以到这就结束了。我觉得这个代码是最好理解的。
相关文章:
leetcode-买卖股票问题
309. 买卖股票的最佳时机含冷冻期 - 力扣(LeetCode) 动态规划解题思路: 1、暴力递归(难点如何定义递归函数) 2、记忆化搜索-傻缓存法(根据暴力递归可变参数确定缓存数组维度) 3、严格表结构依…...
MYSQL学习笔记(三):分组、排序、分页查询
前言: 学习和使用数据库可以说是程序员必须具备能力,这里将更新关于MYSQL的使用讲解,大概应该会更新30篇,涵盖入门、进阶、高级(一些原理分析);这一篇是讲解分组、排序、分页查询,并且结合案例进行讲解;虽…...
上位机工作感想-2024年工作总结和来年计划
随着工作年限的增增长,发现自己越来越不喜欢在博客里面写一些掺杂自己感想的东西了,或许是逐渐被工作逼得“成熟”了吧。2024年,学到了很多东西,做了很多项目,也帮别人解决了很多问题,唯独没有涨工资。来这…...
【视觉惯性SLAM:十六、 ORB-SLAM3 中的多地图系统】
16.1 多地图的基本概念 多地图系统是机器人和计算机视觉领域中的一种关键技术,尤其在 SLAM 系统中具有重要意义。单一地图通常用于表示机器人或相机在环境中的位置和构建的空间结构,但单一地图在以下情况下可能无法满足需求: 大规模场景建图…...
【C++笔记】红黑树封装map和set深度剖析
【C笔记】红黑树封装map和set深度剖析 🔥个人主页:大白的编程日记 🔥专栏:C笔记 文章目录 【C笔记】红黑树封装map和set深度剖析前言一. 源码及框架分析1.1 源码框架分析 二. 模拟实现map和set2.1封装map和set 三.迭代器3.1思路…...
4.若依 BaseController
若依的BaseController是其他所有Controller的基类,一起来看下BaseController定义了什么 1. 定义请求返回内容的格式 code/msg/data 返回数据格式不是必须是AjaxResult,开发者可以自定义返回格式,注意与前端取值方式一致即可。 2. 获取调用…...
vue项目配置多语言
本文详细介绍如何在 Vue 项目中集成 vue-i18n 和 Element-UI ,实现多语言切换;首先通过 npm 安装 vue-i18n 和相关语言包,接着在配置文件中设置中文和英文的语言信息;最后在 main.js 中导入并挂载多语言实例,实现切换地…...
数据可视化大屏设计与实现
本文将带你一步步了解如何使用 ECharts 实现一个数据可视化大屏,并且如何动态加载天气数据展示。通过整合 HTML、CSS、JavaScript 以及后端接口请求,我们可以构建一个响应式的数据可视化页面。 1. 页面结构介绍 在此例中,整个页面分为几个主…...
PDF文件提取开源工具调研总结
概述 PDF是一种日常工作中广泛使用的跨平台文档格式,常常包含丰富的内容:包括文本、图表、表格、公式、图像。在现代信息处理工作流中发挥了重要的作用,尤其是RAG项目中,通过将非结构化数据转化为结构化和可访问的信息࿰…...
多监控m3u8视频流,怎么获取每个监控的封面图(纯前端)
文章目录 1.背景2.问题分析3.解决方案3.1解决思路3.2解决过程3.2.1 封装播放组件3.2.2 隐形的视频div3.2.3 截取封面图 3.3 结束 1.背景 有这样一个需求: 给你一个监控列表,每页展示多个监控(至少12个,m3u8格式)&…...
【机器学习实战入门项目】使用深度学习创建您自己的表情符号
深度学习项目入门——让你更接近数据科学的梦想 表情符号或头像是表示非语言暗示的方式。这些暗示已成为在线聊天、产品评论、品牌情感等的重要组成部分。这也促使数据科学领域越来越多的研究致力于表情驱动的故事讲述。 随着计算机视觉和深度学习的进步,现在可以…...
技术洞察:C++在后端开发中的前沿趋势与社会影响
文章目录 引言C在后端开发中的前沿趋势1. 高性能计算的需求2. 微服务架构的兴起3. 跨平台开发的便利性 跨领域技术融合与创新实践1. C与人工智能的结合2. C与区块链技术的融合 C对社会与人文的影响1. 提升生产力与创新能力2. 促进技术教育与人才培养3. 技术与人文的深度融合 结…...
【人工智能 | 大数据】基于人工智能的大数据分析方法
【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈智能大数据分析 ⌋ ⌋ ⌋ 智能大数据分析是指利用先进的技术和算法对大规模数据进行深入分析和挖掘,以提取有价值的信息和洞察。它结合了大数据技术、人工智能(AI)、机器学习(ML&a…...
数字经济时代下的创新探索与实践:以“开源AI智能名片2+1链动模式S2B2C商城小程序源码”为核心
摘要:在数字经济蓬勃发展的今天,中国作为全球数字经济的领航者,正以前所未有的速度推进“数字中国”建设。本文旨在探讨“开源AI智能名片21链动模式S2B2C商城小程序源码”在数字经济背景下的应用潜力与实践价值,从多个维度分析其对…...
【English-Book】Go in Action目录页翻译中文
第8页 内容 前言 xi 序言 xiii 致谢 xiv 关于本书 xvi 关于封面插图 xix 1 介绍 Go 1 1.1 用 Go 解决现代编程挑战 2 开发速度 3 • 并发 3 • Go 的类型系统 5 内存管理 7 1.2 你好,Go 7 介绍 Go 玩具 8 1.3 总结 8 2 Go 快速入门 9 2.1 程序架构 10 2.2 主包 …...
js: 区分后端返回数字是否为null、‘-’ 或正常number类型数字。
问: 这是我的代码<CountTo v-if!isNaN(Number(item.num))> <span v-else>{{item.num}}</span> 我希望不是null的时候走countTo,是null的时候直接<span>{{item.num}}</span>显示 回答: 最终结果: …...
网络变压器的分类
网络变压器是局域网(LAN)中各级网络设备中必备的元件。它们的主要功能是传输数据,增强信号,并提供电气隔离,以防雷保护和匹配阻抗。网络变压器也被称为数据泵或网络隔离变压器。它们广泛应用于网络交换机、路由器、网卡、集线器等设备中。 网…...
SUCTF-SU_BBRE-好久不见21
哈哈哈哈哈哈,,,,纯汇编有大佬用工具反编译成伪代码吗。。。 题解: 由function2处逻辑,解rc4得到第一段flag We1com3ToReWorld,正常输入下执行完function0,程序结束,cong…...
Python 实现 NLP 的完整流程
💖 欢迎来到我的博客! 非常高兴能在这里与您相遇。在这里,您不仅能获得有趣的技术分享,还能感受到轻松愉快的氛围。无论您是编程新手,还是资深开发者,都能在这里找到属于您的知识宝藏,学习和成长…...
穷举vs暴搜vs深搜vs回溯vs剪枝系列一>N 皇后
题目: 解析: 1.决策树: 代码设计: 根据决策树剪枝设计: 代码: class Solution {private List<List<String>> ret;private char[][] path;private boolean[] checkdig1,checkdig2,checkco…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
从WWDC看苹果产品发展的规律
WWDC 是苹果公司一年一度面向全球开发者的盛会,其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具,对过去十年 WWDC 主题演讲内容进行了系统化分析,形成了这份…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
k8s业务程序联调工具-KtConnect
概述 原理 工具作用是建立了一个从本地到集群的单向VPN,根据VPN原理,打通两个内网必然需要借助一个公共中继节点,ktconnect工具巧妙的利用k8s原生的portforward能力,简化了建立连接的过程,apiserver间接起到了中继节…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
AI书签管理工具开发全记录(十九):嵌入资源处理
1.前言 📝 在上一篇文章中,我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源,方便后续将资源打包到一个可执行文件中。 2.embed介绍 🎯 Go 1.16 引入了革命性的 embed 包,彻底改变了静态资源管理的…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
6️⃣Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙
Go 语言中的哈希、加密与序列化:通往区块链世界的钥匙 一、前言:离区块链还有多远? 区块链听起来可能遥不可及,似乎是只有密码学专家和资深工程师才能涉足的领域。但事实上,构建一个区块链的核心并不复杂,尤其当你已经掌握了一门系统编程语言,比如 Go。 要真正理解区…...
OCR MLLM Evaluation
为什么需要评测体系?——背景与矛盾 能干的事: 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。干不了的事: 碰到复杂表格(合并单元…...
