LeetCode 718. Maximum Length of Repeated Subarray
Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
Example 1:
Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3
Explanation: The repeated subarray with maximum length is [3,2,1].Example 2:
Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]
Output: 5method
dp[i][j]：以i-1结尾的nums1和以j-1结尾的nums2的最长连续公共子序列的长度
如果是表示成以i结尾的nums1和以j结尾的nums2的最长连续重复子序列，那nums1[0]==nums2[0]的时候，dp[0][0]要从dp[-1][-1]过来，这样就要特殊处理，比较麻烦
因此，如果nums1[i-1]==nums2[j-1]，dp[i][j]就可以在dp[i-1][j-1]的基础上加1，不相等连续就中断了，dp[i][j]=0，不用操作
if (nums1[i-1] == nums2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
记录dp[i][j]的最大值作为结果
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
int res = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
res = max(res, dp[i][j]);
}
}
return res;
}滚动数组优化
数据都是从左上方来的，所以遍历nums2的时候要从后往前，如果没有重复要置0，因为连续中断了
int findLength(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size(); // 只需要一行
vector<int> dp(n + 1, 0);
int res = 0;
for (int i = 1; i <= m; i++) {
for (int j = n; j > 0; j--) { // 注意从后往前
if (nums1[i - 1] == nums2[j - 1])
dp[j] = dp[j - 1] + 1;
else dp[j] = 0; // 没有连续就断了，所以置0
res = max(res, dp[j]);
}
}
return res;
}如果需要输出结果，就用dp数组来存储最长连续公共子序列，同样用滚动数组
string LCS(string str1, string str2) {
int m = str1.size(), n = str2.size();
string res = "";
vector<string> dp(n + 1);
for (int i = 1; i <= m; i++) {
for (int j = n; j > 0; j--) {
if (str1[i - 1] == str2[j - 1]) {
dp[j] = dp[j - 1] + str1[i - 1];
}
else dp[j] = ""; // 不连续了就置空
if (dp[j].size() > res.size()) {
res = dp[j];
}
}
}
return res;
}也可以记录最后一次maxLen时的end，代表着以end-1结尾的nums1与nums2的公共部分的结尾是nums[end-1]，而长度是maxLen，因为是连续的，直接倒推回去得到开头是maxLen-i
string LCS(string str1, string str2) {
int m = str1.size(), n = str2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
int maxLen = 0;
int end;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if (dp[i][j] > maxLen) {
maxLen = dp[i][j];
end = i;
}
}
}
return str1.substr(end - maxLen, maxLen);
}LeetCode 1143. Longest Common Subsequence
Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, "ace" is a subsequence of "abcde".
A common subsequence of two strings is a subsequence that is common to both strings.
Example 1:
Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The longest common subsequence is "ace" and its length is 3.Example 2:
Input: text1 = "abc", text2 = "abc"
Output: 3
Explanation: The longest common subsequence is "abc" and its length is 3.method
跟上一题类似，但不要求连续
dp[i][j]：从0到i-1的text1与从0到j-1的text2的最长公共子序列的长度
如果text1[i-1] == text2[j-1]，则dp[i][j] = dp[i-1][j-1]+1
如果不相同，则dp[i][j]取dp[i-1][j]和dp[i][j-1]的较大者
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1])
dp[i][j] = dp[i - 1][j - 1] + 1;
else
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}滚动数组优化
只需要两行
int longestCommonSubsequence(string text1, string text2) {
int m = text1.size(), n = text2.size();
vector<vector<int>> dp(2, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (text1[i - 1] == text2[j - 1]) {
dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + 1;
}
else dp[i % 2][j] = max(dp[i % 2][j - 1], dp[(i - 1) % 2][j]);
}
}
return dp[m % 2][n];
}如果要保存公共子序列的结果，可以用dp数组存储
string LCS(string s1, string s2) {
int m = s1.size(), n = s2.size();
vector<vector<string>> dp(2, vector<string>(n + 1, ""));
int maxLen = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1[i - 1] == s2[j - 1]) {
dp[i % 2][j] = dp[(i - 1) % 2][j - 1] + s1[i - 1];
// 增加公共的字符
}
else dp[i % 2][j] = dp[(i - 1) % 2][j].size() > dp[i % 2][j-1].size() ? dp[(i - 1) % 2][j] : dp[i % 2][j - 1];
// 选择较长的继承
}
}
return dp[m % 2][n] == "" ? "-1" : dp[m % 2][n];
}LeetCode 1035. Uncrossed Lines
You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines.
We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that:
nums1[i]==nums2[j], and- the line we draw does not intersect any other connecting (non-horizontal) line.
Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line).
Return the maximum number of connecting lines we can draw in this way.
Example 1:
Input: nums1 = [1,4,2], nums2 = [1,2,4]
Output: 2
Explanation: We can draw 2 uncrossed lines as in the diagram.
We cannot draw 3 uncrossed lines, because the line from nums1[1] = 4 to nums2[2] = 4 will intersect the line from nums1[2]=2 to nums2[1]=2.method
转化为求最长公共子序列问题
int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n];
}
