Keshawn_lu's Blog

Leetcode 718. 最长重复子数组

字数统计: 339阅读时长: 1 min
2020/07/01 Share

题目简介:

给两个整数数组 AB ,返回两个数组中公共的、长度最长的子数组的长度。

示例 1:

1
2
3
4
5
6
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。

说明:

  1. 1 <= len(A), len(B) <= 1000
  2. 0 <= A[i], B[i] < 100

思路:

使用动态规划的思想,d[i][j]代表以A[i]B[j]为结尾的公共最长子序列。

A[i] != B[j]时,dp[i][j] == 0

A[i] == B[j]时,dp[i][j] == dp[i - 1][j - 1] + 1,即之前的公共最长子序列 + 1。

最后返回dp[i][j]中的最大值即可。

tip:

  • 需初始化dp[0][j], dp[i][0]

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
public:
int findLength(vector<int>& A, vector<int>& B) {

vector<vector<int>> dp(A.size(), vector<int>(B.size(), 0));

int Max_len = 0;

for(int j = 0; j < B.size(); j++){

dp[0][j] = (A[0] == B[j]) ? 1 : 0; //初始化
Max_len = max(Max_len, dp[0][j]);
}

for(int i = 0; i < A.size(); i++){

dp[i][0] = (A[i] == B[0]) ? 1 : 0; //初始化
Max_len = max(Max_len, dp[i][0]);
}

for(int i = 1; i < A.size(); i++){

for(int j = 1; j < B.size(); j++){

if(A[i] == B[j]){

dp[i][j] = dp[i - 1][j - 1] + 1;
Max_len = max(Max_len, dp[i][j]);
}
else
dp[i][j] = 0;
}
}

return Max_len;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: