Re: [閒聊] 每日LeetCode已回收

看板Marginalman作者fxfxxxfxx (愛麗絲)時間3年前 (2022/12/23 12:40)推噓2(2推 0噓 3→)

留言5則, 5人參與討論串148/719 (看更多)

309. Best Time to Buy and Sell Stock with Cooldown LeetCode 出了一系列買賣股票問題我全部都是用有效價格來算的，到目前為止還沒遇到不能用的情況這一題可以買賣任意次，只是中間要 CD 一天有效價格指的是，對於某個 i 假如你想在第 i 天買，然後在未來的某一天 j 賣掉在這個條件下的最佳解還要加上直到第 i-2 天前的答案因此總共的獲利會是 prices[j] - prices[i] + ANSWER[i-2] 這就彷彿其實第 i 天的價格是 prices[i] - ANSWER[i-2] 然後只能買賣一次，這兩件事情是等價的，就又回到最基本的買賣單次問題所以可以定義 effected_prices[i] := prices[i] - ANSWER[i-2] 以及 ANSWER[i] = prices[i] - min_{j<i}(effected_prices[j]) 所以只要一直更新最低的有效價格就可以了 class Solution { public: int maxProfit(vector<int>& prices) { int mn_eprice = 1e7; int ppre = 0, pre = 0; for (int price: prices) { int eprice = price - ppre; int now = max(pre, price - mn_eprice); ppre = pre; pre = now; mn_eprice = min(mn_eprice, eprice); } return pre; } }; 寫了一系列的股票買賣問題，全部都可以用一樣的方法解決 121. Best Time to Buy and Sell Stock 最原始的版本，有效價格就是原本的價格 122. Best Time to Buy and Sell Stock II 無限次買賣，有效價格要扣掉 ANSWER[i-1] 123. Best Time to Buy and Sell Stock III 買賣 2 次，是下一題的特例，就在下一題一起講 188. Best Time to Buy and Sell Stock IV 買賣 K 次 (K <= 100) 就分成 K 個有效價格以及 K 個最佳解就可以了 ANSWER[i][k] = max(ANSWER[i-1][k], prices[i] - min_effprices[k]) min_effprices[k] = min(min_effprices[k], prices[i] - ANSWER[i-1][k-1]) 309. Best Time to Buy and Sell Stock with Cooldown 就是今天的題目 714. Best Time to Buy and Sell Stock with Transaction Fee 無限買賣，但每次買賣要付交易費 fee 有效價格是 prices[i] - ANSWER[i-1] + fee 好像全部都能用同一套解掉 :O -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1671770414.A.4A4.html

→

JenniferLope

12/23 12:40, 3年前 , 1^F

12/23 12:40, 1^F

推

pandix

12/23 12:42, 3年前 , 2^F

12/23 12:42, 2^F

→

PyTorch

12/23 12:43, 3年前 , 3^F

12/23 12:43, 3^F