Skip to content

Commit 24518be

Browse files
linwtlinwt
committed
动态规划7道
1 parent 388c7af commit 24518be

File tree

8 files changed

+579
-0
lines changed

8 files changed

+579
-0
lines changed

‎leetcode_Java/DoneTitle.txt

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,13 +8,17 @@
88
17. 电话号码的字母组合
99
20. 有效的括号
1010
21. 合并两个有序链表
11+
22. 括号生成
1112
37. 解数独
1213
39. 组合总和
1314
40. 组合总和 II
1415
46. 全排列
1516
47. 全排列 II
17+
42. 接雨水
1618
51. N 皇后
1719
53. 最大子数组和
20+
55. 跳跃游戏
21+
62. 不同路径
1822
70. 爬楼梯
1923
77. 组合
2024
78. 子集
@@ -46,6 +50,7 @@
4650
300. 最长上升子序列
4751
303. 区域和检索 - 数组不可变
4852
304. 二维区域和检索 - 矩阵不可变
53+
322. 零钱兑换
4954
338. 比特位计数
5055
406. 根据身高重建队列
5156
437. 路径总和
@@ -54,6 +59,8 @@
5459
463. 岛屿的周长
5560
491. 递增子序列
5661
494. 目标和
62+
509. 斐波那契数
63+
518. 零钱兑换 II
5764
538. 把二叉搜索树转换为累加树
5865
543. 二叉树的直径
5966
560. 和为 K 的子数组

‎leetcode_Java/Solution0022.java

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
// 括号生成
2+
3+
4+
/*
5+
回溯：
6+
1、画图，满二叉树，每个节点的 左子节点是(，右子节点是)
7+
1、剪枝：左括号大于n，右括号大于左括号，这两种情况是非有效括号
8+
2、终止条件：字符串长度为2n，表示到达了叶子结点，满足条件，收集结果
9+
3、递归：每次加一个左括号或加一个右括号，然后进入下一层，并记录左括号或右括号的数量
10+
*/
11+
class Solution {
12+
private List<String> res = new ArrayList<>();
13+
14+
public List<String> generateParenthesis(int n) {
15+
dfs("", n, 0, 0);
16+
return res;
17+
}
18+
19+
private void dfs(String track, int n, int left, int right) {
20+
if (left > n || right > left) {
21+
return;
22+
}
23+
if (track.length() == 2 * n) {
24+
res.add(track);
25+
return;
26+
}
27+
dfs(track + "(", n, left + 1, right);
28+
dfs(track + ")", n, left, right + 1);
29+
}
30+
}
31+
32+
33+
/*
34+
动态规划：
35+
1、在求N个括号的排列组合时，把第N种情况（也就是N个括号排列组合）视为单独拿一个括号E出来，剩下的N-1个括号分为两部分，
36+
P个括号和Q个括号，P+Q=N-1，然后这两部分分别处于括号E内和括号E的右边，各自进行括号的排列组合。
37+
由于我们是一步步计算得到N个括号的情况的，所以小于等于N-1个括号的排列组合方式我们是已知的
38+
（用合适的数据结构存储，方便后续调用，且在存储时可利用特定数据结构实现题目某些要求，如排序，去重等），
39+
且P+Q=N-1，P和Q是小于等于N-1的，所以我们能直接得到P个和Q个括号的情况，进而得到N个括号的结果！
40+
2、dp[i]表示i组括号的所有有效组合
41+
3、dp[i] = "(" + dp[p]的组合 + ")" + dp[q]的组合"，其中1+p+q=i，p从0遍历到i-1，q则相应从i-1到0
42+
*/
43+
class Solution {
44+
public List<String> generateParenthesis(int n) {
45+
if (n == 0) {
46+
return new LinkedList<>();
47+
}
48+
LinkedList<LinkedList<String>> dp = new LinkedList<>();
49+
LinkedList<String> list1 = new LinkedList<>();
50+
list1.add("");
51+
dp.add(list1);
52+
LinkedList<String> list2 = new LinkedList<>();
53+
list2.add("()");
54+
dp.add(list2);
55+
for (int i = 2; i <= n; i++) {
56+
LinkedList<String> temp = new LinkedList<>();
57+
for (int j = 0; j < i; j++) {
58+
List<String> l1 = dp.get(j);
59+
List<String> l2 = dp.get(i - 1 - j);
60+
for (String s1 : l1) {
61+
for (String s2 : l2) {
62+
String s = "(" + s1 + ")" + s2;
63+
temp.add(s);
64+
}
65+
}
66+
}
67+
dp.add(temp);
68+
}
69+
return dp.get(n);
70+
}
71+
}

‎leetcode_Java/Solution0042.java

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,140 @@
1+
// 接雨水
2+
3+
4+
/*
5+
逐行累加雨水：
6+
1、start标志表示是否碰到柱子，碰到则开始计算，避免左侧没有柱子时错误计算
7+
2、tempSum表示两根柱子中间的雨水，遍历时碰到雨水就收集，碰柱子就将柱子间的雨水加入总和，清空当前柱子间的雨水，准备计算下一处柱子间的雨水
8+
3、要碰到柱子才将雨水加入总和，避免左边有柱子，右边没有柱子，这种情况没有雨水
9+
*/
10+
class Solution {
11+
public int trap(int[] height) {
12+
int max = Arrays.stream(height).max().getAsInt();
13+
int sum = 0;
14+
for (int i = 1; i <= max; i++) {
15+
boolean start = false;
16+
int tempSum = 0;
17+
for (int j = 0; j < height.length; j++) {
18+
if (start && height[j] < i) {
19+
tempSum++;
20+
}
21+
if (height[j] >= i) {
22+
sum += tempSum;
23+
tempSum = 0;
24+
start = true;
25+
}
26+
}
27+
}
28+
return sum;
29+
}
30+
}
31+
32+
33+
/*
34+
逐列累加雨水：
35+
1、遍历数组，首尾不用，因为首尾那一列左右柱子不足，不能接雨水
36+
2、遍历到某一位置时，求该位置 左边最高柱子的高度 和 右边最高柱子的高度，两个最高取较低者，较低者高于当前位置则可以接高度差的雨水，否则不能接雨水
37+
*/
38+
class Solution {
39+
public int trap(int[] height) {
40+
int n = height.length;
41+
int sum = 0;
42+
for (int i = 1; i < n - 1; i++) {
43+
int leftMax = getMax(height, 0, i - 1);
44+
int rightMax = getMax(height, i + 1, n - 1);
45+
int minVal = Math.min(leftMax, rightMax);
46+
sum += (minVal > height[i]) ? minVal - height[i] : 0;
47+
}
48+
return sum;
49+
}
50+
51+
private int getMax(int[] height, int start, int end) {
52+
int maxVal = 0;
53+
for (int i = start; i <= end; i++) {
54+
maxVal = Math.max(height[i], maxVal);
55+
}
56+
return maxVal;
57+
}
58+
}
59+
60+
61+
/*
62+
逐列累加雨水，动态规划，时间复杂度优化，空间换时间：
63+
1、为避免重复遍历计算某位置的左右最高柱子，使用dp数组存放最高柱子
64+
2、dpLeft[i]表示i位置左边最高柱子的高度，dpRight[i]表示i位置右边最高柱子的高度
65+
3、状态转移方程：
66+
dpLeft[i] = Math.max(dpLeft[i - 1], height[i - 1]);
67+
dpRight[i] = Math.max(dpRight[i + 1], height[i + 1]);
68+
4、遍历顺序：求 左边最高柱子的高度 则 从左往右 遍历，求 右边最高柱子的高度 则 从右往左 遍历
69+
*/
70+
class Solution {
71+
public int trap(int[] height) {
72+
int n = height.length;
73+
int sum = 0;
74+
int[] dpLeft = new int[n];
75+
int[] dpRight = new int[n];
76+
for (int i = 1; i < n - 1; i++) {
77+
dpLeft[i] = Math.max(dpLeft[i - 1], height[i - 1]);
78+
}
79+
for (int i = n - 2; i >= 0; i--) {
80+
dpRight[i] = Math.max(dpRight[i + 1], height[i + 1]);
81+
}
82+
for (int i = 1; i < n - 1; i++) {
83+
int minVal = Math.min(dpLeft[i], dpRight[i]);
84+
sum += (minVal > height[i]) ? minVal - height[i] : 0;
85+
}
86+
return sum;
87+
}
88+
}
89+
90+
91+
/*
92+
双指针
93+
*/
94+
class Solution {
95+
public int trap(int[] height) {
96+
int n = height.length;
97+
int sum = 0;
98+
int leftMax = 0, rightMax = 0;
99+
int left = 1, right = n - 2;
100+
for (int i = 1; i < n - 1; i++) {
101+
if (height[left - 1] < height[right + 1]) {
102+
leftMax = Math.max(leftMax, height[left - 1]);
103+
sum += (leftMax > height[left]) ? leftMax - height[left] : 0;
104+
left++;
105+
} else {
106+
rightMax = Math.max(rightMax, height[right + 1]);
107+
sum += (rightMax > height[right]) ? rightMax - height[right] : 0;
108+
right--;
109+
}
110+
}
111+
return sum;
112+
}
113+
}
114+
115+
116+
/*
117+
栈
118+
*/
119+
class Solution {
120+
public int trap(int[] height) {
121+
int sum = 0;
122+
int index = 0;
123+
Stack<Integer> stack = new Stack<>();
124+
while (index < height.length) {
125+
while (!stack.empty() && height[index] > height[stack.peek()]) {
126+
int outVal = height[stack.peek()];
127+
stack.pop();
128+
if (stack.empty()) {
129+
break;
130+
}
131+
int distance = index - stack.peek() - 1;
132+
int minVal = Math.min(height[stack.peek()], height[index]);
133+
sum += distance * (minVal - outVal);
134+
}
135+
stack.push(index);
136+
index++;
137+
}
138+
return sum;
139+
}
140+
}

‎leetcode_Java/Solution0055.java

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
// 跳跃游戏
2+
3+
4+
/*
5+
动态规划：
6+
1、dp[i]定义：表示在索引为 i 的位置能够跳跃到的最远距离
7+
2、状态转移方程：dp[i] = max(dp[i - 1], i + nums[i])
8+
3、在状态转移前后进行跳跃长度判断以快速得出结果，没希望跳过去、已经足够跳过去
9+
*/
10+
class Solution {
11+
public boolean canJump(int[] nums) {
12+
int n = nums.length;
13+
int[] dp = new int[n];
14+
dp[0] = nums[0];
15+
for (int i = 1; i < n; i++) {
16+
if (dp[i - 1] < i) {
17+
return false;
18+
}
19+
dp[i] = Math.max(dp[i - 1], i + nums[i]);
20+
if (dp[i] >= n - 1) {
21+
return true;
22+
}
23+
}
24+
return true;
25+
}
26+
}
27+
28+
29+
/*
30+
贪心/动态规划状态压缩：只用一个变量存储可以跳跃的最远距离，省略整个dp数组的空间
31+
1、如果某一个作为 起跳点 的格子可以跳跃的距离是 3，那么表示后面 3 个格子都可以作为 起跳点
32+
2、可以对每一个能作为 起跳点 的格子都尝试跳一次，把 能跳到最远的距离 不断更新
33+
3、如果可以一直跳到最后，就成功了
34+
*/
35+
class Solution {
36+
public boolean canJump(int[] nums) {
37+
int maxLen = 0;
38+
for (int i = 0; i < nums.length; i++) {
39+
if (maxLen < i) {
40+
return false;
41+
}
42+
maxLen = Math.max(maxLen, i + nums[i]);
43+
}
44+
return true;
45+
}
46+
}

‎leetcode_Java/Solution0062.java

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
// 不同路径
2+
3+
4+
/*
5+
动态规划二维dp：自底向上
6+
1、dp[i][j]表示到达位置(i,j)的不同路径条数
7+
2、初始化dp，首行首列只有一条路径，初始化为1
8+
3、状态转移方程：dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 即上方和左方的不同路径条数相加
9+
4、遍历每个位置，记录不同路径条数，直到终点，获得结果
10+
*/
11+
class Solution {
12+
public int uniquePaths(int m, int n) {
13+
int[][] dp = new int[m][n];
14+
for (int i = 0; i < m; i++) {
15+
dp[i][0] = 1;
16+
}
17+
for (int j = 0; j < n; j++) {
18+
dp[0][j] = 1;
19+
}
20+
for (int i = 1; i < m; i++) {
21+
for (int j = 1; j < n; j++) {
22+
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
23+
}
24+
}
25+
return dp[m - 1][n - 1];
26+
}
27+
}
28+
29+
30+
/*
31+
动态规划状态压缩：自底向上
32+
1、由于每次状态更新只用到上一行的记录，因此可以压缩成一维数组
33+
2、滚动数组：二维数组更新变成在一维数组上滚动更新
34+
3、dp[j-1]表示当前行刚更新的值（左方元素），dp[j]表示上一行的旧值（上方元素），相加后覆盖dp[j]表示上一行用过了不需要了
35+
*/
36+
class Solution {
37+
public int uniquePaths(int m, int n) {
38+
int[] dp = new int[n];
39+
Arrays.fill(dp, 1);
40+
for (int i = 1; i < m; i++) {
41+
for (int j = 1; j < n; j++) {
42+
dp[j] += dp[j - 1];
43+
}
44+
}
45+
return dp[n - 1];
46+
}
47+
}
48+
49+
50+
/*
51+
递归 + 备忘录：自顶向下
52+
1、定义二维数组作为备忘录，初始化为-1，记录递归过程已经计算路径的位置，防止重复递归计算
53+
2、从终点位置开始，递归计算路径条数
54+
2、定义递归函数
55+
1）递归函数含义：dfs(i,j)表示到达位置(i,j)的不同路径条数
56+
2）终止条件：碰到左边界或上边界就返回1，或者该位置备忘录有值则直接返回
57+
3）递归调用：(i,j)位置的不同路径条数由上方和左方的不同路径条数相加，计算完结果存入备忘录并返回结果
58+
*/
59+
class Solution {
60+
public int uniquePaths(int m, int n) {
61+
int[][] memo = new int[m][n];
62+
for (int i = 0; i < m; i++) {
63+
for (int j = 0; j < n; j++) {
64+
memo[i][j] = -1;
65+
}
66+
}
67+
return dfs(memo, m - 1, n - 1);
68+
}
69+
70+
private int dfs(int[][] memo, int i, int j) {
71+
if (i == 0 || j == 0) {
72+
return 1;
73+
}
74+
if (memo[i][j] != -1) {
75+
return memo[i][j];
76+
}
77+
memo[i][j] = dfs(memo, i - 1, j) + dfs(memo, i, j - 1);
78+
return memo[i][j];
79+
}
80+
}

0 commit comments

Comments
 (0)