[leetcode] 718. Maximum Length of Repeated Subarray

网友投稿 961 2022-08-23

[leetcode] 718. Maximum Length of Repeated Subarray

[leetcode] 718. Maximum Length of Repeated Subarray

Description

Given two integer arrays A 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: 3Explanation: The repeated subarray with maximum length is [3, 2, 1].

Note:

1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100

分析

题目的意思是:找到两个数组中的两个共同子数组。

dp[i][j]表示数组A的前i个数字和数组B的前j个数字的最长子数组的长度,如果dp[i][j]不为0,则A中第i个数组和B中第j个数字必须相等,比对于这两个数组[1,2,2]和[3,1,2],我们的dp数组为:

3 1 21 0 1 02 0 0 22 0 0 1

我们注意观察,dp值不为0的地方,都是当A[i] == B[j]的地方,而且还要加上左上方的dp值,即dp[i-1][j-1],所以当前的dp[i][j]就等于dp[i-1][j-1] + 1,而一旦A[i] != B[j]时,直接赋值为0,不用多想,因为子数组是要连续的,一旦不匹配了,就不能再增加长度了。我们每次算出一个dp值,都要用来更新结果res,这样就能得到最长相同子数组的长度了.

代码

class Solution {public: int findLength(vector& A, vector& B) { int m=A.size(); int n=B.size(); vector> dp(m+1,vector(n+1,0)); int res=0; 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; } res=max(res,dp[i][j]); } } return res; }};

参考文献

​​[LeetCode] Maximum Length of Repeated Subarray 最长的重复子数组​​

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:[leetcode] 643. Maximum Average Subarray I
下一篇:ImportError: cannot import name ‘IterableDataset‘ from ‘torch.utils.data.dataset‘
相关文章

 发表评论

暂时没有评论,来抢沙发吧~