摘要:關(guān)鍵字,,算法,,動態(tài)規(guī)劃,上關(guān)于主題的題目有四個這四個題目難度依次遞增。其中第四個問題是尋求一個通解,在給定和最大買賣次數(shù)的情況下,求最大收益。首先大致的解題方向是動態(tài)規(guī)劃,這個應(yīng)該不難想到。之后就是怎么找到狀態(tài),怎么列狀態(tài)轉(zhuǎn)移方程。
關(guān)鍵字:leetcode,Best Time To Buy And Sell Stock,算法,algorithm,動態(tài)規(guī)劃,dynamic programming
leetcode 上關(guān)于Best Time to Buy and Sell Stock主題的題目有四個:
https://leetcode.com/problems...
https://leetcode.com/problems...
https://leetcode.com/problems...
https://leetcode.com/problems...
這四個題目難度依次遞增。大致意思就是,給我們一個 List
首先大致的解題方向是動態(tài)規(guī)劃,這個應(yīng)該不難想到。之后就是怎么找到狀態(tài),怎么列狀態(tài)轉(zhuǎn)移方程。考慮某一天的情況,可以有如下三種狀態(tài):
當(dāng)天買入
當(dāng)天賣出
當(dāng)天什么也沒做
因為這個題目我們要找到最大收益,所以,如果最后一天的狀態(tài)是買入的話,那么其收益一定不是最大的,因為最后一天買入的話,就沒有機會賣出了。那么,上面的三個狀態(tài)可以減少到兩個:
當(dāng)天賣出。
賣出,但是不在當(dāng)天(即在前面的某一天)。
所以,我們用 soldAtToday[k] 來表示當(dāng)天賣出且賣出的時候交易了 k 手的時候的最大收益,soldNotAtToday[k] 代表在之前某天賣出,且當(dāng)前交易手數(shù)為 k 的時候的最大收益。那么,狀態(tài)轉(zhuǎn)移方程就可以用如下偽代碼描述:
soldAtToday[k] = max(soldAtYesterday[k] + price, soldNotAtYesterday[k - 1] + price); soldNotAtToday[k] = max(soldAtYesterday[k], soldNotAtYesterday[k]);
其中,k 是交易次數(shù)。需要注意的是soldAtToday[k] = max(soldAtYesterday[k] + price, soldNotAtYesterday[k - 1] + price);中第一個備選項是soldAtYesterday[k],而不是soldAtYesterday[k - 1],其含義就是,把本應(yīng)該昨天賣的延長一天到今天賣,所以交易次數(shù)還是 k 。
具體實現(xiàn)的時候,我們發(fā)現(xiàn) soldAtToday 和 soldNotAtToday 都是只依賴于 soldAtYesterday 和 soldNotAtYesterday,所以我們可以利用兩個長度為 k + 1 的數(shù)組來完成 today 和 yesterday 數(shù)據(jù)的存儲。
package BestTimeToBuyAndSellStock.VersionIV; @SuppressWarnings("Duplicates") class Solution { private int quickSolve(int[] prices) { int len = prices.length, profit = 0; for (int i = 1; i < len; i++) { // as long as there is a price gap, we gain a profit. if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]; } return profit; } public int maxProfit(int k, int[] prices) { if (prices == null || prices.length <= 1 || k <= 0) { return 0; } int len = prices.length; if (k >= len / 2) return quickSolve(prices); int today = 1; int yesterday = 0; int[][] soldAt = new int[2][k + 1]; int[][] soldNotAt = new int[2][k + 1]; soldAt[today][0] = 0; soldAt[yesterday][0] = 0; soldNotAt[today][0] = 0; soldNotAt[yesterday][0] = 0; for (int i = 0; i < k + 1; i++) { soldAt[yesterday][i] = 0; soldNotAt[yesterday][i] = 0; } for (int i = 1; i < prices.length; i++) { int price = prices[i] - prices[i - 1]; for (int j = 1; j < k + 1; j++) { soldAt[today][j] = Math.max( soldAt[yesterday][j] + price, soldNotAt[yesterday][j - 1] + price ); soldNotAt[today][j] = Math.max( soldAt[yesterday][j], soldNotAt[yesterday][j] ); } int tmp = yesterday; yesterday = today; today = tmp; } return Math.max(soldAt[yesterday][k], soldNotAt[yesterday][k]); } }
觀察代碼發(fā)現(xiàn),開頭多了一個 quickSolve 。這是因為,如果直接把上面我們描述的算法實現(xiàn)出來,提交上去,會出現(xiàn) TimeLimted 的問題。仔細分析了一下超時的用例,發(fā)現(xiàn)他們的特征是 k 很大。其實,當(dāng) k 大于 prices.length / 2 的時候,就相當(dāng)于沒有 k 的限制,即隨便買賣了,因為不考慮當(dāng)天買當(dāng)天賣的情況,或者把當(dāng)天買賣的收益虛擬的記為 0 。那么我們的算法就退化成最簡單的情況,于是使用一個 quickSolve 來解決即可。
這個題目也對我們?nèi)粘9ぷ魈峁┝藛⑹荆撼霈F(xiàn)問題了,找到瓶頸,分析特征,然后突破。
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/69203.html
摘要:雙指針法復(fù)雜度時間空間思路根據(jù)買賣股票的特性,我們必須先低價買,再高價賣,這個找最大收益的過程實際上是找到目前為之的最低價。我們可以利用這個之前計算的結(jié)果降低時間復(fù)雜度不過代價是額外空間,所以需要把到的最大收益存在數(shù)組中。 Best Time to Buy and Sell Stock I Say you have an array for which the ith element...
摘要:分析因為當(dāng)前日期買賣股票會受到之前日期買賣股票行為的影響,首先考慮到用解決。所以我們可以用兩個數(shù)組分別記錄當(dāng)前持股跟未持股的狀態(tài)。 Best Time to Buy and Sell Stock with Cooldown Say you have an array for which the ith element is the price of a given stock on ...
摘要:示例輸入輸出解釋對應(yīng)的交易狀態(tài)為買入賣出冷凍期買入賣出思路這道題使用動態(tài)規(guī)劃。狀態(tài)表示當(dāng)天休息能夠獲得的最大價值,表示當(dāng)天持有股票能夠獲得的最大價值,表示當(dāng)天持有股票能夠獲得的最大價值。 Description Say you have an array for which the ith element is the price of a given stock on day i. ...
摘要:微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容,進行補充,并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要:題目要求有一個整數(shù)數(shù)組,每一位上的值代表那一天的股票價格。現(xiàn)在假設(shè)最多能夠進行次交易,問最大的收入是多少思路和代碼這里采用了動態(tài)編程的思想。 題目要求 Say you have an array for which the ith element is the price of a given stock on day i. Design an algorithm to find t...
閱讀 1618·2021-11-22 13:53
閱讀 2848·2021-11-15 18:10
閱讀 2755·2021-09-23 11:21
閱讀 2491·2019-08-30 15:55
閱讀 475·2019-08-30 13:02
閱讀 752·2019-08-29 17:22
閱讀 1659·2019-08-29 13:56
閱讀 3455·2019-08-29 11:31