為什么80%的碼農都做不了架構師？>>> ??

問題：

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

Note:

1 <= len(A), len(B) <= 1000

0 <= A[i], B[i] < 100

解決：

① ?給定兩個數組A和B，返回兩個數組的最長重復子數組。

dp[i][j]表示數組A的前i個數字和數組B的前j個數字的最長重復子數組的長度，如果dp[i][j]不為0，則A中第i個數組和B中第j個數字必須相等。

以[1,2,2]和[3,1,2]為例，dp數組為：

?? 3 1 2
1 0 1 0
2 0 0 2
2 0 0 1

當A[i] == B[j]時，dp[i][j] = dp[i - 1][j - 1] + 1；

當A[i] != B[j]時，dp[i][j] = 0；

每次算出一個dp值，都要用來更新結果res，這樣就能得到最長相同子數組的長度了。

class Solution { //83ms
? ? public int findLength(int[] A, int[] B) {
? ? ? ? int res = 0;
? ? ? ? int[][] dp = new int[A.length + 1][B.length + 1];
? ? ? ? for (int i = 1;i < dp.length;i ++){
? ? ? ? ? ? for (int j = 1;j < dp[i].length;j ++){
? ? ? ? ? ? ? ? dp[i][j] = (A[i - 1] == B[j - 1]) ? dp[i - 1][j - 1] + 1 : 0;
? ? ? ? ? ? ? ? res = Math.max(res,dp[i][j]);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
}

② 簡化為一維數組。

class Solution { //41ms
? ? public int findLength(int[] A, int[] B) {
? ? ? ? int res = 0;
? ? ? ? int[] dp = new int[B.length + 1];
? ? ? ? for (int i = 1;i <= A.length;i ++){
? ? ? ? ? ? for (int j = B.length;j > 0;j --){
? ? ? ? ? ? ? ? if (A[i - 1] == B[j - 1]){
? ? ? ? ? ? ? ? ? ? dp[j] = dp[j - 1] + 1;
? ? ? ? ? ? ? ? ? ? res = Math.max(res,dp[j]);
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? dp[j] = 0;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return res;
? ? }
}

轉載于:https://my.oschina.net/liyurong/blog/1608199

總結

以上是生活随笔為你收集整理的求两个数组的最长重复子数组 Maximum Length of Repeated Subarray的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。