python買賣股票的最佳時機(基于貪心_蠻力算法)

來源：中文源碼網????瀏覽： 次????日期：2019年11月5日

【下載文檔:??python買賣股票的最佳時機(基于貪心_蠻力算法).txt?】

(友情提示:右鍵點上行txt文檔名->目標另存為)

python買賣股票的最佳時機(基于貪心/蠻力算法)開始刷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 bigif __name__ == '__main__':

test=Solution()

prices = [5,7,3,8] # 輸入的每日股票數組

test.maxProfit(prices)分析：

這個代碼理解起來簡單 就是將所有可能都放入數組中 找出最大一個可能

將這個代碼提交時 顯示 超出時間限制 確實 如果輸入的數組長度非常大時 計算量巨大 出現錯誤

——————————————————————————————————————————————————————————————————————————————

更換思路：利用貪心算法解決此事

首先介紹 一下貪心算法： 對問題只對當前情況進行最優解處理，之后發生什么對之前的決定都不改變。簡單的說就是一個局部最優解的過程

介紹個例子就明白了： 找零錢問題

假設有面值為5元、2元、1元、5角、2角、1角的貨幣，需要找給顧客4元6角現金，為使付出的貨幣的數量最少

首先找出小于4元6角的最大面值(2元)

其次找出小于2元6角的最大面值(2元)

接著找出小于6角的最大面值(5角)

最后找出小于1角的最大面值(1角) ---付出4張紙幣介紹完了貪心算法簡單思想 就利用該方法解決對應問題

在已知股票價格走勢情況下 只需要對下一天進行判斷 如果漲了 則買 如果跌了則賣 這樣收益會保持固定增長

當然了 有人會提出 我可以選擇不賣等幾天再賣 或不買等幾天再買 的方式 一樣可以保持增長 但是如圖如果在第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))

以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持中文源碼網。

親,試試微信掃碼分享本頁!?*^_^*

總結

以上是生活随笔為你收集整理的python买卖股票_python买卖股票的最佳时机（基于贪心_蛮力算法）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。