开始刷leetcode算法题今天做的是“买卖股票的最佳时机”
<强>题目要求
给定一个数组,它的第i个元素是一支给定股票我第天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票)。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
看到这个题目最初的想法是蛮力法
通过两层循环不断计算不同天之间的利润及利润和
<强>下面上代码
类解决方案(对象):
def maxProfit(自我,价格):
”“”
:价格类型:列表(int)
: rtype: int
”“”
自我。allbuy1=[] #单次买卖的差值数组(可能为负)
自我。allbuy2=[] #所有可能买卖的利润数组(可能为负)
# allbuy1和allbuy2的区别为一个是单次买卖一个是多次买卖和
self.curbuy(价格,0,0)#价格为价格表0:初始0:
#打印(self.allbuy1)
#打印(self.allbuy2)
返回self.picBigest (self.allbuy2)
def buyticket(自我,prilist, a, b)来:#列表:放入的价格数组:上一次买入的价格b:今天卖出的价格
返回prilist [b] -prilist[一]#返回赚取得价格
def curbuy(自我,plist, x,结果):# plist:价格数组x:当天的数组坐标结果:利润
obj=结果#固定上一次的价格保存为上一个递归
镜头=len (plist) #天数
因为我在范围(x, lens-1):
j的范围(我+ 1,镜头):
temp=自我。buyticket (plist, i, j)来
self.allbuy1.append(临时)
self.allbuy2.append(临时)#单次利润放入数组
结果=obj +临时#将之前的利润加上今天的利润
如果(x>=2): #如果买入是第2 + 1天以后则可以加上之前的利润
self.allbuy2.append(结果)#多次买卖利润放入数组
self.curbuy (plist, j + 1,结果)#递归j + 1:卖出的后一天结果:利润
def picBigest(自我,reslist):
大=0
因为我在reslist:
如果(i>大):
大=我
打印(大)
返回大
if __name__==癬_main__”:
测试=解决方案()
价格=(5、7、3、8)#输入的每日股票数组
test.maxProfit(价格)
分析:
这个代码理解起来简单就是将所有可能都放入数组中找出最大一个可能
将这个代码提交时显示超出时间限制确实如果输入的数组长度非常大时计算量巨大出现错误
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
更换思路:利用贪心算法解决此事
首先介绍一下贪心算法:对问题只对当前情况进行最优解处理,之后发生什么对之前的决定都不改变。简单的说就是一个局部最优解的过程
介绍个例子就明白了:找零钱问题
假设有面值为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所以贪心法在这种情况非常适用并且肯定得到最优解
直接上代码
类解决方案(对象):
def maxProfit(自我,价格):
利润=0
天的范围(len(价格)1):=价格(+ 1天)-价格不同(天)
如果在不同;0：
+=利润不同
返回利润
if __name__==癬_main__”:
测试=解决方案()
价格=(5、7、3、9)#输入的每日股票数组
打印(test.maxProfit(价格)
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
