Skip to content

Commit 1f6974a

Browse files
author
chenweijie
committed
编辑距离 和 股票系列
1 parent 802695a commit 1f6974a

File tree

16 files changed

+610
-51
lines changed

16 files changed

+610
-51
lines changed

‎src/main/java/com/chen/algorithm/study/test121/Solution0.java

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -11,16 +11,16 @@ public class Solution0 {
1111

1212
public int max(int[] prices) {
1313

14-
if(prices == null || prices.length==0){
14+
if (prices == null || prices.length == 0) {
1515
return 0;
1616
}
1717

18-
int min = prices[0], max=0;
19-
for(int i = 1 ; i < prices.length;i++){
20-
if(prices[i] < min){
18+
int min = prices[0], max = 0;
19+
for (int i = 1; i < prices.length; i++) {
20+
if (prices[i] < min) {
2121
min = prices[i];
2222
}
23-
max = Math.max(max,prices[i]-min);
23+
max = Math.max(max, prices[i] - min);
2424
}
2525

2626
return max;

‎src/main/java/com/chen/algorithm/study/test123/Solution.java

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package com.chen.algorithm.study.test123;
2+
3+
/**
4+
* https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/dong-tai-gui-hua-by-liweiwei1419-7/
5+
*
6+
* 参考test188
7+
*
8+
* @author : chen weijie
9+
* @Date: 2020-09-06 01:02
10+
*/
11+
public class Solution {
12+
13+
public int maxProfit(int[] prices) {
14+
15+
if (prices == null || prices.length == 0) {
16+
return 0;
17+
}
18+
19+
int len = prices.length;
20+
21+
// dp[i][j] ，表示 [0, i] 区间里，状态为 j 的最大收益
22+
// j = 0：什么都不操作
23+
// j = 1：第 1 次买入一支股票
24+
// j = 2：第 1 次卖出一支股票
25+
// j = 3：第 2 次买入一支股票
26+
// j = 4：第 2 次卖出一支股票
27+
28+
int[][] dp = new int[len][5];
29+
30+
dp[0][0] = 0;
31+
dp[0][1] = -prices[0];
32+
33+
// 3 状态都还没有发生，因此应该赋值为一个不可能的数
34+
for (int i = 0; i < len; i++) {
35+
dp[i][3] = Integer.MIN_VALUE;
36+
}
37+
38+
// 状态转移只有 2 种情况：
39+
// 情况 1：什么都不做
40+
// 情况 2：由上一个状态转移过来
41+
for (int i = 1; i < len; i++) {
42+
// j = 0 的值永远是 0
43+
dp[i][0] = 0;
44+
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
45+
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
46+
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
47+
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
48+
}
49+
50+
// 最大值只发生在不持股的时候，因此来源有 3 个：j = 0 ,j = 2, j = 4
51+
return Math.max(0, Math.max(dp[len - 1][2], dp[len - 1][4]));
52+
}
53+
54+
}

‎src/main/java/com/chen/algorithm/study/test152/Solution2.java

Lines changed: 0 additions & 31 deletions
This file was deleted.

‎src/main/java/com/chen/algorithm/study/test152/Solution3.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.chen.algorithm.study.test152;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2020-09-04 18:35
8+
*/
9+
public class Solution3 {
10+
11+
12+
// 5 3 -2 10
13+
14+
public int maxProduct(int[] nums) {
15+
return digui(nums.length - 1, 1, nums, nums[0], nums[0], nums[0]);
16+
}
17+
18+
19+
public int digui(int maxLevel, int currLevel, int[] nums, int currMax, int currMin, int max) {
20+
21+
if (maxLevel < currLevel) {
22+
return max;
23+
}
24+
if (nums[currLevel] > 0) {
25+
currMax = Math.max(currMax * nums[currLevel], nums[currLevel]);
26+
currMin = Math.min(currMin * nums[currLevel], nums[currLevel]);
27+
} else {
28+
currMax = Math.max(currMin * nums[currLevel], nums[currLevel]);
29+
currMin = Math.min(currMax * nums[currLevel], nums[currLevel]);
30+
}
31+
max = Math.max(max, currMax);
32+
33+
return digui(maxLevel, currLevel + 1, nums, currMax, currMin, max);
34+
}
35+
36+
@Test
37+
public void testCase() {
38+
39+
int[] nums = {5, 3, -2, 10};
40+
System.out.println(maxProduct(nums));
41+
}
42+
43+
44+
}

‎src/main/java/com/chen/algorithm/study/test152/Solution4.java

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package com.chen.algorithm.study.test152;
2+
3+
import org.junit.Test;
4+
5+
/**
6+
* @author : chen weijie
7+
* @Date: 2020-09-04 18:35
8+
*/
9+
public class Solution4 {
10+
11+
12+
// 5 3 -2 10
13+
14+
public int maxProduct(int[] nums) {
15+
16+
int[][] dp = new int[nums.length + 1][2];
17+
18+
dp[0][1] = nums[0];
19+
dp[0][0] = nums[0];
20+
int max = nums[0];
21+
for (int i = 1; i < nums.length; i++) {
22+
int currVal = nums[i];
23+
if (currVal > 0) {
24+
dp[i][0] = Math.max(dp[i - 1][0] * currVal, currVal);
25+
dp[i][1] = Math.min(dp[i - 1][1] * currVal, currVal);
26+
} else {
27+
dp[i][0] = Math.max(dp[i - 1][1] * currVal, currVal);
28+
dp[i][1] = Math.min(dp[i - 1][0] * currVal, currVal);
29+
}
30+
max = Math.max(dp[i][0], max);
31+
}
32+
return max;
33+
}
34+
35+
36+
@Test
37+
public void testCase() {
38+
39+
int[] nums = {5, 3, -2, 10};
40+
System.out.println(maxProduct(nums));
41+
}
42+
43+
44+
}

‎src/main/java/com/chen/algorithm/study/test188/Solution.java

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package com.chen.algorithm.study.test188;
2+
3+
/**
4+
* https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/solution/dong-tai-gui-hua-by-liweiwei1419-4/
5+
*
6+
* @author : chen weijie
7+
* @Date: 2020-09-06 01:37
8+
*/
9+
public class Solution {
10+
11+
12+
public int maxProfit(int k, int[] prices) {
13+
14+
int len = prices.length;
15+
// 特判
16+
if (k == 0 || len < 2) {
17+
return 0;
18+
}
19+
if (k >= len / 2) {
20+
return greedy(prices, len);
21+
}
22+
23+
// dp[i][j][K]：到下标为 i 的天数为止（从 0 开始），到下标为 j 的交易次数（从 0 开始）
24+
// 状态为 K 的最大利润，K = 0 表示不持股，K = 1 表示持股
25+
int[][][] dp = new int[len][k][2];
26+
27+
// 初始化：把持股的部分都设置为一个较大的负值
28+
for (int i = 0; i < len; i++) {
29+
for (int j = 0; j < k; j++) {
30+
dp[i][j][1] = Integer.MIN_VALUE;
31+
}
32+
}
33+
34+
35+
for (int i = 0; i < len; i++) {
36+
37+
for (int j = 0; j < k; j++) {
38+
if (i == 0) {
39+
dp[i][j][1] = -prices[0];
40+
dp[i][j][0] = 0;
41+
} else {
42+
if (j == 0) {
43+
dp[i][j][1] = Math.max(dp[i - 1][j][1], -prices[i]);
44+
} else {
45+
// 基本状态转移方程 1。
46+
//分类讨论的依据依然是：昨天是否持股。
47+
//
48+
//（1）昨天持股，今天还持股，说明没有发生新的交易，这两天在同一个交易区间里；
49+
//（2）昨天不持股，今天持股，说明开启了一次新的交易。
50+
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
51+
}
52+
// 基本状态转移方程 2
53+
54+
//分类讨论的依据是：昨天是否持股。
55+
//（1）昨天不持股，今天还不持股，说明没有发生新的交易；
56+
//（2）昨天持股，今天不持股，说明这次交易结束了。这两种情况都在一次交易里。
57+
58+
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
59+
}
60+
}
61+
}
62+
// 说明：i、j 状态都是前缀性质的，只需返回最后一个状态
63+
return dp[len - 1][k - 1][0];
64+
}
65+
66+
67+
private int greedy(int[] prices, int len) {
68+
// 转换为股票系列的第 2 题，使用贪心算法完成，思路是只要有利润，就交易
69+
int res = 0;
70+
for (int i = 1; i < len; i++) {
71+
if (prices[i - 1] < prices[i]) {
72+
res += prices[i] - prices[i - 1];
73+
}
74+
}
75+
return res;
76+
}
77+
78+
79+
}

‎src/main/java/com/chen/algorithm/study/test208/Trie.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package com.chen.algorithm.study.test208;
2+
3+
/**
4+
* @author : chen weijie
5+
* @Date: 2020-09-02 01:19
6+
*/
7+
public class Trie {
8+
9+
10+
11+
public TrieNode root;
12+
13+
/**
14+
* Initialize your data structure here.
15+
*/
16+
public Trie() {
17+
root = new TrieNode();
18+
root.val = ' ';
19+
}
20+
21+
22+
/**
23+
* Inserts a word into the trie.
24+
*/
25+
public void insert(String word) {
26+
TrieNode ws = root;
27+
for (int i = 0; i < word.length(); i++) {
28+
char c = word.charAt(i);
29+
if (ws.children[c - 'a'] == null) {
30+
ws.children[c - 'a'] = new TrieNode(c);
31+
}
32+
ws = ws.children[c - 'a'];
33+
}
34+
ws.isWorld = true;
35+
}
36+
37+
/**
38+
* Returns if the word is in the trie.
39+
*/
40+
public boolean search(String word) {
41+
42+
TrieNode ws = root;
43+
for (int i = 0; i < word.length(); i++) {
44+
char c = word.charAt(i);
45+
if (ws.children[c - 'a'] == null) {
46+
return false;
47+
}
48+
ws = ws.children[c - 'a'];
49+
}
50+
51+
return ws.isWorld;
52+
}
53+
54+
/**
55+
* Returns if there is any word in the trie that starts with the given prefix.
56+
*/
57+
public boolean startsWith(String prefix) {
58+
TrieNode ws = root;
59+
for (int i = 0; i < prefix.length(); i++) {
60+
char c = prefix.charAt(i);
61+
if (ws.children[c - 'a'] == null) {
62+
return false;
63+
}
64+
ws = ws.children[c - 'a'];
65+
}
66+
return true;
67+
}
68+
69+
70+
71+
class TrieNode {
72+
public char val;
73+
public boolean isWorld;
74+
public TrieNode[] children = new TrieNode[26];
75+
76+
public TrieNode() {
77+
}
78+
79+
TrieNode(char c) {
80+
TrieNode node = new TrieNode();
81+
node.val = c;
82+
}
83+
}
84+
85+
}

0 commit comments

Comments
 (0)