代码随想录算法训练营Day50 | 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、股票问题总结 | Python | 个人记录向

本文主要是介绍代码随想录算法训练营Day50 | 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、股票问题总结 | Python | 个人记录向,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文目录

  • 309.最佳买卖股票时机含冷冻期
    • 做题
    • 看文章
  • 714.买卖股票的最佳时机含手续费
    • 做题
    • 看文章
  • 股票问题总结
  • 以往忽略的知识点小结
  • 个人体会

309.最佳买卖股票时机含冷冻期

代码随想录:309.最佳买卖股票时机含冷冻期
Leetcode:309.最佳买卖股票时机含冷冻期

做题

简单多加一个冷冻期状态,无法AC。

看文章

具体可以区分出如下四个状态:
状态一:持有股票状态(今天买入股票,或者是之前就买入了股票然后没有操作,一直持有)
不持有股票状态,这里就有两种卖出股票状态
状态二:保持卖出股票的状态(两天前就卖出了股票,度过一天冷冻期。或者是前一天就是卖出股票状态,一直没操作)
状态三:今天卖出股票
状态四:今天为冷冻期状态,但冷冻期状态不可持续,只有一天!

有点绕,可以看看文章。

class Solution(object):
class Solution:def maxProfit(self, prices: List[int]) -> int:n = len(prices)if n == 0:return 0dp = [[0] * 4 for _ in range(n)]  # 创建动态规划数组,4个状态分别表示持有股票、不持有股票且处于冷冻期、不持有股票且不处于冷冻期、不持有股票且当天卖出后处于冷冻期dp[0][0] = -prices[0]  # 初始状态:第一天持有股票的最大利润为买入股票的价格for i in range(1, n):dp[i][0] = max(dp[i-1][0], max(dp[i-1][3], dp[i-1][1]) - prices[i])  # 当前持有股票的最大利润等于前一天持有股票的最大利润或者前一天不持有股票且不处于冷冻期的最大利润减去当前股票的价格dp[i][1] = max(dp[i-1][1], dp[i-1][3])  # 当前不持有股票且处于冷冻期的最大利润等于前一天持有股票的最大利润加上当前股票的价格dp[i][2] = dp[i-1][0] + prices[i]  # 当前不持有股票且不处于冷冻期的最大利润等于前一天不持有股票的最大利润或者前一天处于冷冻期的最大利润dp[i][3] = dp[i-1][2]  # 当前不持有股票且当天卖出后处于冷冻期的最大利润等于前一天不持有股票且不处于冷冻期的最大利润return max(dp[n-1][3], dp[n-1][1], dp[n-1][2])  # 返回最后一天不持有股票的最大利润

时间复杂度:O(n)
空间复杂度:O(n)

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

代码随想录:714.买卖股票的最佳时机含手续费
Leetcode:714.买卖股票的最佳时机含手续费

做题

加手续费就比较简单了,但实现的时候还是出了一些很简单、但一直没看出来的bug:①一开始dp初始化写成dp[0] = xxx,导致赋值错误;②股票完整的买入卖出才算一次手续费,故只需要在卖出时计算即可。

class Solution:def maxProfit(self, prices: List[int], fee: int) -> int:size = len(prices)dp =[[0] * 2 for _ in range(size)]dp[0][0] = - prices[0]for i in range(1, size):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] - fee)return max(dp[size-1][0], dp[size-1][1])

时间复杂度:O(n)
空间复杂度:O(n)

看文章

思路一致。

股票问题总结

代码随想录:股票问题总结

对股票问题进行总结,解题思路主要是分析出所有状态,关键题目是2次交易(可以推导出k次交易),特殊题目是冷冻期(状态划分比较难)。

以往忽略的知识点小结

  • 最佳买卖股票时机的冷冻期状态分析
  • 股票一次完整的买入+卖出算一次手续费
  • 一些基础coding的细节要处理好

个人体会

完成时间:2h。
心得:冷冻期是特殊情况,需要分析状态再处理;股票问题正式完结。

这篇关于代码随想录算法训练营Day50 | 309.最佳买卖股票时机含冷冻期、714.买卖股票的最佳时机含手续费、股票问题总结 | Python | 个人记录向的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1002699

相关文章

Python Transformers库(NLP处理库)案例代码讲解

《PythonTransformers库(NLP处理库)案例代码讲解》本文介绍transformers库的全面讲解,包含基础知识、高级用法、案例代码及学习路径,内容经过组织,适合不同阶段的学习者,对... 目录一、基础知识1. Transformers 库简介2. 安装与环境配置3. 快速上手示例二、核心模

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

Python使用getopt处理命令行参数示例解析(最佳实践)

《Python使用getopt处理命令行参数示例解析(最佳实践)》getopt模块是Python标准库中一个简单但强大的命令行参数处理工具,它特别适合那些需要快速实现基本命令行参数解析的场景,或者需要... 目录为什么需要处理命令行参数?getopt模块基础实际应用示例与其他参数处理方式的比较常见问http

Java Response返回值的最佳处理方案

《JavaResponse返回值的最佳处理方案》在开发Web应用程序时,我们经常需要通过HTTP请求从服务器获取响应数据,这些数据可以是JSON、XML、甚至是文件,本篇文章将详细解析Java中处理... 目录摘要概述核心问题:关键技术点:源码解析示例 1:使用HttpURLConnection获取Resp

python实现svg图片转换为png和gif

《python实现svg图片转换为png和gif》这篇文章主要为大家详细介绍了python如何实现将svg图片格式转换为png和gif,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录python实现svg图片转换为png和gifpython实现图片格式之间的相互转换延展:基于Py

Python中的getopt模块用法小结

《Python中的getopt模块用法小结》getopt.getopt()函数是Python中用于解析命令行参数的标准库函数,该函数可以从命令行中提取选项和参数,并对它们进行处理,本文详细介绍了Pyt... 目录getopt模块介绍getopt.getopt函数的介绍getopt模块的常用用法getopt模

Python利用ElementTree实现快速解析XML文件

《Python利用ElementTree实现快速解析XML文件》ElementTree是Python标准库的一部分,而且是Python标准库中用于解析和操作XML数据的模块,下面小编就来和大家详细讲讲... 目录一、XML文件解析到底有多重要二、ElementTree快速入门1. 加载XML的两种方式2.

Python如何精准判断某个进程是否在运行

《Python如何精准判断某个进程是否在运行》这篇文章主要为大家详细介绍了Python如何精准判断某个进程是否在运行,本文为大家整理了3种方法并进行了对比,有需要的小伙伴可以跟随小编一起学习一下... 目录一、为什么需要判断进程是否存在二、方法1:用psutil库(推荐)三、方法2:用os.system调用

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组