leetcode718. 最长重复子数组动态规划,滑动窗口

    技术2022-07-10  127

    文章目录

    题目:leetcode718. 最长重复子数组/动态规划基本思想1:动态规划基本思想2:滑动窗口基本思想3:暴力

    题目:leetcode718. 最长重复子数组/动态规划

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

    示例 1:

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

    说明:

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

    来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    基本思想1:动态规划

    dp[i][j]:以 A[i - 1]结束的子数组 和 B[j - 1]结束的子数组的最长匹配的个数,因为这里是子数组每个元素要连续(区别:子序列,子序列不连续)状态:两个数组中的每一个字符选择:是否包含当前元素状态转移方程:当前两个元素相等,dp[i][j] = 1 + dp[i - 1][j - 1];不相等:dp[i][j] = dp[i - 1][j - 1]

    说明:如果是最长子序列,dp数组的含义和状态转移方程均不一样

    dp[i][j]:A的前 i 个字符和B的前 j 个字符最长匹配的子序列状态转移方程: d p [ i ] [ j ] = m a x ( d p [ i − 1 ] [ j − 1 ] + ( A [ i − 1 ] = = B [ j − 1 ] ? 1 : 0 ) , d p [ i − 1 ] [ j ] , d p [ i ] [ j − 1 ] ) dp[i][j] = max(dp[i - 1][j - 1] + (A[i - 1] == B[j - 1] ? 1 : 0),dp[i - 1][j], dp[i][j - 1]) dp[i][j]=max(dp[i1][j1]+(A[i1]==B[j1]?1:0),dp[i1][j],dp[i][j1])

    时间复杂度:O(N * M)

    class Solution { public: int findLength(vector<int>& A, vector<int>& B) { //动态规划 vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0)); int res = 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; } res = max(res, dp[i][j]); //cout << dp[i][j] << " "; } //cout << endl; } return res; } };

    基本思想2:滑动窗口

    该思想是基于:最长子数组在两个数组中的位置不一定相同,于是可以采取根据两数组的不同对齐方式取找最长子数组 下述代码中分两步进行:

    首先是A不变,B的首元素依次和A中的某个元素对齐,求解最长的重复子数组,求解的过程中如果两个字符相等,递增变量;否则,将变量置为0,在这个过程中要不断更新结果数组然后是B不变,A的首元素依次和B中的某个元素对齐。接下来的过程是一样的

    时间复杂度:O((N +M)* min(N,M))

    class Solution { public: int findLength(vector<int>& A, vector<int>& B) { //滑动窗口 int res = 0, cur, k; for(int i = 0; i < A.size(); ++i){//以A为基准,滑动B cur = 0; k = i; for(int j = 0; j < B.size() && k < A.size(); ++j,++k){ if(A[k] == B[j]) ++cur; else cur = 0; res = max(res, cur); } } for(int i = 0; i < B.size(); ++i){//以B为基准,滑动A cur = 0; k = i; for(int j = 0; j < A.size() && k < B.size(); ++j, ++k){ if(B[k] == A[j]) ++cur; else cur = 0; res = max(res, cur); } } return res; } };

    基本思想3:暴力

    求数组A中从 i 开始和数组B中从 j 开始的最长重复子数组,时间复杂度为O(n3

    Processed: 0.010, SQL: 9