• <noscript id="e0iig"><kbd id="e0iig"></kbd></noscript>
  • <td id="e0iig"></td>
  • <option id="e0iig"></option>
  • <noscript id="e0iig"><source id="e0iig"></source></noscript>
  • 天天刷leetcode——122 買賣股票的最佳時機

    標簽: 天天刷leetcode  leetcode  貪心算法  算法

    122 買賣股票的最佳時機

    題目描述

    給定一個數組,它的第 i 個元素是一支給定股票第 i 天的價格。

    設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。

    解題思路

    1. 貪心算法

    因為同一天可以同時買賣,所以只要前一天比后一天價格低就買入,利潤就是后一天剪前一天。

        def maxProfit(self, prices: List[int]) -> int:
            res = 0
            for i in range(len(prices)-1):
                if prices[i] > prices[i+1]:
                    continue
                else:
                    res += prices[i+1]-prices[i]
            return res
    

    時間復雜度O(n)
    在這里插入圖片描述

    2. 回溯算法

    這道題可以是回溯,決策樹長下面這個樣子:

    3.動態規劃

    未完待續

    版權聲明:本文為qq_30516823原創文章,遵循 CC 4.0 BY-SA 版權協議,轉載請附上原文出處鏈接和本聲明。
    本文鏈接:https://blog.csdn.net/qq_30516823/article/details/107684932

    智能推薦

    LeetCode #122 買賣股票的最佳時機 II

    題目 給定一個數組,它的第 i 個元素是一支給定股票第 i 天的價格。 設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。 注意:你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。 示例 1: 示例 2: 示例 3: 來源:力扣(LeetCode) 鏈接:https://leetcode-cn.com/problems/best-time-to-...

    LeetCode 122. 買賣股票的最佳時機 II

    方法一:暴力搜索(dfs) 對于每天的股價,有三種情況,不買不賣,買,賣;對于這三種情況進行深度優先搜索 方法二:貪心算法 后一天股價-前一天股價有三種可能,盈利,虧損,利潤不變,由貪心思想可知,我們需要每次都盈利 方法三:波峰波谷法(簡單模擬) 每次在波谷買入,波峰賣出獲得最大利潤...

    Easy | LeetCode 122 | 買賣股票的最佳時機 II

    鏈接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii 給定一個數組,它的第 i 個元素是一支給定股票第 i 天的價格。 設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。 注意:你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。 示例 1: 輸入: [7,1,...

    leetcode 122. 買賣股票的最佳時機 II

    【題目】 給定一個數組,它的第 i 個元素是一支給定股票第 i 天的價格。 設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。 注意:你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。 示例 1: 解釋: 在第 2 天(股票價格 = 1)的時候買入,在第 3 天(股票價格 = 5)的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。 隨后,...

    猜你喜歡

    LeetCode - 122. 買賣股票的最佳時機 II

    122. 買賣股票的最佳時機 II 給定一個數組,它的第 i 個元素是一支給定股票第 i 天的價格。 設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。 注意: 你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。 解題思路: 此題的特點是可以無限次交易,那么只需要從低價格時買入,高價格時賣出就可以了。如果我們今天賣出,明天的股票價格更高,那么我們...

    LeetCode122. 買賣股票的最佳時機 II

    方法一: 時間復雜度O(n) 空間復雜度O(1) 方法二: 從上圖中,我們可以觀察到 A+B+CA+B+C 的和等于差值 DD 所對應的連續峰和谷的高度之差。 時間復雜度O(n) 空間復雜度O(1)...

    leetcode 122. 買賣股票的最佳時機 II

    122. 買賣股票的最佳時機 II 給定一個數組,它的第 i 個元素是一支給定股票第 i 天的價格。 設計一個算法來計算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。 注意:你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。   示例 1: 示例 2: 示例 3:    ...

    Unity_Shader高級篇_13.1_Unity Shader入門精要

    13.4 再談邊緣檢測 在12.3中,我們曾使用Sobel算子對屏幕圖像進行邊緣測試,實現描邊的效果。但是,這種直接利用顏色信息進行邊緣檢測的方法會產生很對我們不希望得到的邊緣線,如圖13.8所示。 可以看出,物體的紋理、陰影等位置也被描上黑邊,而這往往不是我們希望看到的。在本節中,我們將學習如何在深度和法線上進行邊緣檢測,這些圖像不會受紋理和光照的影響,而僅僅保存了當前渲染物體的模型信息,通過這...

    Seata AT 模式 原理詳解

    目錄 前提 整體機制 寫隔離 讀隔離 工作機制 一階段 二階段-回滾 二階段-提交 附錄 回滾日志表 前提 基于支持本地 ACID 事務的關系型數據庫。 Java 應用,通過 JDBC 訪問數據庫。 整體機制 兩階段提交協議的演變: 一階段:業務數據和回滾日志記錄在同一個本地事務中提交,釋放本地鎖和連接資源。 二階段: 提交異步化,非常快速地完成。 回滾通過一階段的回滾日志進行反向補償。 寫隔離 ...

    精品国产乱码久久久久久蜜桃不卡