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