北镇网站建设,室内设计网站有哪些知乎,wordpress福利,彩妆做推广的网站题目#xff1a;Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1].
思路#xff1a;要找到两个数组中重复数据最长的子数组的长度。暴力枚举#xff1a;每个A的下标i#xff0c;分别与B的每个下…题目Input: A: [1,2,3,2,1] B: [3,2,1,4,7] Output: 3 Explanation: The repeated subarray with maximum length is [3, 2, 1].
思路要找到两个数组中重复数据最长的子数组的长度。暴力枚举每个A的下标i分别与B的每个下标j作为起点判断最长的重复数组长度。就像是移动两个指针。 例如i0j分别为0,1,23,4的时候重复数组的长度分别为0,0,1,0,0。 当i2j0的时候重复数组的长度是3。接着还要计算i2,j1。如此一直计算到最后。这里的一个问题是当计算i2,j0找数组找到i4,j2结束之后还有必要查找i2j1位起始节点的子数组吗有必要在连续重复的数组中。例如数组A[X,X,0,0,0,1]数组B[0,0,0,0,1]可以看到以i2j0,为起点重复数组长度为3,以i2j1位起点重复数组长度为4。所以这个暴力枚举没有可以省略操作的地方。 时间复杂度A中每个元素都要和B中每个元素比较一次O(m*n) public int findLength(int[] A, int[] B) {int len1 A.length;int len2 B.length;int maxLen 0;for(int i0;ilen1;i){int j 0;while(jlen2){if(A[i] B[j]){int count 0;int idxA i;int idxB j;while(idxAlen1 idxB len2 A[idxA] B[idxB]) count;maxLen Math.max(maxLen,count);}j;}}return maxLen;}
学习动态规划。上面分析是以数组的起点开始思考动态规划以i,j作为子数组的终点元素考虑从(0,0)到(i,j)中重复数组的最长长度。 分析递归方程式。还以题目中的A、B数组为例。假设i3j1A[3]B[1]那么dp[3][1] dp[2][0]1。假设i3,j4,A[3]≠B[4]A[3]≠B[4]A[3] \ne B[4]那么dp[3][4]dp[2][3]。得出dp[i][j] dp[i-1][j-1]1 如果A[i]B[j]。这里之所以dp[i][j]与dp[i-1][j-1]有关系而不是跟dp[i][j-1]或者dp[i-1][j]有关系是因为这是求重复数组的长度。而求重复数组肯定是两个数组的下标同时移动。 分析初始化条件。如果i0如果A[i]B[j]则dp[0][j]1否则为0。如果j0如果A[i]B[j]则dp[i][0]1否则为0。 public int findLengthV2(int[] A, int[] B) {if (A null || B null)return 0;int m A.length;int n B.length;int[][] dp new int[m][n];int maxLen 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (j 0 || i 0) {dp[i][j] (A[i] B[j] ? 1 : 0);} else if (A[i] B[j]) {dp[i][j] 1 dp[i - 1][j - 1];maxLen Math.max(maxLen, dp[i][j]);}}}return maxLen;}
思考让我不能理解的地方是都是两层for循环时间复杂度都是O(m*n)。方法二就比方法一快。相比较之下方式一多出了
while(idxAlen1 idxB len2 A[idxA] B[idxB]) count;
这个步骤。方法二中只是简单的加法操作当然更快。这样说来方法一的时间复杂度就不是O(m*n)。当数组中重复元素多的情况下两者速度相差就更大了。例如以下数组 [59,59,59,93,59,59,59,59,59,59,59,59,59,59,59,59…] [59,59,59,91,59,59,59,59,59,59,59,59,59,59,59,59..] 还有让我感觉神奇的地方是如果以(i,j)为子数组起点考虑问题解决方法时间长而以(i,j)为子数组终点考虑问题竟然速度就快多了。这就是换个思路再看看下面这段代码。
public int findLength(int[] a, int[] b) {int m a.length, n b.length;if (m 0 || n 0) return 0;int[][] dp new int[m 1][n 1];int max 0;for (int i m - 1; i 0; i--)for (int j n - 1; j 0; j--)max Math.max(max, dp[i][j] a[i] b[j] ? 1 dp[i 1][j 1] : 0);return max; }
这个思路是以(i,j)作为子数组的开始节点dp[i][j]存储以(i,j)为子数组起始节点的重复数组最长长度。这时候从最大的下标开始考虑。为什么从最大下标开始考虑看下面的分析。 数组A: [1,2,3,2,1] B: [3,2,1,4,7] 例如i4,j4,因为A[4]不等于B[4]所以dp[4][4]0。 例如i3j1则dp[3][1]dp[4][2]1应该是在以j4j2这个数组重复数组最长长度1因为A[3]B[1]。dp[3][1] 与dp[2][0]的关系就不是很确定。我可能因为向后移动了位置重复数组变长也可能变短。 开辟空间dp[m1][n1] 而不是dp[m][n]是为了编码方便。 所以暴力枚举与动态规划是两种思考问题的方式。动态规划在找递推关系的时候不是一定要有dp[i][j]与dp[i-1][j-1]也可能是dp[i1][j1]。根据题目的确定性关系确定递推式。
参考资料 网页1 网页2
