8000 stock · hitzzc/go-leetcode@71b7dd8 · GitHub
[go: up one dir, main page]
Skip to content

Commit 71b7dd8

Browse files
hitzzchitzzc
committed
stock
1 parent e3bd6fd commit 71b7dd8

File tree

6 files changed

+94
-0
lines changed

6 files changed

+94
-0
lines changed

‎README.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -107,6 +107,9 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
107107
#### [118. pascal's triangle](https://github.com/hitzzc/go-leetcode/tree/master/pascals_triangle)
108108
#### [119. pascal's triangle II](https://github.com/hitzzc/go-leetcode/tree/master/pascals_triangle_II)
109109
#### [120. triangle](https://github.com/hitzzc/go-leetcode/tree/master/triangle)
110+
#### [121. Best Time to Buy and Sell Stock](https://github.com/hitzzc/go-leetcode/tree/master/best_time_to_buy_and_sell_stock)
111+
#### [122. Best Time to Buy and Sell Stock II](https://github.com/hitzzc/go-leetcode/tree/master/best_time_to_buy_and_sell_stock_II)
112+
#### [123. Best Time to Buy and Sell Stock III](https://github.com/hitzzc/go-leetcode/tree/master/best_time_to_buy_and_sell_stock_III)
110113
#### [124. binary tree maximum path sum](https://github.com/hitzzc/go-leetcode/tree/master/binary_tree_maximum_path_sum)
111114
#### [125. valid palindrome](https://github.com/hitzzc/go-leetcode/tree/master/valid_palindrome)
112115
#### [126. word ladder II](https://github.com/hitzzc/go-leetcode/tree/master/word_ladder_II)
@@ -153,6 +156,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
153156
#### [174. Dungeon Game](https://github.com/hitzzc/go-leetcode/tree/master/dungeon_game)
154157
#### [179. Largest Number](https://github.com/hitzzc/go-leetcode/tree/master/largest_number)
155158
#### [187. Repeated DNA Sequences](https://github.com/hitzzc/go-leetcode/tree/master/repeated_dna_sequences)
159+
#### [188. Best Time to Buy and Sell Stock IV](https://github.com/hitzzc/go-leetcode/tree/master/best_time_to_buy_and_sell_stock_IV)
156160
#### [189. Rotate Array](https://github.com/hitzzc/go-leetcode/tree/master/rotate_array)
157161
#### [190. Reverse Bits](https://github.com/hitzzc/go-leetcode/tree/master/reverse_bits)
158162
#### [191. Number of 1 Bits](https://github.com/hitzzc/go-leetcode/tree/master/number_of_1bits)
@@ -221,6 +225,7 @@ Golang solution for leetcode. For each problem, there is a simple *_test.go to t
221225
#### [304. Range Sum Query 2D - Immutable](https://github.com/hitzzc/go-leetcode/tree/master/range_sum_query_immutable)
222226
#### [306. Additive Number](https://github.com/hitzzc/go-leetcode/tree/master/additive_number)
223227
#### [307. Range Sum Query - Mutable](https://github.com/hitzzc/go-leetcode/tree/master/range_sum_query_mutable)
228+
#### [309. Best Time to Buy and Sell Stock with Cooldown](https://github.com/hitzzc/go-leetcode/tree/master/best_time_to_buy_and_sell_stock_with_cooldown)
224229

225230

226231

‎best_time_to_buy_and_sell_stock/best_time_to_buy_and_sell_stock.cpp

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
class Solution {
2+
public:
3+
int maxProfit(vector<int>& prices) {
4+
if (prices.size() == 0) return 0;
5+
int min = prices[0];
6+
int max = 0;
7+
for (int i = 1; i < prices.size(); ++i) {
8+
int diff = prices[i] - min;
9+
if (diff > max) max = diff;
10+
if (prices[i] < min) min = prices[i];
11+
}
12+
return max;
13+
}
14+
};

‎best_time_to_buy_and_sell_stock_II/best_time_to_buy_and_sell_stock_II.cpp

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
class Solution {
2+
public:
3+
int maxProfit(vector<int>& prices) {
4+
if (prices.size() == 0) return 0;
5+
int ret = 0;
6+
for (int i = 0; i < prices.size()-1; ++i) {
7+
if (prices[i+1] > prices[i]) ret += prices[i+1] - prices[i];
8+
}
9+
return ret;
10+
}
11+
};

‎best_time_to_buy_and_sell_stock_III/best_time_to_buy_and_sell_stock_III.cpp

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
class Solution {
2+
public:
3+
int maxProfit(vector<int>& prices) {
4+
if (prices.size() == 0) return 0;
5+
vector<int> fn1(prices.size(), 0);
6+
vector<int> fn2(prices.size(), 0);
7+
int minV = prices[0];
8+
for (int i = 1; i < prices.size(); ++i) {
9+
fn1[i] = max(fn1[i-1], prices[i]-minV);
10+
minV = min(minV, prices[i]);
11+
}
12+
int maxV = prices[prices.size()-1];
13+
for (int i = prices.size()-2; i >= 0; --i) {
14+
fn2[i] = max(fn2[i+1], maxV-prices[i]);
15+
maxV = max(maxV, prices[i]);
16+
}
17+
int ret = 0;
18+
for (int i = 0; i < fn1.size(); ++i) {
19+
ret = max(ret, fn1[i] + fn2[i]);
20+
}
21+
return ret;
22+
}
23+
};

‎best_time_to_buy_and_sell_stock_IV/best_time_to_buy_and_sell_stock_IV.cpp

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
class Solution {
2+
public:
3+
int maxProfit(int k, vector<int>& prices) {
4+
if (prices.size() < 2) return 0;
5+
if (k > prices.size()/2) {
6+
int ret = 0;
7+
for (int i = 0; i < prices.size()-1; ++i) {
8+
if (prices[i+1] - prices[i] > 0) ret += prices[i+1] - prices[i];
9+
}
10+
return ret;
11+
}
12+
vector<vector<int>> dp(k+1, vector<int>(prices.size()+1, 0));
13+
for (int i = 1; i <= k; ++i) {
14+
int maxV = dp[i-1][0] - prices[0];
15+
for (int j = 1; j <= prices.size(); ++j) {
16+
dp[i][j] = max(dp[i][j-1], maxV + prices[j-1]);
17+
if (j < prices.size() && dp[i-1][j] - prices[j] > maxV) {
18+
maxV = dp[i-1][j] - prices[j];
19+
}
20+
}
21+
}
22+
return dp[k][prices.size()];
23+
}
24+
};

‎best_time_to_buy_and_sell_stock_with_cooldown/best_time_to_buy_and_sell_stock_with_cooldown.cpp

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 A9BE ,17 @@
1+
class Solution {
2+
public:
3+
int maxProfit(vector<int>& prices) {
4+
if (prices.size() < 2) return 0;
5+
int buy = -prices[0];
6+
int sell = -1;
7+
int cold = 0;
8+
int tmp;
9+
for (int i = 1; i < prices.size(); ++i) {
10+
tmp = buy;
11+
buy = max(tmp, cold-prices[i]);
12+
cold = max(cold, sell);
13+
sell = tmp+prices[i];
14+
}
15+
return max(sell, cold);
16+
}
17+
};

0 commit comments

Comments
 (0)
0