Skip to content

Commit 4e5bd23

Browse files
dunwudunwu
committed
feat: leetcode 刷题
1 parent 5fb7476 commit 4e5bd23

20 files changed

+531
-217
lines changed

‎README.md‎

Lines changed: 43 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@
1818
<img alt="build" class="no-zoom" src="https://img.shields.io/github/actions/workflow/status/dunwu/algorithm-tutorial/deploy.yml?style=for-the-badge">
1919
</a>
2020

21-
<a href="https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh">
21+
<a href="https://creativecommons.org/licensestyp/by-nc-sa/4.0/deed.zh">
2222
<img alt="code style" class="no-zoom" src="https://img.shields.io/github/license/dunwu/algorithm-tutorial?style=for-the-badge">
2323
</a>
2424

@@ -404,32 +404,59 @@
404404
| --------------------------------------------------------------------------------- | :--: | :----: |
405405
| [509. 斐波那契数](https://leetcode.cn/problems/fibonacci-number/) | 💚 | ✔️ |
406406
| [1137. 第 N 个泰波那契数](https://leetcode.cn/problems/n-th-tribonacci-number/) | 💚 | ✔️ |
407-
| [70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/) | 💚 | ❗ |
408-
| [746. 使用最小花费爬楼梯](https://leetcode.cn/problems/min-cost-climbing-stairs/) | 💚 | ❗ |
409-
| [198. 打家劫舍](https://leetcode.cn/problems/house-robber/) | 💛 | ❌ |
410-
| [740. 删除并获得点数](https://leetcode.cn/problems/delete-and-earn/) | 💛 | ❌ |
407+
| [70. 爬楼梯](https://leetcode.cn/problems/climbing-stairs/) | 💚 | ✔️ |
408+
| [746. 使用最小花费爬楼梯](https://leetcode.cn/problems/min-cost-climbing-stairs/) | 💚 | ✔️ |
409+
| [198. 打家劫舍](https://leetcode.cn/problems/house-robber/) | 💛 | ❗ |
410+
| [740. 删除并获得点数](https://leetcode.cn/problems/delete-and-earn/) | 💛 | ❗ |
411+
412+
#### 一维
413+
414+
| 题目 | 难度 | 掌握度 |
415+
| ------------------------------------------------------------------------------------------------ | :--: | :----: |
416+
| [2140. 解决智力问题](https://leetcode.cn/problems/solving-questions-with-brainpower/) | 💛 | |
417+
| [322. 零钱兑换](https://leetcode.cn/problems/coin-change/) | 💛 | |
418+
| [2466. 统计构造好字符串的方案数](https://leetcode.cn/problems/count-ways-to-build-good-strings/) | 💛 | |
419+
| [91. 解码方法](https://leetcode.cn/problems/decode-ways/) | 💛 | |
420+
| [983. 最低票价](https://leetcode.cn/problems/minimum-cost-for-tickets/) | 💛 | |
421+
| [790. 多米诺和托米诺平铺](https://leetcode.cn/problems/domino-and-tromino-tiling/) | 💛 | |
411422

412423
#### 矩阵
413424

414425
| 题目 | 难度 | 掌握度 |
415426
| ----------------------------------------------------------------------------- | :--: | :----: |
416-
| [62. 不同路径](https://leetcode.cn/problems/unique-paths/) | 💛 | ❌ |
417-
| [63. 不同路径 II](https://leetcode.cn/problems/unique-paths-ii/) | 💛 | ❌ |
427+
| [62. 不同路径](https://leetcode.cn/problems/unique-paths/) | 💛 | ❗ |
428+
| [63. 不同路径 II](https://leetcode.cn/problems/unique-paths-ii/) | 💛 | ❗ |
418429
| [64. 最小路径和](https://leetcode.cn/problems/minimum-path-sum/) | 💛 | ✔️ |
419-
| [120. 三角形最小路径和](https://leetcode.cn/problems/triangle/) | 💛 | ❌ |
420-
| [931. 下降路径最小和](https://leetcode.cn/problems/minimum-falling-path-sum/) | 💛 | ❌ |
421-
| [221. 最大正方形](https://leetcode.cn/problems/maximal-square/) | 💛 | ❌ |
430+
| [120. 三角形最小路径和](https://leetcode.cn/problems/triangle/) | 💛 | ❗ |
431+
| [931. 下降路径最小和](https://leetcode.cn/problems/minimum-falling-path-sum/) | 💛 | ❗ |
432+
| [221. 最大正方形](https://leetcode.cn/problems/maximal-square/) | 💛 | ❌ |
422433

423434
#### 字符串
424435

436+
| 题目 | 难度 | 掌握度 |
437+
| ------------------------------------------------------------------------------ | :--: | :----: |
438+
| [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) | | |
439+
| | | |
440+
| | | |
441+
| | | |
442+
| | | |
443+
| | | |
444+
445+
#### 最长递增/公共子序列
446+
425447
| 题目 | 难度 | 掌握度 |
426448
| ------------------------------------------------------------ | :--: | :----: |
427-
| [5. 最长回文子串](https://leetcode.cn/problems/longest-palindromic-substring/) | | |
428-
| | | |
429-
| | | |
430-
| | | |
431-
| | | |
432-
| | | |
449+
| [300. 最长递增子序列](https://leetcode.cn/problems/longest-increasing-subsequence/) | 💛 | ❌ |
450+
| [673. 最长递增子序列的个数](https://leetcode.cn/problems/number-of-longest-increasing-subsequence/) | 💛 | ❌ |
451+
| [646. 最长数对链](https://leetcode.cn/problems/maximum-length-of-pair-chain/) | 💛 | ✔️ |
452+
| [1218. 最长定差子序列](https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/) | 💛 | ❌ |
453+
| [1027. 最长等差数列](https://leetcode.cn/problems/longest-arithmetic-subsequence/) | 💛 | ❌ |
454+
| [1143. 最长公共子序列](https://leetcode.cn/problems/longest-common-subsequence/) | 💛 | ❗ |
455+
| [1035. 不相交的线](https://leetcode.cn/problems/uncrossed-lines/) | 💛 | ❌ |
456+
| [583. 两个字符串的删除操作](https://leetcode.cn/problems/delete-operation-for-two-strings/) | 💛 | ❌ |
457+
| [712. 两个字符串的最小ASCII删除和](https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/) | 💛 | ❌ |
458+
459+
#### 买卖股票的最佳时间/状态机
433460

434461
#### 其他
435462

@@ -440,9 +467,6 @@
440467
| [354. 俄罗斯套娃信封问题](https://leetcode.cn/problems/russian-doll-envelopes/) | ❤️ | |
441468
| [72. 编辑距离](https://leetcode.cn/problems/edit-distance/) | 💛 | ❌ |
442469
| [53. 最大子数组和](https://leetcode.cn/problems/maximum-subarray/) | 💛 | ❌ |
443-
| [712. 两个字符串的最小ASCII删除和](https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/) | 💛 | ❌ |
444-
| [583. 两个字符串的删除操作](https://leetcode.cn/problems/delete-operation-for-two-strings/) | 💛 | ❌ |
445-
| [1143. 最长公共子序列](https://leetcode.cn/problems/longest-common-subsequence/) | 💛 | ❌ |
446470
| [416. 分割等和子集](https://leetcode.cn/problems/partition-equal-subset-sum/) | | |
447471
| [518. 零钱兑换 II](https://leetcode.cn/problems/coin-change-ii/) | | |
448472

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dp/fib/使用最小花费爬楼梯.java‎

Lines changed: 31 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -14,22 +14,44 @@ public static void main(String[] args) {
1414
Solution s = new Solution();
1515
Assertions.assertEquals(15, s.minCostClimbingStairs(new int[] { 10, 15, 20 }));
1616
Assertions.assertEquals(6, s.minCostClimbingStairs(new int[] { 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 }));
17+
18+
Solution2 s2 = new Solution2();
19+
Assertions.assertEquals(15, s2.minCostClimbingStairs(new int[] { 10, 15, 20 }));
20+
Assertions.assertEquals(6, s2.minCostClimbingStairs(new int[] { 1, 100, 1, 1, 1, 100, 1, 1, 100, 1 }));
1721
}
1822

1923
static class Solution {
2024

2125
public int minCostClimbingStairs(int[] cost) {
22-
int n = cost.length;
23-
int dp_i_1 = 0, dp_i_2 = 0, dp_i = 0;
24-
for (int i = 2; i <= n; i++) {
25-
dp_i = Math.min(
26-
dp_i_1 + cost[i - 1],
27-
dp_i_2 + cost[i - 2]
26+
if (cost == null || cost.length == 0) { return 0; }
27+
int N = cost.length;
28+
int[] dp = new int[N + 1];
29+
dp[0] = dp[1] = 0;
30+
for (int i = 2; i <= N; i++) {
31+
dp[i] = Math.min(
32+
dp[i - 1] + cost[i - 1],
33+
dp[i - 2] + cost[i - 2]
34+
);
35+
}
36+
return dp[N];
37+
}
38+
39+
}
40+
41+
static class Solution2 {
42+
43+
public int minCostClimbingStairs(int[] cost) {
44+
if (cost == null || cost.length == 0) { return 0; }
45+
int pre1 = 0, pre2 = 0;
46+
for (int i = 2; i <= cost.length; i++) {
47+
int tmp = Math.min(
48+
pre1 + cost[i - 1],
49+
pre2 + cost[i - 2]
2850
);
29-
dp_i_2 = dp_i_1;
30-
dp_i_1 = dp_i;
51+
pre2 = pre1;
52+
pre1 = tmp;
3153
}
32-
return dp_i;
54+
return pre1;
3355
}
3456

3557
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dp/fib/删除并获得点数.java‎

Lines changed: 15 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,8 @@
22

33
import org.junit.jupiter.api.Assertions;
44

5+
import java.util.Arrays;
6+
57
/**
68
* <a href="https://leetcode.cn/problems/delete-and-earn/">740. 删除并获得点数</a>
79
*
@@ -24,26 +26,25 @@ public static void main(String[] args) {
2426
static class Solution {
2527

2628
public int deleteAndEarn(int[] nums) {
27-
int max = 0;
28-
for (int val : nums) {
29-
max = Math.max(max, val);
30-
}
31-
int[] sums = new int[max + 1];
32-
for (int val : nums) {
33-
sums[val] += val;
29+
int[] sums = new int[10001];
30+
for (int num : nums) {
31+
sums[num] += num;
3432
}
3533
return rob(sums);
3634
}
3735

3836
public int rob(int[] sums) {
39-
int N = sums.length;
40-
int first = sums[0], second = Math.max(sums[0], sums[1]);
41-
for (int i = 2; i < N; i++) {
42-
int temp = second;
43-
second = Math.max(second, first + sums[i]);
44-
first = temp;
37+
if (sums == null || sums.length == 0) { return 0; }
38+
if (sums.length == 1) { return sums[0]; }
39+
int pre1 = Math.max(sums[0], sums[1]), pre2 = sums[0];
40+
int max = 0;
41+
for (int i = 2; i < sums.length; i++) {
42+
int tmp = Math.max(pre1, pre2 + sums[i]);
43+
max = Math.max(max, tmp);
44+
pre2 = pre1;
45+
pre1 = tmp;
4546
}
46-
return second;
47+
return max;
4748
}
4849

4950
}

‎codes/algorithm/src/main/java/io/github/dunwu/algorithm/dp/fib/打家劫舍.java‎

Lines changed: 7 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -15,51 +15,21 @@ public static void main(String[] args) {
1515
Assertions.assertEquals(4, s.rob(new int[] { 1, 2, 3, 1 }));
1616
Assertions.assertEquals(12, s.rob(new int[] { 2, 7, 9, 3, 1 }));
1717
Assertions.assertEquals(1, s.rob(new int[] { 1, 1 }));
18-
19-
Solution2 s2 = new Solution2();
20-
Assertions.assertEquals(4, s2.rob(new int[] { 1, 2, 3, 1 }));
21-
Assertions.assertEquals(12, s2.rob(new int[] { 2, 7, 9, 3, 1 }));
22-
Assertions.assertEquals(1, s2.rob(new int[] { 1, 1 }));
2318
}
2419

2520
static class Solution {
2621

2722
public int rob(int[] nums) {
28-
29-
int N = nums.length;
30-
if (N <= 1) { return nums[0]; }
31-
32-
int[] dp = new int[N + 1];
33-
dp[0] = nums[0];
34-
dp[1] = Math.max(nums[0], nums[1]);
35-
for (int i = 2; i < N; i++) {
36-
dp[i] = Math.max(
37-
dp[i - 1],
38-
dp[i - 2] + nums[i]
39-
);
40-
}
41-
42-
return dp[N - 1];
43-
}
44-
45-
}
46-
47-
/**
48-
* 优化空间复杂度
49-
*/
50-
static class Solution2 {
51-
52-
public int rob(int[] nums) {
23+
if (nums == null || nums.length == 0) { return 0; }
24+
if (nums.length == 1) { return nums[0]; }
5325
int N = nums.length;
54-
if (N <= 1) { return nums[0]; }
55-
56-
int cur = Math.max(nums[0], nums[1]), pre = nums[0];
26+
int first = nums[0], second = Math.max(nums[0], nums[1]);
5727
for (int i = 2; i < N; i++) {
58-
int tmp = Math.max(cur, pre + nums[i]);
59-
pre = cur;
60-
cur = tmp;
28+
int tmp = Math.max(second, first + nums[i]);
29+
first = second;
30+
second = tmp;
6131
}
62-
return cur;
32+
return second;
6333
}
6434

6535
}

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

Lines changed: 7 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -42,28 +42,26 @@ public int climbStairs(int n) {
4242
// 爬上 n−1 阶楼梯的方法数量。因为再爬1阶就能到第n阶
4343
// 爬上 n−2 阶楼梯的方法数量，因为再爬2阶就能到第n阶
4444
public int dp(int n) {
45-
if (n == 0) return 1;
46-
if (n == 1) return 1;
45+
if (n == 0 || n == 1) return 1;
4746
if (memo[n] != -1) return memo[n];
4847
memo[n] = dp(n - 1) + dp(n - 2);
4948
return memo[n];
5049
}
5150

5251
}
5352

53+
// 空间复杂度 o(1)
5454
static class Solution2 {
5555

5656
public int climbStairs(int n) {
57-
5857
if (n == 0 || n == 1) return 1;
59-
60-
int[] dp = new int[n + 1];
61-
dp[0] = 1;
62-
dp[1] = 1;
58+
int pre1 = 1, pre2 = 1;
6359
for (int i = 2; i <= n; i++) {
64-
dp[i] = dp[i - 1] + dp[i - 2];
60+
int tmp = pre1 + pre2;
61+
pre2 = pre1;
62+
pre1 = tmp;
6563
}
66-
return dp[n];
64+
return pre1;
6765
}
6866

6967
}

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

Lines changed: 38 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -24,24 +24,53 @@ public static void main(String[] args) {
2424

2525
// 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
2626
// 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
27+
28+
// 示例 1：
29+
//
30+
// 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
31+
// 输出：11
32+
// 解释：如下面简图所示：
33+
// 2
34+
// 3 4
35+
// 6 5 7
36+
// 4 1 8 3
37+
// 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
38+
// 示例 2：
39+
//
40+
// 输入：triangle = [[-10]]
41+
// 输出：-10
2742
}
2843

2944
static class Solution {
3045

3146
public int minimumTotal(List<List<Integer>> triangle) {
47+
48+
// base case
49+
if (triangle == null || triangle.size() == 0) { return 0; }
50+
if (triangle.size() == 1) { return triangle.get(0).get(0); }
51+
52+
// 状态定义
3253
int n = triangle.size();
3354
int[][] dp = new int[n][n];
55+
56+
// 初始化
3457
dp[0][0] = triangle.get(0).get(0);
35-
for (int i = 1; i < n; ++i) {
36-
dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
37-
for (int j = 1; j < i; ++j) {
38-
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
58+
59+
// 状态转移
60+
int min = Integer.MAX_VALUE;
61+
for (int i = 1; i < n; i++) {
62+
for (int j = 0; j <= i; j++) {
63+
if (j == 0) {
64+
dp[i][j] = dp[i - 1][0] + triangle.get(i).get(0);
65+
} else if (j == i) {
66+
dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j);
67+
} else {
68+
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
69+
}
70+
if (i == n - 1) {
71+
min = Math.min(min, dp[i][j]);
72+
}
3973
}
40-
dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
41-
}
42-
int min = dp[n - 1][0];
43-
for (int i = 1; i < n; ++i) {
44-
min = Math.min(min, dp[n - 1][i]);
4574
}
4675
return min;
4776
}

0 commit comments

Comments
 (0)