Leetcode第121題到123題連續(xù)出現(xiàn)了三道買賣股票相關(guān)的題目,一年前的網(wǎng)易筆試和半年前的百度面試都遇到過121題,不過不用慌,看完本文,你一定能夠完美解決買賣股票的問題。那么我們由易到難,依次介紹這三道題目。
best time to buy and sell stock
121題題目是這樣的:
在所有的過程中,我們只允許一次的買賣,基于這個(gè)問題,我們得到了下面的兩種解法。
解法1根據(jù)題意,我們只需要找出數(shù)組中最大的差值即可,即 max(prices[j] – prices[i]) ,i < j。
如何得到最大的差值,只需要一次遍歷即可,在遍歷的用一個(gè)變量記錄遍歷到當(dāng)前時(shí)的最小值即可。時(shí)間復(fù)雜度為O(n).
相關(guān)的實(shí)現(xiàn)代碼如下:
classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length2){return0;}intmin=prices[0];intprofit=0;//第i天的價(jià)格可以看作是買入價(jià)也可以看作是賣出價(jià)for(inti=1;i//找到更低的買入價(jià)if(min>prices[i]){//更新買入價(jià)min=prices[I];}//當(dāng)天的價(jià)格不低于買入價(jià)else{//如果當(dāng)天買出的價(jià)格比之前賣出的價(jià)格高if(profit//更新賣出價(jià)profit=prices[i]-min;}}}returnprofit;}}
解法2
第二題的解法是我在面試百度的時(shí)候想到的,應(yīng)用的是求數(shù)組中和最大的連續(xù)子數(shù)組序列的思路,這種思路又被稱為Kadane's Algorithm。我們有兩個(gè)問題:
如何轉(zhuǎn)化為求數(shù)組中的和最大的連續(xù)子序列?相鄰兩個(gè)數(shù)作差即可,這樣的話子序列的和就是我們?cè)谧有蛄虚_始賣出股票,在子序列最后買回股票所能得到的收益。
那么什么是Kadane's Algorithm呢?
kadane算法利用了數(shù)學(xué)歸納法的思想。簡單來講就是,隨意給你一個(gè)現(xiàn)成的數(shù)組,比如說?2, 1, ?3, 4, ?1, 2, 1, ?5, 4,讓你求其中的最大子列和,并不是容易的事情。但如果我們能從第一個(gè)數(shù)開始,隨著數(shù)組的擴(kuò)充,始終對(duì)其最大子列和保持跟蹤,就可以輕易的求出任意一個(gè)數(shù)組的最大子列和。換言之,長度n的數(shù)組我們不會(huì)求,長度為一的總能算出來吧?長度為一的算出來了,二也就能算出來,二算出來了,三就能算出來,以此類推,用這種根據(jù)i求i+1的思想,我們就能達(dá)到最終目的。
詳細(xì)的分析一下,往一個(gè)長度為i的數(shù)組后面插入第i+1個(gè)數(shù),這時(shí),數(shù)組的最大子列只有兩種情況,要么包括第i+1個(gè)數(shù),要么不包括第i+1個(gè)數(shù)。即:
maxsubarraum = max(以第i+1個(gè)數(shù)結(jié)尾的子列和, 不以第i+1個(gè)數(shù)結(jié)尾的子列和)。*
先計(jì)算前者,以第i+1個(gè)數(shù)結(jié)尾的子列和怎么算呢?很簡單,要么它是以第i個(gè)數(shù)結(jié)尾的子列作為前綴,要么它不以之作為前綴。假設(shè)第i+1個(gè)數(shù)為x,那么:
以第i+1個(gè)數(shù)結(jié)尾的子列和 = max(x,以第i個(gè)數(shù)結(jié)尾的子列和+x) (1)。
再計(jì)算后者,也就是不以第i+1個(gè)數(shù)結(jié)尾的子列和。這啥意思呢?其實(shí)就是插入第i+1個(gè)數(shù)之前的數(shù)組的最大子列和嘛。我們的數(shù)學(xué)歸納思想也就體現(xiàn)在這里,如果你還看不明白,我們將*式改寫:
數(shù)列長度i+1的最大子列和 = max(以第i+1個(gè)數(shù)結(jié)尾的子列和, 數(shù)列長度i的最大子列和)。(2)
看到了吧,無論(1)式還是(2)式,后一種情況都可以由前一種情況推出,妥妥的數(shù)學(xué)歸納。我們的算法只要從i=1開始,一步一步按照上面的規(guī)則走下去,那么任意一個(gè)數(shù)列的最大子列和就能求出來了!
classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;intmaxCur=0;intmaxSoFar=0;for(inti=1;i0,Math.max(prices[i]-prices[i-1],maxCur+prices[i]-prices[i-1]));maxSoFar=Math.max(maxCur,maxSoFar);}returnmaxSoFar;}}
122.best time to buy and sell stockII
這道題的描述如下:
這道題允許無限次的買賣,簡直太簡單了吧,只要后一天的價(jià)值比前一天的大,那就買賣唄。不忍吐槽的一道題,代碼如下:
classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;intmaxProf=0;for(inti=1;iprices[i-1]?prices[i]-prices[i-1]:0);}returnmaxProf;}}
123 best time to buy and sell stock III
這一題還是比較難的,題目描述如下:
我們只允許最多兩次的買賣,這可如何是好?我們同樣提供兩種思路:
解法1這個(gè)問題可以轉(zhuǎn)換成Best Time to Buy and Sell Stock I問題。
兩次股票交易的核心是可以定義一個(gè)交易點(diǎn),在這個(gè)交易點(diǎn)之前可以做一次交易(賺的最大數(shù)目的錢為firstProf),在這個(gè)交易點(diǎn)之后可以做一個(gè)交易(賺的最大數(shù)目的錢是secondProf)。那么要求的是max(firstProf+secondProf)。但是這個(gè)方法的時(shí)間復(fù)雜度是O(N^2),空間復(fù)雜度是O(1)。leetcode中顯示超時(shí)。
可以使用兩次掃描的方法避免上面的雙重循環(huán)。
不同于Best Time to Buy and Sell Stock I中定義的初始狀態(tài)A[i]表示第i天賣出掙的最大數(shù)目的錢,這個(gè)更進(jìn)一步直接定義A[i]表示前i天賺的最大數(shù)目的錢。minPrice表示從第0天到第i-1天中的最低價(jià)格。
A[0]=0。(初始狀態(tài))A[1]=max(prices[1]-prices[0],A[0])A[2]=max(prices[2]-minPrice,A[1]).....
即A[i]=max(price[i]-minPrice,A[i-1]).
另外一次掃描從數(shù)組后向前掃描,定義B[i]表示從第i天到最后一天n能賺的最大數(shù)目的錢。
maxPrice表示第i+1天到n天的最高價(jià)格。B[n]=0。(初始狀態(tài))B[n-1]=max(maxPrice-prices[n-1],B[n])B[n-2]=max(maxPrice-prices[n-2],B[n-1]).....
即B[i]=max(maxPrice-prices[i],B[i+1])
那么以第i天為分割點(diǎn)能賺的最多數(shù)目的錢為A[i]+B[i]問題的解為max{A[i]+B[i]}。0<=i<=n。時(shí)間復(fù)雜度是O(N),空間復(fù)雜度是O(N)。
classSolution{publicintmaxProfit(int[]prices){if(prices==null||prices.length<2)return0;int[]asc=newint[prices.length];int[]desc=newint[prices.length];intn=prices.length;intminprice=prices[0];intmaxProf=0;asc[0]=0;for(inti=1;iasc[i]=Math.max(prices[i]-minprice,maxProf);minprice=Math.min(prices[i],minprice);maxProf=asc[i];}desc[prices.length-1]=0;maxProf=0;intmaxprice=prices[prices.length-1];for(inti=prices.length-2;i>=0;i--){desc[i]=Math.max(maxprice-prices[i],maxProf);maxprice=Math.max(maxprice,prices[i]);maxProf=desc[i];}maxProf=0;for(inti=0;iasc[i]+desc[i]);}returnmaxProf;}}
解法2
第二種解法的核心是假設(shè)手上最開始只有0元錢,那么如果買入股票的價(jià)格為price,手上的錢需要減去這個(gè)price,如果賣出股票的價(jià)格為price,手上的錢需要加上這個(gè)price。
因此我們定義了4個(gè)狀態(tài):
Buy1[i]表示前i天做第一筆交易買入股票后剩下的最多的錢;Sell1[i]表示前i天做第一筆交易賣出股票后剩下的最多的錢;Buy2[i]表示前i天做第二筆交易買入股票后剩下的最多的錢;Sell2[i]表示前i天做第二筆交易賣出股票后剩下的最多的錢;
那么假設(shè)我們?cè)诘趇天時(shí)第二次賣出股票,我們賣出股票可以獲得Buy2[i-1]+prices[i]的錢,假設(shè)在第i天前已經(jīng)完成了兩筆交易,那么我們最多的錢是Sell2[i-1],因此Sell2[i]=max{Sell2[i-1],Buy2[i-1]+prices[I]}同樣的道理,假設(shè)我們?cè)诘趇天時(shí)第二次買入股票,我們手中的錢是Sell[i-1]-prices[i],假設(shè)我們?cè)诘趇天錢已經(jīng)賣出了兩次股票,那么我們最多的錢是Buy2[i-1],因此Buy2[i]=max{Buy2[i-1],Sell[i-1]-prices[I]}同樣的道理我們還可以得到:Sell1[i]=max{Sell[i-1],Buy1[i-1]+prices[I]}Buy1[i]=max{Buy[i-1],-prices[I]}
可以發(fā)現(xiàn)上面四個(gè)狀態(tài)都是只與前一個(gè)狀態(tài)有關(guān),所以可以不使用數(shù)組而是使用變量來存儲(chǔ)即可。
-
人工智能
+關(guān)注
關(guān)注
1791文章
47206瀏覽量
238274
原文標(biāo)題:如何買賣股票?不要慌,我有妙招!
文章出處:【微信號(hào):atleadai,微信公眾號(hào):LeadAI OpenLab】歡迎添加關(guān)注!文章轉(zhuǎn)載請(qǐng)注明出處。
發(fā)布評(píng)論請(qǐng)先 登錄
相關(guān)推薦
評(píng)論