【121】Best Time to Buy and Sell Stock （2018年11月25日重新復(fù)習(xí)）

給一個(gè)數(shù)組代表股票每天的價(jià)格，只能有一次交易，即一次買(mǎi)入一次賣(mài)出，求最大收益。

題解：用一個(gè)變量維護(hù)此時(shí)的最大收益和最小成本。遍歷數(shù)組求值。

1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 int minPrice = INT_MAX; 5 int maxProfit = 0; 6 for (auto ele : prices) { 7 minPrice = min(ele, minPrice); 8 maxProfit = max(maxProfit, (ele - minPrice)); 9 } 10 return maxProfit; 11 } 12 }; View Code

?2018年11月25日，這次一次 AC 了。

1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 const int n = prices.size(); 5 if (n < 2) {return 0;} 6 int buy = prices[0], sell = 0; 7 int ret = 0; 8 for (int i = 1; i < n; ++i) { 9 sell = prices[i]; 10 if (buy < sell) { 11 ret = max(sell - buy, ret); 12 } else { 13 buy = prices[i]; 14 } 15 } 16 return ret; 17 } 18 }; View Code

?

【122】 Best Time to Buy and Sell Stock II （2018年11月25日復(fù)習(xí)）

這題是給了一個(gè)數(shù)組代表股票每天的價(jià)格，可以做任意次的交易，但是不能同時(shí)持有多支股票。（每次的操作方式只能是先買(mǎi)，然后賣(mài)了，再買(mǎi)。不能在賣(mài)了之前再次買(mǎi)入。）

題解：這題我是用了貪心，每次發(fā)現(xiàn)今天的價(jià)格比昨天的價(jià)格高，就在昨天買(mǎi)入，今天賣(mài)出。

1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 const int n = prices.size(); 5 int ret = 0; 6 for (int i = 1; i < n; ++i) { 7 if (prices[i] - prices[i-1] > 0) { 8 ret += prices[i] - prices[i-1]; 9 } 10 } 11 return ret; 12 } 13 }; View Code

還可以用dp解答，dp通用一些。以后那些變種都是dp的變種。

?

【123】Best Time to Buy and Sell Stock III （2018年11月30日，復(fù)習(xí)）

給了一個(gè)數(shù)組代表每天股票的價(jià)格，只能做兩次交易，問(wèn)最大的盈利是多少。（還跟原來(lái)的條件是一樣的，不支持同時(shí)持有多股票，每次操作方式都是先買(mǎi)，賣(mài)了，然后才能再買(mǎi)。）

題解：這題我用了類(lèi)似動(dòng)態(tài)規(guī)劃這種做法，狀態(tài)其實(shí)很簡(jiǎn)單，四個(gè)狀態(tài)，分別代表第一次買(mǎi)入后的錢(qián)，第一次賣(mài)出后的錢(qián)，第二次買(mǎi)入后的錢(qián)，第二次賣(mài)出后的錢(qián)。最后這四個(gè)數(shù)可能都是負(fù)數(shù)，這個(gè)時(shí)候不買(mǎi)最好了。?

1 class Solution { 2 public: 3 int maxProfit(vector<int>& prices) { 4 const int n = prices.size(); 5 if (n == 0) {return 0;} 6 vector<int> g(4, INT_MIN); 7 g[0] = -prices[0]; 8 for (int i = 1; i < n; ++i) { 9 g[0] = max(g[0], -prices[i]); 10 g[1] = max(g[1], g[0]+prices[i]); 11 g[2] = max(g[2], g[1]-prices[i]); 12 g[3] = max(g[3], g[2]+prices[i]); 13 } 14 return max(0, max(g[1], g[3])); 15 } 16 }; View Code

?

?

【188】 Best Time to Buy and Sell Stock IV

?

【309】 Best Time to Buy and Sell Stock with Cooldown

?

【714】 Best Time to Buy and Sell Stock with Transaction Fee

?

轉(zhuǎn)載于:https://www.cnblogs.com/zhangwanying/p/9360841.html

總結(jié)

以上是生活随笔為你收集整理的【LeetCode+51nod】股票低买高卖N题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。