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

LeetCode 0714. 买卖股票的最佳时机含手续费

【LetMeFly】714.买卖股票的最佳时机含手续费

力扣题目链接:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

给定一个整数数组 prices,其中 prices[i]表示第 i 天的股票价格 ;整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意:这里的一笔交易指买入持有并卖出股票的整个过程,每笔交易你只需要为支付一次手续费。

 

示例 1:

输入:prices = [1, 3, 2, 8, 4, 9], fee = 2
输出:8
解释:能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

示例 2:

输入:prices = [1,3,7,5,10,3], fee = 3
输出:6

 

提示:

  • 1 <= prices.length <= 5 * 104
  • 1 <= prices[i] < 5 * 104
  • 0 <= fee < 5 * 104

方法一:动态规划

使用两个变量:buy代表当前处于持仓状态下的最大收益、sell代表当前处于“空手”状态下的最大收益。

在第一天:

  • 若处于持仓状态,则说明购买了第一天的股票,当前总收益 b u y = − p r i c e s [ 0 ] buy = -prices[0] buy=prices[0]
  • 若处于空手状态,则说明第一天没有进行股票交易(因为有手续费所以不会当天购买当天卖出),当前总收益 s e l l = 0 sell = 0 sell=0

之后从第二天开始遍历到最后一天,遍历过程中:

  • b u y = max ⁡ ( b u y , s e l l − p r i c e s [ i ] ) buy = \max(buy, sell - prices[i]) buy=max(buy,sellprices[i])
  • s e l l = max ⁡ ( s e l l , b u y + p r i c e s [ i ] − f e e ) sell = \max(sell, buy + prices[i] - fee) sell=max(sell,buy+prices[i]fee)

最终返回 s e l l sell sell即可。

  • 时间复杂度 O ( l e n ( p r i c e s ) ) O(len(prices)) O(len(prices))
  • 空间复杂度 O ( 1 ) O(1) O(1)

AC代码

C++
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int buy = -prices[0], sell = 0;for (int i = 1; i < prices.size(); i++) {buy = max(buy, sell - prices[i]);sell = max(sell, buy + prices[i] - fee);}return sell;}
};
Python
# from typing import Listclass Solution:def maxProfit(self, prices: List[int], fee: int) -> int:buy, sell = -prices[0], 0for i in range(1, len(prices)):buy = max(buy, sell - prices[i])sell = max(sell, buy + prices[i] - fee)return sell

同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/133609633

相关文章:

LeetCode 0714. 买卖股票的最佳时机含手续费

【LetMeFly】714.买卖股票的最佳时机含手续费 力扣题目链接&#xff1a;https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/ 给定一个整数数组 prices&#xff0c;其中 prices[i]表示第 i 天的股票价格 &#xff1b;整数 fee 代表了交易股…...

cartographer-(0)-ubuntu(20.04)-环境安装

1.安装 ROS wiki.ros.org 1.1修改镜像源&#xff1a; 到网站上找与操作系统相匹配的镜像源 ubuntu | 镜像站使用帮助 | 清华大学开源软件镜像站 | Tsinghua Open Source Mirror # 默认注释了源码镜像以提高 apt update 速度&#xff0c;如有需要可自行取消注释 deb htt…...

MIT 6.S081学习笔记(第二章)

〇、前言 本文主要完成MIT 6.S081 实验二&#xff1a;system call 一、Using gdb (easy) Question requirements In many cases, print statements will be sufficient to debug your kernel, but sometimes being able to single step through some assembly code or inspe…...

L958. 二叉树的完全性检验 java

从1开始当下标&#xff0c;最后节点下标节点总数&#xff1f;true&#xff1a;false&#xff1b; /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { …...

阿里云对象存储OSS SDK的使用

官方文档 https://help.aliyun.com/zh/oss/developer-reference/java 准备工作 windows安装好JDK&#xff0c;这里使用JDK1.8为例 windows安装好IDEA&#xff0c;这里使用IDEA2022 登录阿里云控制台&#xff0c;通过免费试用OSS或开通OSS 步骤 配置访问凭证 有临时和长期…...

二、互联网技术——网络协议

文章目录 一、OSI与TCP/IP参考模型二、TCP/IP参考模型各层功能三、TCP/IP参考模型与对应协议四、常用协议与功能五、常用协议端口 一、OSI与TCP/IP参考模型 二、TCP/IP参考模型各层功能 三、TCP/IP参考模型与对应协议 例题&#xff1a;TCP/IP模型包含四个层次&#xff0c;由上至…...

初赛错题集

MPEG属于视频文件格式. UNIX,Mac OS属于操作系统. 中国计算机协会成立于&#xff08;&#xff09;年。 A. 1961 B. 1962 C. 1971 D. 1972 Ans:B 五个本质不同的点在没有重边或者自环的情况下&#xff0c;组成不同的无向图的个数是: A. 10 B. 1024 C. 15 D. 120 Ans:B 解析&…...

Java Thread类详解

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开兴好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

3_使用传统CNN网络训练图像分类模型

使用传统CNN网络训练图像分类模型 1. MNIST 首先,定义一下超参数等 import torch# dataset input_shape = 28 num_classes = 10# hyper batch_size = 64 num_epochs = 5 learning_rate = 1e-3# gpu device = torch.device(cuda...

Java 创建线程的方法

&#x1f648;作者简介&#xff1a;练习时长两年半的Java up主 &#x1f649;个人主页&#xff1a;程序员老茶 &#x1f64a; ps:点赞&#x1f44d;是免费的&#xff0c;却可以让写博客的作者开兴好久好久&#x1f60e; &#x1f4da;系列专栏&#xff1a;Java全栈&#xff0c;…...

基于安卓android微信小程序的旅游app系统

项目介绍 随着人民生活水平的提高,旅游业已经越来越大众化,而旅游业的核心是信息,不论是对旅游管理部门、对旅游企业,或是对旅游者而言,有效的获取旅游信息,都显得特别重要.自助定制游将使旅游相关信息管理工作规范化、信息化、程序化,提供旅游景点、旅游线路,旅游新闻等服务本…...

C++设计模式-单件(Singleton)

目录 C设计模式-单件&#xff08;Singleton&#xff09; 一、意图 二、适用性 三、结构 四、参与者 五、代码 C设计模式-单件&#xff08;Singleton&#xff09; 一、意图 保证一个类仅有一个实例&#xff0c;并提供一个访问它的全局访问点。 二、适用性 当类只能有一…...

想做好接口测试,先把这些概念搞清楚了

接口一般来说有两种&#xff0c;一种是程序内部的接口&#xff0c;一种是系统对外的接口。 系统对外的接口 比如你要从别的网站或服务器上获取资源或信息&#xff0c;别人肯定不会把数据库共享给你&#xff0c;他只能给你提供一个他们写好的方法来获取数据&#xff0c;你引用…...

通过融合UGV的地图信息和IMU的惯性测量数据,实现对车辆精确位置和运动状态的估计和跟踪研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

『Linux』Linux环境搭建 | 阿里云云服务器白嫖 | Xshell环境配置

&#x1f525;博客主页&#xff1a; 小羊失眠啦 &#x1f516;系列专栏&#xff1a; C语言、Linux &#x1f325;️每日语录&#xff1a;时间&#xff0c;都是公平的&#xff0c;不公平的&#xff0c;只是现在的自己&#xff0c;对未来的自己。 ❤️感谢大家点赞&#x1f44d;收…...

C++ 类和对象篇(五) 析构函数

目录 一、概念 1. 析构函数是什么&#xff1f; 2. 为什么要有析构函数&#xff1f; 3. 怎么用析构函数&#xff1f; 3.1 创建析构函数 3.2 调用析构函数 二、特性 三、由编译器生成的默认析构函数 四、对象的析构顺序 1. 局部对象 2. new出来的堆对象 3. 全局对象 一、概念 1…...

find 与 cp 命令组合使用

查找到文件后&#xff0c;拷贝到指定路径 find ~/Downloads/ -name *.torrent -exec cp {} ~/Downloads/myTorrent \;\;前面有个空格&#xff0c;要注意&#xff0c;这是固定结构&#xff0c;请不要尝试改变 上面命令是在Downloads 目标中查找后缀为torrent所有文件&#xff0…...

用VLD调查VC内存泄漏

一、发现内存泄漏 使用VS2022&#xff0c;发现提示有内存泄漏&#xff0c;检查了所有的new&#xff0c;确认都有相应的delete释放。 Detected memory leaks! Dumping objects -> {1914} normal block at 0x0000021FDFFBD2E0, 48 bytes long.Data: < >…...

【Java 进阶篇】使用 JDBCTemplate 执行 DQL 语句详解

在前面的文章中&#xff0c;我们已经学习了如何使用 Spring 的 JDBCTemplate 执行 DML&#xff08;Data Manipulation Language&#xff09;操作&#xff0c;包括插入、更新和删除操作。现在&#xff0c;让我们来深入了解如何使用 JDBCTemplate 执行 DQL&#xff08;Data Query…...

了解了spring mvc web容器中一个http请求的全过程,能给我们提升多少武力值

继上一篇文章什么&#xff0c;这年头还有人不知道404_cow__sky的博客-CSDN博客后&#xff0c;有些同学发现&#xff0c;学了之后有啥用&#xff0c;有什么实际场景可以用到吗&#xff1f;程序员就是这样&#xff0c;不习惯于纸上谈兵&#xff0c;给一个场景show me code才是最实…...

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

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

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

return this;返回的是谁

一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请&#xff0c;不同级别的经理有不同的审批权限&#xff1a; // 抽象处理者&#xff1a;审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

comfyui 工作流中 图生视频 如何增加视频的长度到5秒

comfyUI 工作流怎么可以生成更长的视频。除了硬件显存要求之外还有别的方法吗&#xff1f; 在ComfyUI中实现图生视频并延长到5秒&#xff0c;需要结合多个扩展和技巧。以下是完整解决方案&#xff1a; 核心工作流配置&#xff08;24fps下5秒120帧&#xff09; #mermaid-svg-yP…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...