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

Commit 0c480cb

Browse files
AinevsiaAinevsia
committed
1
1 parent cb02071 commit 0c480cb

File tree

5 files changed

+75
-0
lines changed

5 files changed

+75
-0
lines changed

‎notes/src/SUMMARY.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -169,4 +169,8 @@
169169
- [300.最长递增子序列](./day52/lc300.md)
170170
- [674. 最长连续递增序列](./day52/lc674.md)
171171
- [718. 最长重复子数组](./day52/lc718.md)
172+
- [day 53](./day53.md)
173+
- [1143.最长公共子序列](./day53/lc1143.md)
174+
- [1035.不相交的线](./day53/lc1035.md)
175+
- [53. 最大子序和](./day53/lc53.md)
172176
- [remains](./remains.md)

‎notes/src/day53.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
1143.最长公共子序列

‎notes/src/day53/lc1035.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# 1035.不相交的线
2+
3+
原来需要转化成‘最长公共子序列的长度’，一下子真不会
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
int maxUncrossedLines(vector<int>& v, vector<int>& w) {
9+
// dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
10+
vector<vector<int>>dp(v.size()+1, vector<int>(w.size()+1, 0));
11+
int result = 0;
12+
for (int i = 1; i <= v.size(); i++) {
13+
for (int j = 1; j <= w.size(); j++) {
14+
if (v[i - 1] == w[j - 1]) {
15+
dp[i][j] = dp[i - 1][j - 1] + 1;
16+
} else {
17+
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
18+
}
19+
if (dp[i][j] > result) result = dp[i][j];
20+
}
21+
}
22+
return result;
23+
}
24+
};
25+
```

‎notes/src/day53/lc1143.md

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
# 1143.最长公共子序列
2+
3+
抄了随想录
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
int longestCommonSubsequence(string v, string w) {
9+
// dp[i][j]：长度为[0, i - 1]的字符串text1与长度为[0, j - 1]的字符串text2的最长公共子序列为dp[i][j]
10+
vector<vector<int>>dp(v.size()+1, vector<int>(w.size()+1, 0));
11+
int result = 0;
12+
for (int i = 1; i <= v.size(); i++) {
13+
for (int j = 1; j <= w.size(); j++) {
14+
if (v[i - 1] == w[j - 1]) {
15+
dp[i][j] = dp[i - 1][j - 1] + 1;
16+
} else {
17+
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
18+
}
19+
if (dp[i][j] > result) result = dp[i][j];
20+
}
21+
}
22+
return result;
23+
}
24+
};
25+
```

‎notes/src/day53/lc53.md

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
# 53. 最大子序和
2+
3+
自己做的 喜喜
4+
5+
```cpp
6+
class Solution {
7+
public:
8+
int maxSubArray(vector<int>& v) {
9+
// dp[i] 以前i个数结尾的连续子数组最大和
10+
int res = v[0];
11+
vector<int>dp(v.size(),0);
12+
dp[0]=res;
13+
for(int i=1;i<v.size();i++){
14+
dp[i]=max(v[i],dp[i-1]+v[i]);
15+
res=max(res,dp[i]);
16+
}
17+
return res;
18+
}
19+
};
20+
```

0 commit comments

Comments
 (0)
0