【LeetCode】貪心算法--買賣股票的最佳時(shí)機(jī) II（122）

xbynet 發(fā)布于2019-07-31 11:21 / 503人閱讀

摘要：貪心算法每一步必須滿足一下條件可行的即它必須滿足問題的約束。四題目分析貪心算法，總是做出在當(dāng)前看來是最好的選擇，不從整體最優(yōu)上加以考慮，也就是說，只關(guān)心當(dāng)前最優(yōu)解，按照貪心策略，不關(guān)心以后，我們只關(guān)心當(dāng)前利益。

一、寫在前面

為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數(shù)人的短板，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中脫穎而出，拿到滿意的offer。自己是打算考研的，計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)也是必考題，所以刷題的第二個(gè)原因就是為了鞏固自己的數(shù)據(jù)結(jié)構(gòu)知識。

應(yīng)該如何刷題呢？這兩個(gè)月自己是順序刷題的，但是總結(jié)的時(shí)候發(fā)現(xiàn)知識點(diǎn)太零散，前二十題有棧，鏈表，數(shù)組等等，自己總結(jié)的時(shí)候沒有形成一個(gè)完整的體系，也沒有清晰的分類，這不是自己想要的，所以自己后期刷題將采用專題的方式，比如數(shù)組，鏈表，二叉樹等等。

那么第一個(gè)專題就是貪心算法。前20題鏈接【LeetCode】匯總貼（NO.1-20）

自己建了一個(gè)LeetCode刷題群，交流自己的刷題心得，現(xiàn)在還沒有到達(dá)預(yù)定的人數(shù)，感興趣的小伙伴可以參加哦，個(gè)人微信：wxb950917。

為面試而生，期待你的加入。
二、什么是貪心算法

貪心算法在LeetCode共有41個(gè)題目，以中等難度居多。那么什么是貪心算法呢？

貪心算法（又稱貪婪算法）是指，在對問題求解時(shí)，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解。

貪心算法每一步必須滿足一下條件：

　　1、可行的：即它必須滿足問題的約束。

　　2、局部最優(yōu)：他是當(dāng)前步驟中所有可行選擇中最佳的局部選擇。

　　3、不可取消：即選擇一旦做出，在算法的后面步驟就不可改變了。

學(xué)習(xí)貪心算法的時(shí)候可以結(jié)合動態(tài)規(guī)劃一起來學(xué)習(xí)，兩者還是很相似的。

三、今日題目

買賣股票的最佳時(shí)機(jī) II（122）

給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。

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

注意：你不能同時(shí)參與多筆交易（你必須在再次購買前出售掉之前的股票）。

示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買入，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。

 隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買入，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。

示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買入，在第 5 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。

 注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。
 因?yàn)檫@樣屬于同時(shí)參與了多筆交易，你必須在再次購買前出售掉之前的股票。

示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 所以最大利潤為 0。

四、題目分析

貪心算法，總是做出在當(dāng)前看來是最好的選擇，不從整體最優(yōu)上加以考慮，也就是說，只關(guān)心當(dāng)前最優(yōu)解，按照貪心策略，不關(guān)心以后，我們只關(guān)心當(dāng)前利益。第0天買入，花費(fèi)prices[0]，第一天賣出，得到prices[1]，那么我們的收獲就是profit = prices[1] - prices[0],那么有兩種情況

（1）當(dāng)profit > 0 時(shí)，趕緊買入賣出，能賺一筆是一筆。

（2）當(dāng)profit <= 0 時(shí)，再買入賣出的話，那就是傻了，虧錢。

以此方式類推下去，即得最大利潤。

五、代碼實(shí)現(xiàn)

class Solution:

def maxProfit(self, prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    profit = 0
    temp=0
    for i in range(1,len(prices)):
        temp=prices[i] - prices[i-1]
        if temp>0:
            profit+=temp
    return profit

【推薦閱讀】

【Python爬蟲】初識爬蟲（1）

用Python來一場人工造雪

機(jī)器學(xué)習(xí)實(shí)戰(zhàn)--住房月租金預(yù)測（1）

Python之禪