NC183. 最长公共子数组
描述
示例1
输入:
[1,2],[1,2]
输出:
2
说明:
最长的公共子数组是[1,2]示例2
输入:
[1,2,5,5,7,8],[2,5,7,8,5]
输出:
3
说明:
最长的公共子数组是[5,7,8]示例3
输入:
[1,2],[1,3,2]
输出:
1
说明:
最长的公共子数组是[1]C++ 解法, 执行用时: 4ms, 内存消耗: 392KB, 提交时间: 2022-06-06
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param B int整型vector
* @return int整型
*/
int longestCommonSubarry(vector<int>& A, vector<int>& B) {
// write code here
int ret = 0;
vector<int> dp(B.size(), 0);
for (int i = 0; i < A.size(); ++i)
{
int pre = 0;
for (int j = 0; j < dp.size(); ++j)
{
int temp = dp[j];
if (B[j] == A[i])
{
dp[j] = pre + 1;
ret = max(ret, dp[j]);
}
else
dp[j] = 0;
pre = temp;
}
}
return ret;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 412KB, 提交时间: 2022-05-07
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param B int整型vector
* @return int整型
*/
int longestCommonSubarry(vector<int>& A, vector<int>& B) {
// write code here
int Alen=A.size(),Blen=B.size();
int dp[Blen+1];
int ans=0;
memset(dp,0,sizeof(dp));
for(int i=1;i<=Alen;++i){
for(int j=Blen;j>=1;--j){
if(A[i-1]==B[j-1]) dp[j]=dp[j-1]+1;
else{
dp[j]=0;
}
ans=max(ans,dp[j]);
}
}
return ans;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 412KB, 提交时间: 2022-01-24
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param B int整型vector
* @return int整型
*/
int longestCommonSubarry(vector<int>& A, vector<int>& B) {
// write code here
int maxLen=0;
vector<int> dp(A.size()+1);
for(int i=0;i<B.size();i++){
for(int j=A.size();j>0;j--){
if(A[j-1]==B[i])
dp[j]=dp[j-1]+1;
else
dp[j]=0;
if(dp[j]>maxLen)
maxLen=dp[j];
}
}
return maxLen;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-02-03
//思路参考： NC165 最长公共子序列(一)
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param B int整型vector
* @return int整型
*/
int longestCommonSubarry(vector<int>& A, vector<int>& B)
{
int m = A.size();
int n = B.size();
//int len = min(m, n);
//vector<int> dp(n+1, 0);
int maxVal=0;
vector<int> dp(n + 1);
for(int i=1; i <=m; ++i)
{
int pre = dp[0];
for(int j=1; j <=n; ++j)
{
//dp[j]: 第i-1轮, 第j次循环的值，等价于dp[i-1][j]
//第i轮更新后，保存的值等价于：第i轮，第j次循环的值，即dp[i][j];
int temp = dp[j];
//pre等价于 dp[i-1][j-1],相对于当前循环j而言，是前一次循环保存的值dp[i-1][j-1]
if(A[i-1] == B[j-1])
dp[j] = pre + 1;
else
dp[j] = 0;
maxVal = max(maxVal, dp[j]);
////pre等价于 dp[i-1][j-1],留作++j后的下一循环使用
pre = temp;
}
}
return maxVal;
}
};
class Solution1 {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param A int整型vector
* @param B int整型vector
* @return int整型
*/
int longestCommonSubarry(vector<int>& A, vector<int>& B)
{
int m = A.size();
int n = B.size();
vector<int> vec(n+1,0);;
vector<vector<int>> dp(m+1, vec);
int maxVal = INT_MIN;
for(int i=1; i<=m; ++i)
{
for(int j=1; j<=n; ++j)
{
if(A[i-1]==B[j-1])
{
dp[i][j] = dp[i-1][j-1] + 1;
maxVal = max(maxVal, dp[i][j]);
}
else
dp[i][j] = 0;
}
}
return maxVal;
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 424KB, 提交时间: 2022-01-29
class Solution {
public:
/*
方法一：动态规划
本质是最长公共子串问题，设dp[i][j]表示以A[i]结尾和以B[j]结尾的最长公共子数组。
1. 如果A[i]=B[j]，说明可以在“以A[i-1]结尾和以B[j-1]结尾”的最长公共子数组的基础上增加一个长度，
因此状态转移方程为：dp[i][j] = dp[i-1][j-1] + 1；
2. 如果A[i]≠B[j]，说明在此处公共子数组断了，不存在以A[i]结尾和以B[j]结尾的公共子数组，dp[i][j]=0。
由于某个普遍位置的取值仅依赖于它左上角的值，因此填表的顺序为从上到下，从左往右。
复杂度分析
时间复杂度：O(nm)
空间复杂度：O(nm)
*/
int longestCommonSubarry1(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1));
int maxLen = 0;
for(int i = 1; i <= A.size(); i++) {
for(int j = 1; j <= B.size(); j++) {
if(A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
maxLen = max(maxLen, dp[i][j]);
}
}
return maxLen;
}
/*
动态规划解法优化
复杂度分析：O(nm)
空间复杂度：O(n)
*/
int longestCommonSubarry(vector<int>& A, vector<int>& B) {
int maxLen = 0;
vector<int> dp(A.size() + 1);
for(int i = 0; i < B.size(); i++){
for(int j = A.size(); j > 0; j--){
if(A[j - 1] == B[i])
dp[j] = dp[j - 1] + 1;
else
dp[j] = 0;
if(dp[j] > maxLen)
maxLen = dp[j];
}
}
return maxLen;
}
};