题目原文
Given two integer arraysA
and
B
, return the maximum length of an subarray that appears in both arrays.Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].
Note:- 1 <= len(A), len(B) <= 1000
- 0 <= A[i], B[i] < 100
转自 : here
题意分析
给定两个长度不一定相等的整型数组,找出他们间相同子数组的最大长度。解法分析
此题采用动态规划方法,关键是找到最优子结构,首先我想到的是用bothLen[i][j]表示以A[i],B[j]结尾的数组的相同子数组的最长长度,但是这样做不能得到最优子结构,因此用bothLen[i][j]表示以A[i],B[j]结尾的相同子数组的长度,bothLen[i][j]=(A[i]==B[j])?bothLen[i-1][j-1]+1:0,C++代码如下:class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
vector<vector<int>> bothLen(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++){
bothLen[i][j]=(A[i-1]==B[j-1])?bothLen[i-1][j-1]+1:0;
maxLen=max(bothLen[i][j],maxLen);
}
}
return maxLen;
}
};
为了减少空间消耗,可以将二维vector转化为一维,但是j的遍历方向需要改变。
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {
vector<int> bothLen(B.size()+1,0);
int maxLen=0;
for(int i=1;i<=A.size();i++){
for(int j=B.size();j>0;j--){
bothLen[j]=(A[i-1]==B[j-1])?bothLen[j-1]+1:0;
maxLen=max(bothLen[j],maxLen);
}
}
return maxLen;
}
};
这里bothLen[j]表示了bothLen[j][i],bothLen[j-1]表示了bothLen[j-1][i-1],为了达到这个效果j需要从大往小变,以免覆盖i-1时的值。因此对于一维数组的递归式,如a[i]=a[i-1]+1,这种可以用一个变量表示,而a[i]=a[i-1]+a[i-2],可以用两个变量表示,二维如a[i][j]=a[i][j-1]可以用a[i]表示,而本题这种需要通过改变j的遍历方向减少所需空间。当然也可以将将二维a[i][j]变为a[2][j],第一维大小固定为2.
No comments:
Post a Comment