Skip to content

Commit 0afc141

Browse files
dunwudunwu
committed
update codes
1 parent 94a260c commit 0afc141

File tree

9 files changed

+798
-0
lines changed

9 files changed

+798
-0
lines changed

‎assets/算法.xmind‎

4.86 KB
Binary file not shown.

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/三角形最小路径和.java‎

Lines changed: 101 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,101 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
import java.util.ArrayList;
6+
import java.util.Arrays;
7+
import java.util.Collections;
8+
import java.util.List;
9+
10+
/**
11+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
12+
* @see <a href="https://leetcode-cn.com/problems/triangle/">120. 三角形最小路径和</a>
13+
* @since 2020-07-04
14+
*/
15+
public class 三角形最小路径和 {
16+
17+
public static void main(String[] args) {
18+
List<List<Integer>> triangle = new ArrayList<>();
19+
triangle.add(Collections.singletonList(2));
20+
triangle.add(Arrays.asList(3, 4));
21+
triangle.add(Arrays.asList(6, 5, 7));
22+
triangle.add(Arrays.asList(4, 1, 8, 3));
23+
System.out.println("args = " + minimumTotal(triangle));
24+
Assertions.assertEquals(11, minimumTotal(triangle));
25+
Assertions.assertEquals(11, minimumTotal2(triangle));
26+
Assertions.assertEquals(11, minimumTotal3(triangle));
27+
Assertions.assertEquals(11, minimumTotal4(triangle));
28+
}
29+
30+
// 回溯法，自上而下
31+
// 时间复杂度：O(2^(M*N))
32+
public static int minimumTotal(List<List<Integer>> triangle) {
33+
return backtrack(triangle, triangle.size(), 0, 0);
34+
}
35+
36+
private static int backtrack(List<List<Integer>> triangle, int row, int x, int y) {
37+
if (x == row - 1) return triangle.get(x).get(y);
38+
int left = backtrack(triangle, row, x + 1, y);
39+
int right = backtrack(triangle, row, x + 1, y + 1);
40+
return triangle.get(x).get(y) + Math.min(left, right);
41+
}
42+
43+
// 回溯法 + 剪枝，自上而下
44+
// 针对 minimumTotal 加入记忆缓存 memory 存储计算结果，避免递归中的重复计算
45+
// 时间复杂度：< O(2^(M*N))
46+
// 空间复杂度：O(M*M)
47+
public static int minimumTotal2(List<List<Integer>> triangle) {
48+
int level = triangle.size();
49+
int[][] memory = new int[level][level]; // 存储每个节点能得到的最优解
50+
return backtrack2(triangle, memory, triangle.size(), 0, 0);
51+
}
52+
53+
private static int backtrack2(List<List<Integer>> triangle, int[][] memory, int row, int x, int y) {
54+
if (memory[x][y] != 0) { return memory[x][y]; }
55+
if (x == row - 1) return memory[x][y] = triangle.get(x).get(y);
56+
int left = backtrack2(triangle, memory, row, x + 1, y);
57+
int right = backtrack2(triangle, memory, row, x + 1, y + 1);
58+
memory[x][y] = triangle.get(x).get(y) + Math.min(left, right);
59+
return memory[x][y];
60+
}
61+
62+
// 动态规划，自下而上
63+
// 时间复杂度：O(M^2)
64+
// 空间复杂度：O(M^2)
65+
public static int minimumTotal3(List<List<Integer>> triangle) {
66+
// 判空
67+
if (triangle == null || triangle.size() == 0) return 0;
68+
int level = triangle.size();
69+
// 横竖维度都加1，可以不用考虑最后一行的初始化
70+
// 由于是三角形二维数组，可视为横竖维度都是行数
71+
int[][] memory = new int[level + 1][level + 1];
72+
for (int i = level - 1; i >= 0; i--) {
73+
for (int j = 0; j < triangle.get(i).size(); j++) {
74+
if (memory[i][j] == 0) {
75+
memory[i][j] = Math.min(memory[i + 1][j], memory[i + 1][j + 1]) + triangle.get(i).get(j);
76+
}
77+
}
78+
}
79+
return memory[0][0];
80+
}
81+
82+
// 动态规划，自下而上 + 空间优化
83+
// 时间复杂度：O(M^2)
84+
// 空间复杂度：O(M^2)
85+
public static int minimumTotal4(List<List<Integer>> triangle) {
86+
// 判空
87+
if (triangle == null || triangle.size() == 0) return 0;
88+
int level = triangle.size();
89+
// 横竖维度都加1，可以不用考虑最后一行的初始化
90+
// 由于是三角形二维数组，可视为横竖维度都是行数
91+
int[] memory = new int[level + 1];
92+
for (int i = level - 1; i >= 0; i--) {
93+
List<Integer> rows = triangle.get(i);
94+
for (int j = 0; j < rows.size(); j++) {
95+
memory[j] = Math.min(memory[j], memory[j + 1]) + rows.get(j);
96+
}
97+
}
98+
return memory[0];
99+
}
100+
101+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/乘积最大子数组.java‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @since 2020-07-05
8+
*/
9+
public class 乘积最大子数组 {
10+
11+
public static void main(String[] args) {
12+
int[] nums = { 2, 3, -2, 4 };
13+
int[] nums2 = { -2, 0, -1 };
14+
// Assertions.assertEquals(6, maxProduct(nums));
15+
Assertions.assertEquals(6, maxProduct2(nums));
16+
Assertions.assertEquals(0, maxProduct2(nums2));
17+
}
18+
19+
public static int maxProduct(int[] nums) {
20+
return backtrack(nums, 0, 0, 1, 0);
21+
}
22+
23+
// 递归 + 回溯 暴力破解
24+
// 时间复杂度 O(2^N)
25+
public static int backtrack(int[] nums, int begin, int end, int res, int max) {
26+
if (end >= nums.length || begin > end) return max;
27+
res *= nums[end];
28+
if (res > max) {
29+
return backtrack(nums, begin, end + 1, res, res);
30+
} else {
31+
return backtrack(nums, end + 1, end + 1, 1, max);
32+
}
33+
}
34+
35+
public static int maxProduct2(int[] nums) {
36+
int min = nums[0];
37+
int max = nums[0];
38+
int res = nums[0];
39+
for (int i = 1; i < nums.length; i++) {
40+
int currMax = Math.max(Math.max(nums[i] * max, nums[i] * min), nums[i]);
41+
int currMin = Math.min(Math.min(nums[i] * max, nums[i] * min), nums[i]);
42+
res = Math.max(currMax, res);
43+
max = currMax;
44+
min = currMin;
45+
}
46+
return res;
47+
}
48+
49+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/买卖股票的最佳时机.java‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/">121. 买卖股票的最佳时机</a>
8+
* @since 2020-07-05
9+
*/
10+
public class 买卖股票的最佳时机 {
11+
12+
public static void main(String[] args) {
13+
int[] prices = { 7, 1, 5, 3, 6, 4 };
14+
int[] prices2 = { 7, 6, 4, 3, 1 };
15+
Assertions.assertEquals(5, maxProfit(prices));
16+
Assertions.assertEquals(0, maxProfit(prices2));
17+
}
18+
19+
public static int maxProfit(int[] prices) {
20+
if (prices == null || prices.length == 0) return 0;
21+
int n = prices.length;
22+
int max = 0;
23+
24+
// 定义二维数组
25+
// 一维表示第 i 天
26+
// 二维表示交易状态：0 表示没有买卖；1 表示买入；2 表示卖出
27+
int[][] mp = new int[n][3];
28+
mp[0][0] = 0; // 无
29+
mp[0][1] = -prices[0]; // 买
30+
mp[0][2] = 0; // 当天买进卖出，净赚0
31+
for (int i = 1; i < n; i++) {
32+
mp[i][0] = mp[i - 1][0]; // 一直不买
33+
mp[i][1] = Math.max(mp[i - 1][1], mp[i - 1][0] - prices[i]); // 昨天买或今天买
34+
mp[i][2] = mp[i - 1][1] + prices[i]; // 昨天还有股，今天卖出
35+
for (int j = 0; j <= 2; j++) {
36+
if (max < mp[i][j]) {
37+
max = mp[i][j];
38+
}
39+
}
40+
}
41+
return max;
42+
}
43+
44+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/买卖股票的最佳时机II.java‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/">122. 买卖股票的最佳时机 II</a>
8+
* @since 2020-07-05
9+
*/
10+
public class 买卖股票的最佳时机II {
11+
12+
public static void main(String[] args) {
13+
int[] prices = { 7, 1, 5, 3, 6, 4 };
14+
int[] prices2 = { 1, 2, 3, 4, 5 };
15+
Assertions.assertEquals(7, maxProfit(prices));
16+
Assertions.assertEquals(4, maxProfit(prices2));
17+
}
18+
19+
public static int maxProfit(int[] prices) {
20+
if (prices == null || prices.length == 0) return 0;
21+
int max = 0;
22+
int n = prices.length;
23+
int[][] dp = new int[n][2];
24+
dp[0][0] = 0;
25+
dp[0][1] = -prices[0];
26+
for (int i = 1; i < n; i++) {
27+
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
28+
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
29+
max = Math.max(dp[i][0], dp[i][1]);
30+
}
31+
return max;
32+
}
33+
34+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/买卖股票的最佳时机III.java‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/">123. 买卖股票的最佳时机 III</a>
8+
* @since 2020-07-05
9+
*/
10+
public class 买卖股票的最佳时机III {
11+
12+
public static void main(String[] args) {
13+
int[] prices = { 3, 3, 5, 0, 0, 3, 1, 4 };
14+
int[] prices2 = { 1, 2, 3, 4, 5 };
15+
Assertions.assertEquals(6, maxProfit(prices));
16+
Assertions.assertEquals(4, maxProfit(prices2));
17+
}
18+
19+
public static int maxProfit(int[] prices) {
20+
if (prices == null || prices.length == 0) return 0;
21+
final int days = prices.length;
22+
final int deal = 2; // 交易笔数
23+
24+
// 定义二维数组
25+
// 一维表示第 i 天
26+
// 二维表示交易笔数，最多 2 笔
27+
// 三维表示是否持有股票：0/1（持有）
28+
int[][][] dp = new int[days][deal + 1][2];
29+
30+
// 第一天数据初始化
31+
for (int k = 0; k <= deal; k++) {
32+
dp[0][k][0] = 0;
33+
dp[0][k][1] = -prices[0];
34+
}
35+
36+
for (int i = 1; i < days; i++) { // 扫描天数
37+
for (int k = deal; k >= 1; k--) {
38+
dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + prices[i]);
39+
dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - prices[i]);
40+
}
41+
}
42+
43+
return dp[days - 1][deal][0];
44+
}
45+
46+
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dynamic/爬楼梯.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package io.github.dunwu.algorithm.dynamic;
2+
3+
import org.junit.jupiter.api.Assertions;
4+
5+
/**
6+
* @author <a href="mailto:forbreak@163.com">Zhang Peng</a>
7+
* @see <a href="https://leetcode-cn.com/problems/climbing-stairs/submissions/">79. 单词搜索</a>
8+
* @since 2020-07-04
9+
*/
10+
public class 爬楼梯 {
11+
12+
public static void main(String[] args) {
13+
Assertions.assertEquals(1, climbStairs(0));
14+
Assertions.assertEquals(1, climbStairs(1));
15+
Assertions.assertEquals(2, climbStairs(2));
16+
Assertions.assertEquals(3, climbStairs(3));
17+
18+
Assertions.assertEquals(1, climbStairs2(0));
19+
Assertions.assertEquals(1, climbStairs2(1));
20+
Assertions.assertEquals(2, climbStairs2(2));
21+
Assertions.assertEquals(3, climbStairs2(3));
22+
23+
Assertions.assertEquals(1, climbStairs3(0));
24+
Assertions.assertEquals(1, climbStairs3(1));
25+
Assertions.assertEquals(2, climbStairs3(2));
26+
Assertions.assertEquals(3, climbStairs3(3));
27+
}
28+
29+
// 使用递归（回溯方式）
30+
// 时间复杂度：O(2^N)
31+
public static int climbStairs(int n) {
32+
return (n <= 1) ? 1 : climbStairs(n - 1) + climbStairs(n - 2);
33+
}
34+
35+
// 使用动态规划
36+
// 时间复杂度：O(N)
37+
// 空间复杂度：O(N)
38+
public static int climbStairs2(int n) {
39+
if (n <= 1) return 1;
40+
int[] mem = new int[n + 1];
41+
mem[0] = 1;
42+
mem[1] = 1;
43+
for (int i = 2; i < n + 1; i++) {
44+
mem[i] = mem[i - 1] + mem[i - 2];
45+
}
46+
return mem[n];
47+
}
48+
// 优化 climbStairs2 动态规划方案
49+
// 时间复杂度：O(N)
50+
// 空间复杂度：O(3)
51+
public static int climbStairs3(int n) {
52+
if (n <= 1) return 1;
53+
int res = 0;
54+
int prevStep1 = 1;
55+
int prevStep2 = 1;
56+
for (int i = 2; i < n + 1; i++) {
57+
res = prevStep1 + prevStep2;
58+
prevStep2 = prevStep1;
59+
prevStep1 = res;
60+
}
61+
return res;
62+
}
63+
}

0 commit comments

Comments
 (0)