最长重复子数组分析

访客 阅读:138 2020-10-21 17:06:16 评论:0

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

 

示例:

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

提示:

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

 

解:这道题一开始用动态规划做得,和最长公共子字符串一样的方法。还有种方法是用滑动窗口,好处是空间复杂度只有O(1)

A和B两个字符串,先对其,然后计算公共字符串;然后A往后挪一位,继续计算。。

同理,A计算完后B也要往后挪分别计算

class Solution { 
public: 
    int maxLength(vector<int>& A, vector<int>& B, int addA, int addB, int len) { 
        int ret = 0, k = 0; 
        for (int i = 0; i < len; i++) { 
            if (A[addA + i] == B[addB + i]) { 
                k++; 
            } else { 
                k = 0; 
            } 
            ret = max(ret, k); 
        } 
        return ret; 
    } 
    int findLength(vector<int>& A, vector<int>& B) { 
        int n = A.size(), m = B.size(); 
        int ret = 0; 
        for (int i = 0; i < n; i++) { 
            int len = min(m, n - i); 
            int maxlen = maxLength(A, B, i, 0, len); 
            ret = max(ret, maxlen); 
        } 
        for (int i = 0; i < m; i++) { 
            int len = min(n, m - i); 
            int maxlen = maxLength(A, B, 0, i, len); 
            ret = max(ret, maxlen); 
        } 
        return ret; 
    } 
};

 

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

扫一扫关注我们,了解最新精彩内容