贵阳网站建开发,网站运营方案模板,哈尔滨今天新闻头条,wordpress分配管理员【问题描述】[中等]
给两个整数数组 A 和 B #xff0c;返回两个数组中公共的、长度最长的子数组的长度。示例 1:输入:
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…【问题描述】[中等]
给两个整数数组 A 和 B 返回两个数组中公共的、长度最长的子数组的长度。示例 1:输入:
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【解答思路】
1. 暴力法
时间复杂度O(N^3) 空间复杂度O(1)
public int findLength1(int[] numa, int[] numb) {if(numa null || numb null){return 0;}int max 0;int aLen numa.length, bLen numb.length;int aIndex, bIndex, sameLen;for(int i0; iaLen; i){for(int j0; jbLen; j){aIndex i;bIndex j;sameLen 0;while(aIndexaLen bIndexbLen numa[aIndex]numb[bIndex] ){sameLen;aIndex;bIndex;}if(max sameLen){max sameLen;}}}return max;}
2. 动态规划 第 1 步设计状态 int[][] dp 表示 A[i:] 和 B[j:] 的最长公共前缀 第 2 步状态转移方程 如果 A[i] B[j]那么 dp[i][j] dp[i 1][j 1] 1否则 dp[i][j] 0。 第 3 步考虑初始化 int[][] dp new int[n 1][m 1]; 第 4 步考虑输出 max 第 5 步考虑是否可以状态压缩 暂时不考虑
时间复杂度O(N×M) 空间复杂度O(N×M)
class Solution {public int findLength(int[] A, int[] B) {int n A.length, m B.length;int[][] dp new int[n 1][m 1];int ans 0;for (int i n - 1; i 0; i--) {for (int j m - 1; j 0; j--) {dp[i][j] A[i] B[j] ? dp[i 1][j 1] 1 : 0;ans Math.max(ans, dp[i][j]);}}return ans;}
} public int findLength(int[] A, int[] B) {int lenA A.length;int lenB B.length;int[][] dp new int[lenA][lenB];int max Integer.MIN_VALUE;for (int i 0; i lenA; i) {for (int j 0; j lenB; j) {if (A[i] B[j]){if (i 0 j 0){dp[i][j] dp[i - 1][j - 1] 1;}else{dp[i][j] 1;}}max Math.max(max,dp[i][j]);}}return max;}3. 滑动窗口 时间复杂度O((NM)×min(N,M)) 空间复杂度O(1)
class Solution {public int findLength(int[] A, int[] B) {int n A.length, m B.length;int ret 0;for (int i 0; i n; i) {int len Math.min(m, n - i);int maxlen maxLength(A, B, i, 0, len);ret Math.max(ret, maxlen);}for (int i 0; i m; i) {int len Math.min(n, m - i);int maxlen maxLength(A, B, 0, i, len);ret Math.max(ret, maxlen);}return ret;}public int maxLength(int[] A, 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 Math.max(ret, k);}return ret;}
}
【总结】
1. 暴力法 注意边界问题
2.动态规划 做到前四就不错啦
第 1 步设计状态 第 2 步状态转移方程 第 3 步考虑初始化 第 4 步考虑输出 第 5 步考虑是否可以状态压缩
3.滑动窗口 还可以是两个块之间对比使用 之前都是用双指针滑的
转载链接https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zui-chang-zhong-fu-zi-shu-zu-by-leetcode-solution/
