您好,登錄后才能下訂單哦!
開始刷leetcode算法題 今天做的是“買賣股票的最佳時(shí)機(jī)”
題目要求
給定一個(gè)數(shù)組,它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。
注意:你不能同時(shí)參與多筆交易(你必須在再次購買前出售掉之前的股票)。
看到這個(gè)題目 最初的想法是蠻力法
通過兩層循環(huán) 不斷計(jì)算不同天之間的利潤及利潤和
下面上代碼
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ self.allbuy1 = [] #單次買賣的差值數(shù)組 (可能為負(fù)) self.allbuy2 = [] #所有可能買賣的利潤數(shù)組 (可能為負(fù)) # allbuy1和allbuy2的區(qū)別為一個(gè)是單次買賣 一個(gè)是多次買賣和 self.curbuy(prices,0,0) #prices 為價(jià)格表 0:初始 0: #print(self.allbuy1) #print(self.allbuy2) return self.picBigest(self.allbuy2) def buyticket(self,prilist,a,b): #list:放入的價(jià)格數(shù)組 a:上一次買入的價(jià)格 b:今天賣出的價(jià)格 return prilist[b] -prilist[a] #返回 賺取得價(jià)格 def curbuy(self,plist,x,result): #plist:價(jià)格數(shù)組 x:當(dāng)天的數(shù)組坐標(biāo) result: 利潤 obj=result #固定上一次的價(jià)格 保存為上一個(gè)遞歸 lens=len(plist) #天數(shù) for i in range(x,lens-1): for j in range(i+1,lens): temp=self.buyticket(plist,i, j) self.allbuy1.append(temp) self.allbuy2.append(temp) #單次利潤放入數(shù)組 result = obj + temp #將之前的利潤加上今天的利潤 if(x>=2): #如果買入是第2+1天以后 則可以加上之前的利潤 self.allbuy2.append(result) #多次買賣利潤放入數(shù)組 self.curbuy(plist,j+1,result) #遞歸 j+1:賣出的后一天 result:利潤 def picBigest(self,reslist): big=0 for i in reslist: if (i>big): big=i print(big) return big if __name__ == '__main__': test=Solution() prices = [5,7,3,8] # 輸入的每日股票數(shù)組 test.maxProfit(prices)
分析:
這個(gè)代碼理解起來簡單 就是將所有可能都放入數(shù)組中 找出最大一個(gè)可能
將這個(gè)代碼提交時(shí) 顯示 超出時(shí)間限制 確實(shí) 如果輸入的數(shù)組長度非常大時(shí) 計(jì)算量巨大 出現(xiàn)錯(cuò)誤
——————————————————————————————————————————————————————————————————————————————
更換思路:利用貪心算法解決此事
首先介紹 一下貪心算法: 對問題只對當(dāng)前情況進(jìn)行最優(yōu)解處理,之后發(fā)生什么對之前的決定都不改變。簡單的說就是一個(gè)局部最優(yōu)解的過程
介紹個(gè)例子就明白了: 找零錢問題
假設(shè)有面值為5元、2元、1元、5角、2角、1角的貨幣,需要找給顧客4元6角現(xiàn)金,為使付出的貨幣的數(shù)量最少
介紹完了貪心算法簡單思想 就利用該方法解決對應(yīng)問題
在已知股票價(jià)格走勢情況下 只需要對下一天進(jìn)行判斷 如果漲了 則買 如果跌了則賣 這樣收益會(huì)保持固定增長
當(dāng)然了 有人會(huì)提出 我可以選擇不賣等幾天再賣 或不買等幾天再買 的方式 一樣可以保持增長 但是如圖
如果在第2天買入 3天賣出 4天買入 5天賣出 收益為A+B
如果在第2天買入 5天賣出 收益為 C
明顯得出A+B大于C 所以貪心法在這種情況非常適用并且肯定得到最優(yōu)解
直接上代碼
class Solution(object): def maxProfit(self, prices): profit = 0 for day in range(len(prices)-1): differ = prices[day+1] - prices[day] if differ > 0: profit += differ return profit if __name__ == '__main__': test=Solution() prices = [5,7,3,9] # 輸入的每日股票數(shù)組 print(test.maxProfit(prices))
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持億速云。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。