Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb853d27

Browse files
committed
[Function add]
1. Add leetcode solutions related to the stock buy and sell questions.
1 parentc564493 commitb853d27

4 files changed

+161
-1
lines changed

‎leetcode/123. Best Time to Buy and Sell Stock III.md

Lines changed: 23 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -79,4 +79,26 @@ class Solution {
7979
return first+ second;
8080
}
8181
}
82-
```
82+
```
83+
84+
###Amazon Session
85+
* Method 1: DP
86+
```Java
87+
class Solution {
88+
public int maxProfit(int[] prices) {
89+
if(prices == null || prices.length <= 1) return 0;
90+
int len = prices.length;
91+
int[][] buys = new int[len + 1][3];
92+
int[][] sells = new int[len + 1][3];
93+
buys[1][1] = -prices[0];
94+
buys[1][2] = Integer.MIN_VALUE;
95+
for(int i = 2; i <= len; i++){
96+
for(int j = 1; j <= 2; j++){
97+
buys[i][j] = Math.max(buys[i - 1][j], sells[i - 1][j - 1] - prices[i - 1]);
98+
sells[i][j] = Math.max(sells[i - 1][j], buys[i - 1][j] + prices[i - 1]);
99+
}
100+
}
101+
return Math.max(sells[len][0], Math.max(sells[len][1], sells[len][2]));
102+
}
103+
}
104+
```
Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
##188. Best Time to Buy and Sell Stock IV
2+
3+
###Question
4+
Say you have an array for which the ith element is the price of a given stock on day i.
5+
6+
Design an algorithm to find the maximum profit. You may complete at most k transactions.
7+
8+
Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
9+
10+
```
11+
Example 1:
12+
13+
Input: [2,4,1], k = 2
14+
Output: 2
15+
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
16+
17+
Example 2:
18+
19+
Input: [3,2,6,5,0,3], k = 2
20+
Output: 7
21+
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4.
22+
Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
23+
```
24+
25+
###Solution
26+
* Method 1: dp
27+
1. We need to pay attention to the initialization.
28+
2. Transaction function is same as [123. Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/).
29+
3. If k is larger than prices length, we treat it as question [122. Best Time to Buy and Sell Stock II](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/122.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20II.md).
30+
```Java
31+
class Solution {
32+
public int maxProfit(int k, int[] prices) {
33+
if(k == 0 || prices == null || prices.length <= 1) return 0;
34+
int len = prices.length;
35+
if(k > len) return maxProfit(prices);
36+
int[][] buys = new int[len + 1][k + 1];
37+
int[][] sells = new int[len + 1][k + 1];
38+
for(int i = 2; i <= k; i++){
39+
for(int j = 0; j < i; j++){
40+
buys[j][i] = Integer.MIN_VALUE;
41+
}
42+
}
43+
int sum = 0;
44+
for(int i = 1; i <= k; i++){
45+
sum -= prices[i - 1];
46+
buys[i][i] = sum;
47+
}
48+
for(int i = 2; i <= len; i++){
49+
for(int j = 1; j <= k; j++){
50+
buys[i][j] = Math.max(buys[i - 1][j], sells[i - 1][j - 1] - prices[i - 1]);
51+
sells[i][j] = Math.max(sells[i - 1][j], buys[i - 1][j] + prices[i - 1]);
52+
}
53+
}
54+
int profit = 0;
55+
for(int i = 0; i <= k; i++){
56+
profit = Math.max(profit, sells[len][i]);
57+
}
58+
return profit;
59+
}
60+
61+
private int maxProfit(int[] prices) {
62+
int len = prices.length;
63+
int[] buys = new int[len + 1];
64+
int[] sells = new int[len + 1];
65+
buys[1] = -prices[0];
66+
for(int i = 2; i <= len; i++){
67+
buys[i] = Math.max(buys[i - 1], sells[i - 1] - prices[i - 1]);
68+
sells[i] = Math.max(sells[i - 1], buys[i - 1] + prices[i - 1]);
69+
}
70+
return sells[len];
71+
}
72+
}
73+
```

‎leetcode/309. Best Time to Buy and Sell Stock with Cooldown.md

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -111,6 +111,26 @@ class Solution {
111111
}
112112
```
113113

114+
###Amazon Session
115+
* Method 1: dp
116+
```Java
117+
class Solution {
118+
public int maxProfit(int[] prices) {
119+
if(prices == null || prices.length <= 1) return 0;
120+
int len = prices.length;
121+
int[] buys = new int[len + 1];
122+
int[] sells = new int[len + 1];
123+
int[] cools = new int[len + 1];
124+
buys[1] = -prices[0];
125+
for(int i = 2; i <= len; i++){
126+
buys[i] = Math.max(buys[i - 1], cools[i - 1] - prices[i - 1]);
127+
cools[i] = Math.max(cools[i - 1], sells[i - 1]);
128+
sells[i] = Math.max(buys[i - 1] + prices[i - 1], sells[i - 1]);
129+
}
130+
return sells[len];
131+
}
132+
}
133+
```
114134

115135
###Reference
116136
1.[【LeetCode】309. Best Time to Buy and Sell Stock with Cooldown](https://www.cnblogs.com/jdneo/p/5228004.html)
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
##714. Best Time to Buy and Sell Stock with Transaction Fee
2+
3+
###Question
4+
Your are given an array of integers prices, for which the i-th element is the price of a given stock on day i; and a non-negative integer fee representing a transaction fee.
5+
6+
You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)
7+
8+
Return the maximum profit you can make.
9+
10+
```
11+
Example 1:
12+
13+
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
14+
Output: 8
15+
Explanation: The maximum profit can be achieved by:
16+
Buying at prices[0] = 1
17+
Selling at prices[3] = 8
18+
Buying at prices[4] = 4
19+
Selling at prices[5] = 9
20+
The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
21+
```
22+
23+
Note:
24+
1. 0 < prices.length <= 50000.
25+
2. 0 < prices[i] < 50000.
26+
3. 0 <= fee < 50000.
27+
28+
###Solutions
29+
* Method 1: dp
30+
```Java
31+
class Solution {
32+
public int maxProfit(int[] prices, int fee) {
33+
if(prices == null || prices.length <= 1) return 0;
34+
int len = prices.length;
35+
int[] buys = new int[len + 1];
36+
int[] sells = new int[len + 1];
37+
buys[1] = -prices[0];
38+
for(int i = 2; i <= len; i++){
39+
buys[i] = Math.max(buys[i - 1], sells[i - 1] - prices[i - 1]);
40+
sells[i] = Math.max(sells[i - 1], buys[i - 1] + prices[i - 1] - fee);
41+
}
42+
return sells[len];
43+
}
44+
}
45+
```

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp