一、寫(xiě)在前面
為什么要在LeetCode刷題？大家都知道不管是校招還是社招算法題是必考題，而這一部分恰巧是大多數(shù)人的短板悦穿，所以刷題首先是為了提高自身的編程能力，能夠在算法面試中脫穎而出业踢，拿到滿(mǎn)意的offer栗柒。自己是打算考研的，計(jì)算機(jī)考研數(shù)據(jù)結(jié)構(gòu)也是必考題知举，所以刷題的第二個(gè)原因就是為了鞏固自己的數(shù)據(jù)結(jié)構(gòu)知識(shí)瞬沦。
應(yīng)該如何刷題呢？這兩個(gè)月自己是順序刷題的雇锡，但是總結(jié)的時(shí)候發(fā)現(xiàn)知識(shí)點(diǎn)太零散逛钻，前二十題有棧，鏈表锰提，數(shù)組等等曙痘，自己總結(jié)的時(shí)候沒(méi)有形成一個(gè)完整的體系，也沒(méi)有清晰的分類(lèi)欲账，這不是自己想要的屡江，所以自己后期刷題將采用專(zhuān)題的方式，比如數(shù)組赛不，鏈表惩嘉，二叉樹(shù)等等。
那么第一個(gè)專(zhuān)題就是貪心算法踢故。前20題鏈接【LeetCode】匯總貼（NO.1-20）
自己建了一個(gè)LeetCode刷題群文黎，交流自己的刷題心得惹苗，現(xiàn)在還沒(méi)有到達(dá)預(yù)定的人數(shù)，感興趣的小伙伴可以參加哦耸峭。
為面試而生桩蓉，期待你的加入。
二劳闹、什么是貪心算法
貪心算法在LeetCode共有41個(gè)題目院究，以中等難度居多。那么什么是貪心算法呢本涕？
貪心算法（又稱(chēng)貪婪算法）是指业汰，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇菩颖。也就是說(shuō)样漆，不從整體最優(yōu)上加以考慮，他所做出的是在某種意義上的局部最優(yōu)解晦闰。
貪心算法每一步必須滿(mǎn)足一下條件：
1放祟、可行的：即它必須滿(mǎn)足問(wèn)題的約束。
2呻右、局部最優(yōu)：他是當(dāng)前步驟中所有可行選擇中最佳的局部選擇跪妥。
3、不可取消：即選擇一旦做出窿冯，在算法的后面步驟就不可改變了骗奖。
學(xué)習(xí)貪心算法的時(shí)候可以結(jié)合動(dòng)態(tài)規(guī)劃一起來(lái)學(xué)習(xí)，兩者還是很相似的醒串。
三执桌、今日題目
買(mǎi)賣(mài)股票的最佳時(shí)機(jī) II（122）
給定一個(gè)數(shù)組，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格芜赌。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)仰挣。你可以盡可能地完成更多的交易（多次買(mǎi)賣(mài)一支股票）。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）缠沈。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入膘壶，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 。
隨后洲愤，在第 4 天（股票價(jià)格 = 3）的時(shí)候買(mǎi)入颓芭，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入柬赐，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣(mài)出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 亡问。
注意你不能在第 1 天和第 2 天接連購(gòu)買(mǎi)股票，之后再將它們賣(mài)出。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易州藕，你必須在再次購(gòu)買(mǎi)前出售掉之前的股票束世。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。
四床玻、題目分析
貪心算法毁涉，總是做出在當(dāng)前看來(lái)是最好的選擇，不從整體最優(yōu)上加以考慮锈死，也就是說(shuō)贫堰，只關(guān)心當(dāng)前最優(yōu)解，按照貪心策略待牵，不關(guān)心以后严嗜，我們只關(guān)心當(dāng)前利益。第0天買(mǎi)入洲敢，花費(fèi)prices[0]，第一天賣(mài)出茄蚯，得到prices[1]压彭，那么我們的收獲就是profit = prices[1] - prices[0],那么有兩種情況
（1）當(dāng)profit > 0 時(shí)，趕緊買(mǎi)入賣(mài)出渗常，能賺一筆是一筆壮不。
（2）當(dāng)profit <= 0 時(shí)，再買(mǎi)入賣(mài)出的話(huà)皱碘，那就是傻了询一，虧錢(qián)。
以此方式類(lèi)推下去癌椿，即得最大利潤(rùn)健蕊。
五、代碼實(shí)現(xiàn)
1class Solution:
2 def maxProfit(self, prices):
3 """
4 :type prices: List[int]
5 :rtype: int
6 """
7 profit = 0
8 temp=0
9 for i in range(1,len(prices)):
10 temp=prices[i] - prices[i-1]
11 if temp>0:
12 profit+=temp
13 return profit
【推薦閱讀】
【Python爬蟲(chóng)】初識(shí)爬蟲(chóng)（1）
