• 软件:1160
  • 资讯:41601|
  • 收录网站:97880|

IT精英团

407,动态规划和滑动窗口解决最长重复子数组

407,动态规划和滑动窗口解决最长重复子数组

浏览次数:
评论次数:
编辑: 乐咏
信息来源: 51CTO博客
更新日期: 2021-06-13 00:17:50
摘要

407,动态规划和滑动窗口解决最长重复子数组, Neverbeafraidtoreachforthestars,becauseevenifyoufall,you'llalwaysbewearingaparent-chute.永远不要害怕去摘星星,因为就算你跌下来,你永远有“父母牌”降落伞防身。问题描述给两个整数数组A和B,返回两个数组中公共的、长度最长的子数组的长度。 示例:输入:

  • 资讯详情

Never be afraid to reach for the stars, because even if you fall, you'll always be wearing a parent-chute.

永远不要害怕去摘星星,因为就算你跌下来,你永远有“父母牌”降落伞防身。

问题描述

给两个整数数组 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

动态规划

这题一看就知道其实就是求最长公共子串问题,不懂的可以看下前面的370,最长公共子串和子序列,只不过换了种说法,换汤不换药,本质还是没变。我们就以题中的示例画个图来看一下

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

最长的公共子数组就是上面红色所对应的[3,2,1],长度是3。

递推公式是

  •  
if(s1.charAt(i) == s2.charAr(j))    dp[i][j] = dp[i-1][j-1] + 1;else    dp[i][j] = 0;

有了递推公式,代码就容易多了,我们来看下完整代码

 1public int findLength(int[] A, int[] B) {
2    int max = 0;
3    int[][] dp = new int[A.length + 1][B.length + 1];
4    for (int i = 1; i <= A.length; i++) {
5        for (int j = 1; j <= B.length; j++) {
6            if (A[i - 1] == B[j - 1]) {
7                dp[i][j] = dp[i - 1][j - 1] + 1;
8                max = Math.max(max, dp[i][j]);
9            }
10        }
11    }
12    return max;
13}
14

这里的二维数组dp长和宽都要加1是为了减少判断,当然也可以不加1,但这样会多了一些边界的判断,我们来看下不加1的代码

 1public int findLength(int[] A, int[] B) {
2    int max = 0;
3    int[][] dp = new int[A.length][B.length];
4    for (int i = 0; i < A.length; i++) {
5        for (int j = 0; j < B.length; j++) {
6            if (A[i] == B[j]) {
7                if (i > 0 && j > 0)
8                    dp[i][j] = dp[i - 1][j - 1] + 1;
9                else
10                    dp[i][j] = 1;
11                max = Math.max(max, dp[i][j]);
12            }
13        }
14    }
15    return max;
16}

如果看过之前写的370,最长公共子串和子序列,我们还可以把二维数组改为一维数组来减少空间复杂度

 1public int findLength(int[] A, int[] B) {
2    int max = 0;
3    int[] dp = new int[B.length + 1];
4    for (int i = 1; i <= A.length; i++) {
5        for (int j = B.length; j >= 1; j--) {
6            if (A[i - 1] == B[j - 1])
7                dp[j] = dp[j - 1] + 1;
8            else
9                dp[j] = 0;
10            max = Math.max(max, dp[j]);
11        }
12    }
13    return max;
14}

注意这里第二个for循环是从后往前遍历的,这是因为dp后面的值会依赖前面的值,但前面的值不会依赖后面的值,如果我们改变后面的值对前面的值不会有影响,但改变前面的值会影响面的值,所以这里我们从后往前计算是最合适的。

滑动窗口

第2种方式是滑动窗口,文字叙述不好理解,我们就以[1, 2, 3, 2, 1]和[3,2,1,4]为例来举例说明,这两个数组我故意弄成两个长度不一样的,我们画个图来看一下

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

watermark,size_16,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_90,type_ZmFuZ3poZW5naGVpdGk=

相当于说第一个数组位置不动,第二个数组每次往右移一位,搞懂了上的分析过程,代码就容易多了,我们来看下

 1public int findLength(int[] A, int[] B) {
2    if (A.length < B.length)
3        return findLengthHelper(A, B);
4    return findLengthHelper(B, A);
5}
6
7public int findLengthHelper(int[] A, int[] B) {
8    int aLength = A.length, bLength = B.length;
9    //total是总共运行的次数
10    int total = aLength + bLength - 1;
11    int max = 0;
12    for (int i = 0; i < total; i++) {
13        //下面一大坨主要判断数组A和数组B比较的起始位置和比较的长度
14        int aStart = 0;
15        int bStart = 0;
16        int len = 0;
17        if (i < aLength) {
18            aStart = aLength - i - 1;
19            bStart = 0;
20            len = i + 1;
21        } else {
22            aStart = 0;
23            bStart = i - aLength + 1;
24            len = Math.min(bLength - bStart, aLength);
25        }
26        int maxlen = maxLength(A, B, aStart, bStart, len);
27        max = Math.max(max, maxlen);
28    }
29    return max;
30}
31
32//计算A和B在上面图中红色框内的最大长度
33public int maxLength(int[] A, int[] B, int aStart, int bStart, int len) {
34    int max = 0, count = 0;
35    for (int i = 0; i < len; i++) {
36        if (A[aStart + i] == B[bStart + i]) {
37            count++;
38            max = Math.max(max, count);
39        } else {
40            count = 0;
41        }
42    }
43    return max;
44}

总结

其实这道题求的就是最长公共子串问题,通过上面的图分析,可以发现第一种方式和第二种方式都比较好理解,但第一种方式代码明显比第二种少了很多。

标签: 数组
406,剑指 Offer-二维数组中的查找
« 上一篇
返回列表
下一篇 »
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
你会是第一个来这里评论的人吗?
最近发布资讯
更多