8000 1 · Ainevsia/Leetcode-Rust@89b582b · GitHub
[go: up one dir, main page]
Skip to content

Commit 89b582b

Browse files
AinevsiaAinevsia
committed
1
1 parent 0c480cb commit 89b582b

File tree

11 files changed

+243
-1
lines changed

11 files changed

+243
-1
lines changed

‎notes/src/SUMMARY.md

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -173,4 +173,13 @@
173173
- [1143.最长公共子序列](./day53/lc1143.md)
174174
- [1035.不相交的线](./day53/lc1035.md)
175175
- [53. 最大子序和](./day53/lc53.md)
176+
- [day 55](./day55.md)
177+
- [392.判断子序列](./day55/lc392.md)
178+
- [115.不同的子序列](./day55/lc115.md)
179+
- [day 56](./day56.md)
180+
- [583. 两个字符串的删除操作](./day55/lc583.md)
181+
- [72. 编辑距离](./day56/lc72.md)
182+
- [day 57](./day57.md)
183+
- [647. 回文子串](./day56/lc647.md)
184+
- [516.最长回文子序列](./day56/lc516.md)
176185
- [remains](./remains.md)

‎notes/src/day53.md

Lines changed: 25 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1 +1,25 @@
1-
1143.最长公共子序列
1+
第九章 动态规划part14
2+
● 1143.最长公共子序列
3+
● 1035.不相交的线
4+
● 53. 最大子序和 动态规划
5+
6+
详细布置
7+
8+
1143.最长公共子序列
9+
10+
体会一下本题和 718. 最长重复子数组 的区别
11+
视频讲解：https://www.bilibili.com/video/BV1ye4y1L7CQ
12+
https://programmercarl.com/1143.%E6%9C%80%E9%95%BF%E5%85%AC%E5%85%B1%E5%AD%90%E5%BA%8F%E5%88%97.html
13+
14+
1035.不相交的线
15+
16+
其实本题和 1143.最长公共子序列 是一模一样的，大家尝试自己做一做。
17+
视频讲解：https://www.bilibili.com/video/BV1h84y1x7MP
18+
https://programmercarl.com/1035.%E4%B8%8D%E7%9B%B8%E4%BA%A4%E7%9A%84%E7%BA%BF.html
19+
20+
53. 最大子序和
21+
22+
这道题我们用贪心做过，这次 再用dp来做一遍
23+
视频讲解：https://www.bilibili.com/video/BV19V4y1F7b5
24+
https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C%EF%BC%88%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%89.html
25+

‎notes/src/day55.md

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
# 第九章 动态规划part15
2+
3+
4+
详细布置
5+
6+
## 392.判断子序列
7+
8+
这道题目算是 编辑距离问题 的入门题目（毕竟这里只是涉及到减法），慢慢的，后面就要来解决真正的 编辑距离问题了
9+
10+
https://programmercarl.com/0392.%E5%88%A4%E6%96%AD%E5%AD%90%E5%BA%8F%E5%88%97.html
11+
12+
## 115.不同的子序列
13+
14+
但相对于刚讲过 392.判断子序列，本题 就有难度了 ，感受一下本题和 392.判断子序列 的区别。
15+
16+
https://programmercarl.com/0115.%E4%B8%8D%E5%90%8C%E7%9A%84%E5%AD%90%E5%BA%8F%E5%88%97.html
17+

‎notes/src/day55/lc115.md

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
# 115.不同的子序列
2+
3+
扇贝力扣
4+
5+
最后一个测试案例答案是-1
6+
7+
递推公式想不清楚啊 啊嗷嗷啊
8+
9+
```cpp
10+
class Solution {
11+
public:
12+
int numDistinct(string s, string t) {
13+
// dp[i][j] = s[0:i-1]的子序列中t[0:j-1]出现的次数
14+
vector<vector<unsigned long long>>dp(s.size()+1,vector<unsigned long long>(t.size()+1,0));
15+
dp[0][0]=1;
16+
// for(int i=1;i<t.size()+1;i++)dp[0][i]=1;
17+
for(int j=1;j<s.size()+1;j++)dp[j][0]=1;
18+
// dp[i][j]+=dp[i][j-1]
19+
// if(s[i-1]==t[j-1])dp[i][j]+=dp[i-1][j-1]
20+
for(int i=1;i<s.size()+1;i++)
21+
for(int j=1;j<t.size()+1;j++){
22+
if(s[i-1]==t[j-1])
23+
dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
24+
else
25+
dp[i][j]=dp[i-1][j];
26+
}
27+
return int(dp[s.size()][t.size()]);
28+
}
29+
};
30+
```

‎notes/src/day55/lc392.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# 392.判断子序列
2+
3+
抄了随想录
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
bool isSubsequence(string s, string t) {
9+
// dp[i][j] 表示以下标i-1为结尾的字符串s，
10+
// 和以下标j-1为结尾的字符串t，
11+
// 相同子序列的长度为dp[i][j]
12+
vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));
13+
for(int i=1;i<s.size()+1;i++){
14+
for(int j=i;j<t.size()+1;j++){
15+
if(s[i-1]==t[j-1])dp[i][j]=dp[i-1][j-1]+1;
16+
else dp[i][j]=dp[i][j-1];
17+
}
18+
}
19+
return dp[s.size()][t.size()]==s.size();
20+
}
21+
};
22+
```

‎notes/src/day55/lc583.md

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
# 583. 两个字符串的删除操作
2+
3+
自己做的喜喜
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
int minDistance(string s, string t) {
9+
// dp[i][j]：s[0:i-1] vs t[0:j-1]
10+
// 想要达到相等，所需要删除元素的最少次数
11+
vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));
12+
for(int j=1;j<t.size()+1;j++)dp[0][j]=j;
13+
for(int j=1;j<s.size()+1;j++)dp[j][0]=j;
14+
for(int i=1;i<s.size()+1;i++)
15+
for(int j=1;j<t.size()+1;j++)
16+
{
17+
if(s[i-1]==t[j-1]){
18+
dp[i][j]=dp[i-1][j-1];
19+
}else{
20+
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
21+
}
22+
}
23+
return dp[s.size()][t.size()];
24+
}
25+
};
26+
```

‎notes/src/day56.md

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
# 第九章 动态规划part16
2+
3+
4+
详细布置
5+
6+
## 583. 两个字符串的删除操作
7+
8+
本题和动态规划：115.不同的子序列 相比，其实就是两个字符串都可以删除了，情况虽说复杂一些，但整体思路是不变的。
9+
https://programmercarl.com/0583.%E4%B8%A4%E4%B8%AA%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C.html
10+
11+
## 72. 编辑距离
12+
13+
最终我们迎来了编辑距离这道题目，之前安排题目都是为了 编辑距离做铺垫。
14+
15+
https://programmercarl.com/0072.%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB.html
16+
17+
## 编辑距离总结篇
18+
做一个总结吧
19+
https://programmercarl.com/%E4%B8%BA%E4%BA%86%E7%BB%9D%E6%9D%80%E7%BC%96%E8%BE%91%E8%B7%9D%E7%A6%BB%EF%BC%8C%E5%8D%A1%E5%B0%94%E5%81%9A%E4%BA%86%E4%B8%89%E6%AD%A5%E9%93%BA%E5%9E%AB.html

‎notes/src/day56/lc516.md

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
# 516.最长回文子序列
2+
3+
```cpp
4+
class Solution {
5+
public:
6+
int longestPalindromeSubseq(string s) {
7+
// dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]
8+
vector<vector<int>>dp(s.size(),vector<int>(s.size(),0));
9+
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
10+
for (int i = s.size() - 1; i >= 0; i--) {
11+
for (int j = i + 1; j < s.size(); j++) {
12+
if (s[i] == s[j]) {
13+
dp[i][j] = dp[i + 1][j - 1] + 2;
14+
} else {
15+
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
16+
}
17+
}
18+
}
19+
return dp[0][s.size() - 1];
20+
}
21+
};
22+
```

‎notes/src/day56/lc647.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
# 647. 回文子串
2+
3+
抄了随想录
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
int countSubstrings(string s) {
9+
// 布尔类型的dp[i][j]：表示区间范围[i,j] （注意是左闭右闭）的子串是否是回文子串，如果是dp[i][j]为true，否则为false。
10+
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
11+
int result = 0;
12+
for (int i = s.size() - 1; i >= 0; i--) { // 注意遍历顺序
13+
for (int j = i; j < s.size(); j++) {
14+
if (s[i] == s[j]) {
15+
if (j - i <= 1) { // 情况一 和 情况二
16+
result++;
17+
dp[i][j] = true;
18+
} else if (dp[i + 1][j - 1]) { // 情况三
19+
result++;
20+
dp[i][j] = true;
21+
}
22+
}
23+
}
24+
}
25+
return result;
26+
}
27+
};
28+
```

‎notes/src/day56/lc72.md

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
# 72. 编辑距离
2+
3+
```cpp
4+
class Solution {
5+
public:
6+
int minDistance(string s, string t) {
7+
// s[0:i-1] vs t[0:j-1] 最近编辑距离为dp[i][j]
8+
vector<vector<int>>dp(s.size()+1,vector<int>(t.size()+1,0));
9+
for(int j=1;j<t.size()+1;j++)dp[0][j]=j;
10+
for(int j=1;j<s.size()+1;j++)dp[j][0]=j;
11+
12+
for(int i=1;i<s.size()+1;i++)
13+
for(int j=1;j<t.size()+1;j++)
14+
{
15+
if(s[i-1]==t[j-1]){
16+
dp[i][j]=dp[i-1][j-1];
17+
} else {
18+
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
19+
}
20+
}
21+
return dp[s.size()][t.size()];
22+
}
23+
};
24+
```

0 commit comments

Comments
 (0)
0