Skip to content

Commit 9dccda8

Browse files
SeanforfunSeanforfun
committed
[Function add]
1. Add leetcode solutions.
1 parent c5e44ac commit 9dccda8

6 files changed

+171
-1
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -481,6 +481,8 @@
481481

482482
[307. Range Sum Query - Mutable](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/307.%20Range%20Sum%20Query%20-%20Mutable.md)
483483

484+
[309. Best Time to Buy and Sell Stock with Cooldown](https://github.com/Seanforfun/Algorithm-and-Leetcode/blob/master/leetcode/309.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20with%20Cooldown.md)
485+
484486

485487
## Algorithm(4th_Edition)
486488
Reading notes of book Algorithm(4th Algorithm),ISBN: 9787115293800.

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

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,4 +97,22 @@ class Solution {
9797
return global;
9898
}
9999
}
100+
```
101+
102+
### Third time
103+
1. This time I beat 100%, for each day, we have fixed price, we need to find the minimum price ahead.
104+
* Update the max profit.
105+
* Update the min price.
106+
```Java
107+
class Solution {
108+
public int maxProfit(int[] prices) {
109+
if(prices == null || prices.length == 0) return 0;
110+
int min = prices[0], profit = 0;
111+
for(int i = 0; i < prices.length; i++){
112+
profit = Math.max(profit, prices[i] - min);
113+
min = Math.min(min, prices[i]);
114+
}
115+
return profit;
116+
}
117+
}
100118
```

‎leetcode/122. Best Time to Buy and Sell Stock II.md

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -63,4 +63,45 @@ class Solution {
6363
return result;
6464
}
6565
}
66+
```
67+
68+
### Third time
69+
1. Method 1: Finding the dropping points.
70+
```Java
71+
class Solution {
72+
public int maxProfit(int[] prices) {
73+
if(prices == null || prices.length == 0) return 0;
74+
int profit = 0, pre = -1;
75+
for(int i = 1; i < prices.length; i++){
76+
if(prices[i] < prices[i - 1]){
77+
if(pre != -1) profit += prices[i - 1] - prices[pre];
78+
else profit += prices[i - 1] - prices[0];
79+
pre = i;
80+
}
81+
}
82+
if(pre == -1) return prices[prices.length - 1] - prices[0];
83+
if(pre != prices.length - 1) profit += prices[prices.length - 1] - prices[pre];
84+
return profit;
85+
}
86+
}
87+
```
88+
89+
2. Use dp to solve this question.
90+
* s0(holding a stock): 1. rest 2. sell
91+
* s1(not holding any stock): 1.rest, 2. buy
92+
```Java
93+
class Solution {
94+
public int maxProfit(int[] prices) {
95+
if(prices == null || prices.length == 0) return 0;
96+
int len = prices.length;
97+
int[] s0 = new int[len + 1];
98+
int[] s1 = new int[len + 1];
99+
s0[1] = -prices[0];
100+
for(int i = 2; i <= len; i++){
101+
s0[i] = Math.max(s0[i - 1], s1[i - 1] - prices[i - 1]);
102+
s1[i] = Math.max(s1[i - 1], s0[i - 1] + prices[i - 1]);
103+
}
104+
return s1[len];
105+
}
106+
}
66107
```

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

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -49,4 +49,34 @@ class Solution {
4949
return global[2];
5050
}
5151
}
52+
```
53+
54+
### Second time
55+
1. (Wrong)I tried my best to solve this question but cannot pass one case: [1,2,4,2,5,7,2,4,9,0], maybe I can use recursion to solve this question, but not a good idea.
56+
```Java
57+
class Solution {
58+
public int maxProfit(int[] prices) {
59+
if(prices == null || prices.length == 0) return 0;
60+
int first = 0, second = 0, pre = -1, temp = 0;;
61+
for(int i = 1; i < prices.length; i++){
62+
if(prices[i] < prices[i - 1]){
63+
temp = pre == -1 ? prices[i - 1] - prices[0] : prices[i - 1] - prices[pre];
64+
pre = i;
65+
if(temp >= first){
66+
second = first;
67+
first = temp;
68+
}else if(temp > second) second = temp;
69+
}
70+
}
71+
if(pre == -1) return prices[prices.length - 1] - prices[0];
72+
if(pre != prices.length - 1){
73+
temp = prices[prices.length - 1] - prices[pre];
74+
if(temp >= first){
75+
second = first;
76+
first = temp;
77+
}else if(temp > second) second = temp;
78+
}
79+
return first + second;
80+
}
81+
}
5282
```

‎leetcode/307. Range Sum Query - Mutable.md

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -128,6 +128,61 @@ class NumArray {
128128
return sum2 - sum1;
129129
}
130130
}
131+
/**
132+
* Your NumArray object will be instantiated and called as such:
133+
* NumArray obj = new NumArray(nums);
134+
* obj.update(i,val);
135+
* int param_2 = obj.sumRange(i,j);
136+
*/
137+
```
138+
139+
2. Use segment tree to solve this question.
140+
```Java
141+
class NumArray {
142+
private int[] segment;
143+
private int[] nums;
144+
public NumArray(int[] nums) {
145+
this.segment = new int[nums.length << 2 + 1];
146+
this.nums = nums;
147+
if(nums != null && nums.length != 0) build(1, nums.length, 1);
148+
}
149+
private void build(int l, int r, int k){
150+
if(l == r){
151+
segment[k] = this.nums[l - 1];
152+
}else{
153+
int m = l + ((r - l) >> 1);
154+
build(l, m, k << 1);
155+
build(m + 1, r, k << 1 | 1);
156+
segment[k] = segment[k << 1] + segment[k << 1 | 1];
157+
}
158+
}
159+
public void update(int i, int val) {
160+
update(i + 1, val - this.nums[i], 1, this.nums.length, 1);
161+
this.nums[i] = val;
162+
}
163+
private void update(int i, int diff, int l, int r, int k){
164+
if(l == r) segment[k] += diff;
165+
else{
166+
int mid = l + ((r - l) >> 1);
167+
if(i <= mid) update(i, diff, l, mid, k << 1);
168+
else update(i, diff, mid + 1, r, k << 1 | 1);
169+
segment[k] = segment[k << 1] + segment[k << 1 | 1];
170+
}
171+
}
172+
public int sumRange(int i, int j) {
173+
return sum(i + 1, j + 1, 1, this.nums.length, 1);
174+
}
175+
private int sum(int L, int R, int l, int r, int k){
176+
if(L <= l && R >= r) return segment[k];
177+
else{
178+
int m = l + ((r - l) >> 1);
179+
int sum = 0;
180+
if(L <= m) sum += sum(L, R, l, m, k << 1);
181+
if(R > m) sum += sum(L, R, m + 1, r, k << 1 | 1);
182+
return sum;
183+
}
184+
}
185+
}
131186
/**
132187
* Your NumArray object will be instantiated and called as such:
133188
* NumArray obj = new NumArray(nums);

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

Lines changed: 25 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -39,4 +39,28 @@ class Solution {
3939
return sell[len];
4040
}
4141
}
42-
```
42+
```
43+
44+
### Second time
45+
![Imgur](https://i.imgur.com/N0jPd47.png)
46+
```Java
47+
class Solution {
48+
public int maxProfit(int[] prices) {
49+
if(prices == null || prices.length == 0) return 0;
50+
int len = prices.length;
51+
int[] s0 = new int[len + 1];
52+
int[] s1 = new int[len + 1];
53+
int[] s2 = new int[len + 1];
54+
s1[1] = -prices[0];
55+
for(int i = 2; i <= prices.length; i++){
56+
s0[i] = Math.max(s0[i - 1], s2[i - 1]);
57+
s1[i] = Math.max(s1[i - 1], s0[i - 1] - prices[i - 1]);
58+
s2[i] = s1[i - 1] + prices[i - 1];
59+
}
60+
return Math.max(s0[len], s2[len]);
61+
}
62+
}
63+
```
64+
65+
### Reference
66+
1. [【LeetCode】309. Best Time to Buy and Sell Stock with Cooldown](https://www.cnblogs.com/jdneo/p/5228004.html)

0 commit comments

Comments
 (0)