首页 > 编程语言 >代码随性训练营第四十九天(Python)| 121. 买卖股票的最佳时机 、122.买卖股票的最佳时机II

代码随性训练营第四十九天(Python)| 121. 买卖股票的最佳时机 、122.买卖股票的最佳时机II

时间:2023-11-30 19:56:08浏览次数:56  
标签:买卖 int max 第四十九 len range 最佳时机 prices dp

121. 买卖股票的最佳时机
1、动态规划

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp[i][0] 代表第 i 天持有股票获取的最大利益
        # dp[i][1] 代表第 i 天不持有股票获取的最大利益
        dp = [[0] * 2 for _ in range(len(prices))]
        dp[0][0] = - prices[0]
        dp[0][1] = 0
        for i in range(1, len(prices)):
            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[-1][1]

2、贪心

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        res = 0
        low = prices[0]
        for i in range(1, len(prices)):
            low = min(low, prices[i])
            res = max(res, prices[i] - low)
        return res

3、动态规划优化

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp0, dp1 = - prices[0], 0
        for i in range(1, len(prices)):
            dp1 = max(dp1, dp0 + prices[i])
            dp0 = max(dp0, -prices[i])
        return dp1

122.买卖股票的最佳时机II
1、动态规划

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # dp[i][0] 不持有股票,dp[i][1] 持有股票
        dp = [[0] * 2 for _ 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[-1][0]

标签:买卖,int,max,第四十九,len,range,最佳时机,prices,dp
From: https://www.cnblogs.com/yixff/p/17867954.html

相关文章

  • 买卖股票的最佳时机2
    买卖股票的最佳时机2难度:简单|中等√|困难-------------------用时:16分钟(第一次)-------------------作题日期:2023-11-29ps:本人理解有限,以下是自我理解,leetCode官方和大佬有更完整和详细的解析!!!题目描述题目描述给你一个整数数组prices,其中prices......
  • 714. 买卖股票的最佳时机含手续费(中)
    目录题目动态规划优化题目给定一个整数数组prices,其中prices[i]表示第i天的股票价格;整数fee代表了交易股票的手续费用。你可以无限次地完成交易,但是你每笔交易都需要付手续费。如果你已经购买了一个股票,在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值......
  • 188. 买卖股票的最佳时机 IV(难)
    目录题目动态规划优化题目给你一个整数数组prices和一个整数k,其中prices[i]是某支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成k笔交易。也就是说,你最多可以买k次,卖k次。注意:你不能同时参与多笔交易(你必须在再次购买前出......
  • 123. 买卖股票的最佳时机 III(难)
    目录题目动态规划题目给定一个数组,它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。示例1:输入:prices=[3,3,5,0,0,3,1,4]输出:6......
  • 代码随想训练营第三十二天(Python)| 122.买卖股票的最佳时机 II、55. 跳跃游戏、45.跳跃
    122.买卖股票的最佳时机II1、贪心classSolution:defmaxProfit(self,prices:List[int])->int:res=0foriinrange(1,len(prices)):res+=max(prices[i]-prices[i-1],0)returnres2、动态规划classSolution:d......
  • 车买卖交易小程序平台系统开发
      一、主要功能  1.车辆分类查找  小程序会对不同型号、不同价位、不同颜色的车辆依类划分,用户在选择心仪的车辆时可以通过搜索关键词查找,然后平台会根据用户喜好推送一些与该车型相关的车辆信息,用户再对其进行比对,然后做出决定。  2.车辆信息展示  上传到......
  • 车买卖交易小程序平台系统开发
      开发一款车买卖交易小程序需要具备以下功能:  一、主要功能  1.车辆分类查找  小程序会对不同型号、不同价位、不同颜色的车辆依类划分,用户在选择心仪的车辆时可以通过搜索关键词查找,然后平台会根据用户喜好推送一些与该车型相关的车辆信息,用户再对其进行比对,......
  • 二手房买卖注意事项
    产权确认★★★★★产权证上的房主是否与卖房人是同一个人,核对卖方身份证或工商档案中的名称与房产证上的房屋所有人是否一致,原则上是一个字也不能错。产权证上注明的面积与实际面积是否有不符之处。看该房屋是否有房屋共有权人,如果房屋为多人共有,则须卖房人提供所有共有人......
  • LeetCode121 买卖股票的最佳时机
    题目描述:给定一个数组 prices ,它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择 某一天 买入这只股票,并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能......
  • 算法题解——买卖股票的最佳时机
    解题思路先考虑最简单的「暴力遍历」,即枚举出所有情况,并从中选择最大利润。设数组prices的长度为n,由于只能先买入后卖出,因此第1天买可在未来n−1天卖出,第2天买可在未来n-2天卖出……以此类推,共有\[(n-1)+(n-2)+\cdots+0=\frac{n(n-1)}{2}\]种情况,时间复......