程序员经验分享-hwhale

买卖股票系列问题 Leetcode题目

2023-05-16

leetcode 刷题记录

一. 买卖股票系列问题

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

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

解法1： 一次遍历

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        min_v = prices[0]  #  设置 股票最小值为初始值
        max_profile = 0  #  最大收益
        for i in range(1, len(prices)):
            if prices[i] < min_v:  # 小于 最小值时 可以尝试买入，此时没有收益
                min_v = prices[i]
            else:    # 此时，大于最小值时，尝试卖出，但是 和 之前最大收益比较，
                max_profile = max(prices[i] - min_v, max_profile)
        return max_profile

解法2: 动态规划, 感觉有点大材小用了

class Solution:
   def maxProfit(self, prices: List[int]) -> int:
       if len(prices) <= 1:
           return 0
       # dp[i]: 表示前i天的最大利润， dp[i]由前i-1天的最大利润 和 第i天的利润 决定的， 
       # 递推公式: dp[i] = max(dp[i-1], prices[i] - minprices) # minprices表示之前的 最低价格
       # 这题使用 动态规划，大材小用了
       len_prices = len(prices)
       dp = [0] * len_prices
       dp[0] = 0 
       minprices = prices[0]
       for i in range(1, len_prices):
           minprices = min(minprices, prices[i])
           dp[i] = max(dp[i-1], prices[i] - minprices)  # 比方法1麻烦了
       return dp[-1]

解法3: 暴力 思路很简单就是， 计算当前价格和之前最低价格的差值，找到最大值； 3692 ms

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        dp = [0] * len(prices)
        for i in range(len(prices)-1, 0, -1): 
            temp = prices[i] - min(prices[:i])  # 计算当前和 之前最低价格 最小值
            dp[i] = temp if temp > 0 else 0
        return max(dp)

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

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

解法1： 动态规划

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        len_prices = len(prices)
        dp = [0] * len_prices
        dp[0] = 0
        # dp[i]:表示第i天收益
        min_prices = prices[0]
        for i in range(1, len_prices):  # 什么时候售掉?
            min_prices = min(min_prices, prices[i])
            if i < len_prices - 1 and  min_prices < prices[i] and prices[i] > prices[i+1]:
                dp[i] = (prices[i] - min_prices)
                min_prices = prices[i+1]
            elif i == len_prices -1:
                dp[i] = (prices[i] - min_prices)
        return sum(dp)

或者 不使用动态规划，一次遍历，

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        len_prices = len(prices)
        sum_price = 0   # 最终利润
        min_prices = prices[0]
        for i in range(1, len_prices):  # 什么时候售掉? 判断条件太复杂，
            min_prices = min(min_prices, prices[i])
            if i < len_prices - 1 and  min_prices < prices[i] and prices[i] > prices[i+1]:
                sum_price += (prices[i] - min_prices)
                min_prices = prices[i+1]
            elif i == len_prices -1:
                sum_price += (prices[i] - min_prices)
        return sum_price

解法2： 贪心法， 不太好理解 参考官方
最大化公式 ∑ i = 1 x a [ r i ] − a [ l i ] \sum_{i=1}^{x} a[r_i] - a[l_i] i=1∑x​a[ri​]−a[li​]
其实等价于 连续若干个长度为1的区间价值和。

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        # 贪心法
        max_profile = 0
        for i in range(1, len(prices)):
            max_profile += max(0, prices[i]-prices[i-1])
        return max_profile

解法3 动态规划

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0
        # 动态规划
        # dp[i][0]: 表示第i天交易完后，手里没有股票的最大利润；
        # 状态转移方程： dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]); 可能之前没有股票，或 有股票 现在卖了；
        # dp[i][1]: 表示第i天交易完后，手里持有一支股票的最大利润； 持有股票，数值是负的
        # 状态转移方程： dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]); 可能之前就有股票， 或 之前没有股票，现在买入股票（买入股票 减）；
        len_prices = len(prices)
        dp = [[0, 0] for i in range(len_prices)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]
        for i in range(1, len_prices):
            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[len_prices-1][0]

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

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

  • 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
  • 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

解法1: 动态规划, 仔细琢磨， 反复记忆

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 多了个 冷冻期
        # 设置三个状态
        if len(prices) <= 1:
            return 0 
        len_prices = len(prices)
        dp = [[0, 0, 0] for i in range(len_prices)]
        # dp[i][0]:  手上持有股票的最大收益
        # dp[i][1]: 手上不持有股票，并且处于冷冻期的 累计最大收益
        # dp[i][2]: 手上不持有股票，并且不处于冷冻期中的 最大收益
        dp[0][0] = -prices[0]
        dp[0][1] = 0
        dp[0][2] = 0
        for i in range(1, len_prices):
            dp[i][0] = max(dp[i-1][0], dp[i-1][2]-prices[i]) # i-1不处于冷冻可以买
            dp[i][1] = dp[i-1][0] + prices[i]
            dp[i][2] = max(dp[i-1][1], dp[i-1][2]) # 之前处于冷冻期， 或者 之前不处于冷冻期
        return max(dp[len_prices-1][1], dp[len_prices-1][2])

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

123. 买卖股票的最佳时机 III

188. 买卖股票的最佳时机 IV

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

LeetCode

买卖股票系列问题

买卖股票系列问题 Leetcode题目 的相关文章

  • 第 208 场周赛

    1 5523 文件夹操作日志搜集器 class Solution def minOperations self logs List str gt int 栈 xff0c 先进 后出 zhan 61 39 main 39 for log in

  • day 5: 字符串

    1 剑指 Offer 38 字符串的排列 输入一个字符串 xff0c 打印出该字符串中字符的所有排列 你可以以任意顺序返回这个字符串数组 xff0c 但里面不能有重复元素 示例 xff1a 输入 xff1a s 61 34 abc 34 输

随机推荐

  • day6: 数组

    1 18 四数之和 给定一个包含 n 个整数的数组 nums 和一个目标值 target xff0c 判断 nums 中是否存在四个元素 a xff0c b xff0c c 和 d xff0c 使得 a 43 b 43 c 43 d 的值与

  • day7: 剑指 Offer 44. 数字序列中某一位的数字

    1 剑指 Offer 44 数字序列中某一位的数字 数字以0123456789101112131415 的格式序列化到一个字符序列中 在这个序列中 xff0c 第5位 xff08 从下标0开始计数 xff09 是5 xff0c 第13位是1

  • casbin 使用说明记录

    本文简单记录casbin 安装步骤 使用 Casbin 作为 ThinkPHP 的权限控制中间件 PHP Casbin 是一个强大的 高效的开源访问控制框架 xff0c 它支持基于各种访问控制模型的权限管理 Think Casbin 是一个

  • 844. 比较含退格的字符串

    给定 S 和 T 两个字符串 xff0c 当它们分别被输入到空白的文本编辑器后 xff0c 判断二者是否相等 xff0c 并返回结果 代表退格字符 注意 xff1a 如果对空文本输入退格字符 xff0c 文本继续为空 示例 1 xff1a

  • 笔试题记录

    1 逆波兰表达式 是称为 后缀表达式 xff0c 把运算量写在前面 xff0c 把算符写在后面 写出a b c d 43 e f g h 43 i j k 的逆波兰表达式 拆开写各个部分的 xff1a 按优先级 xff08 1 xff09

  • 牛客网 赛码在线编程中数据读取问题

    一 数据读取的方式 xff08 python3 xff09 1 input 读取输入数据 while True try inputs 61 input except break 2 网站的数据输入是是一个含有多行数据的input文件 in文

  • 贪心算法 leetcode编程题

    1 452 用最少数量的箭引爆气球 在二维空间中有许多球形的气球 对于每个气球 xff0c 提供的输入是水平方向上 xff0c 气球直径的开始和结束坐标 由于它是水平的 xff0c 所以纵坐标并不重要 xff0c 因此只要知道开始和结束的横

  • 排序题 LeetCode题

    1 1370 上升下降字符串 给你一个字符串 s xff0c 请你根据下面的算法重新构造字符串 xff1a 从 s 中选出 最小 的字符 xff0c 将它 接在 结果字符串的后面 从 s 剩余字符中选出 最小 的字符 xff0c 且该字符比

  • BP算法公式推导

    令表示第层的第个神经元到第层的第个神经元的连接权值 xff0c 表示第层第个神经元的输入 xff0c 表示第层第个神经元的输出 xff0c 表示层第个神经元的偏置 xff0c C表示代价函数 则有 xff1a 其中 表示激活函数 训练多层网

  • 卷积神经网络中的Separable Convolution_转载

    卷积神经网络在图像处理中的地位已然毋庸置疑 卷积运算具备强大的特征提取能力 相比全连接又消耗更少的参数 xff0c 应用在图像这样的二维结构数据中有着先天优势 然而受限于目前移动端设备硬件条件 xff0c 显著降低神经网络的运算量依旧是网络

  • 二分查找方法 leetcode题

    这里用来 记录 使用二分查找方法 的题目 1 704 二分查找 给定一个 n 个元素有序的 xff08 升序 xff09 整型数组 nums 和一个目标值 target xff0c 写一个函数搜索 nums 中的 target xff0c

  • 动态规划题 leetcode

    1 62 不同路径 一个机器人位于一个 m x n 网格的左上角 xff08 起始点在下图中标记为 Start xff09 机器人每次只能向下或者向右移动一步 机器人试图达到网格的右下角 xff08 在下图中标记为 Finish xff09

  • 字典序 Leetcode题目

    1 440 字典序的第K小数字 给定整数 n 和 k xff0c 找到 1 到 n 中字典序第 k 小的数字 注意 xff1a 1 k n 109 示例 xff1a 输入 n 13 k 2 输出 10 解释 字典序的排列是 1 10 11

  • Git：从Git下载项目到本地及项目重建

    从Git上下载项目 重建项目

  • 子序列题目 Leetcode题目

    1 53 最大子序和 面试题 16 17 连续数列 给定一个整数数组 nums xff0c 找到一个具有最大和的连续子数组 xff08 子数组最少包含一个元素 xff09 xff0c 返回其最大和 示例 xff1a 输入 2 1 3 4 1

  • 整数问题（求和 拆分 替换等） leetcode问题

    1 829 连续整数求和 给定一个正整数 N xff0c 试求有多少组连续正整数满足所有数字之和为 N 示例 1 输入 5 输出 2 解释 5 61 5 61 2 43 3 xff0c 共有两组连续整数 5 2 3 求和后为 5 示例 2

  • B 中等题 LeetCode

    中等题 按出题指数排列 1 2 两数相加 给出两个 非空 的链表用来表示两个非负的整数 其中 xff0c 它们各自的位数是按照 逆序 的方式存储的 xff0c 并且它们的每个节点只能存储 一位 数字 如果 xff0c 我们将这两个数相加起来

  • 回文串 leetcode

    1 125 验证回文串 给定一个字符串 xff0c 验证它是否是回文串 xff0c 只考虑字母和数字字符 xff0c 可以忽略字母的大小写 说明 xff1a 本题中 xff0c 我们将空字符串定义为有效的回文串 示例 1 输入 34 A m

  • 回溯法 题目 leetcode

    1 22 括号生成 数字 n 代表生成括号的对数 xff0c 请你设计一个函数 xff0c 用于能够生成所有可能的并且 有效的 括号组合 示例 xff1a 输入 xff1a n 61 3 输出 xff1a 34 34 34 34 34 34

  • 买卖股票系列问题 Leetcode题目

    leetcode 刷题记录 一 买卖股票系列问题 1 121 买卖股票的最佳时机 给定一个数组 xff0c 它的第 i 个元素是一支给定股票第 i 天的价格 如果你最多只允许完成一笔交易 xff08 即买入和卖出一支股票一次 xff09 x

热门标签