最新消息:XAMPP默认安装之后是很不安全的,我们只需要点击左方菜单的 "安全"选项,按照向导操作即可完成安全设置。

数组篇8_最长重复子数组[难度:中等]

XAMPP相关 admin 626浏览 0评论

来源:LeetCode

难度:中等

描述:

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

示例1:

drf37

分析:题目要求找到两个数组中最长的相同部分的长度,该题不要求咱们返回最长部分的内容,所以我们无需保存节点值,只计数并保留最大即可。

解题

方法一:暴力法解题

思路:将两个数组从头开始循环,每个元素进行挨个比较,有相同的部分时同时往下比较并进行计算,结果保留最大计数

代码:

 1public int findLength(int[] nums1, int[] nums2) {
 2    if (nums1 == null || nums2 == null) {
 3        return 0;
 4    }
 5    int n1 = nums1.length;
 6    int m2 = nums2.length;
 7    //结果
 8    int res = 0;
 9    for (int i = 0; i < n1; i++) {
10        for (int j = 0; j < m2; j++) {
11            int tempRes = 0;
12            //相等开始计数
13            if (nums1[i] == nums2[j]) {
14                tempRes++;
15                int t1 = i;
16                int t2 = j;
17                //边界判断
18                while (t1 < n1 - 1 && t2 < m2 -1) {
19                    //往下走还一样时,计数累加
20                    if (nums1[++t1] == nums2[++t2]) {
21                        tempRes++;
22                    } else {
23                        break;
24                    }
25                }
26            }
27            //保留最大结果
28            res = Math.max(res, tempRes);
29        }
30    }
31    return res;
32}

 

方法二:动态规划解题

思路:暴力解法中当两个数组存在公共部分的时候,公共部分在遍历的过程中会被遍历多次,例如j1~j5之间是公共部分,当数组走到j1时,会遍历到j5,走到j2又会遍历的j5…,此时咱们采用一个额外的数组将遍历过的每个位置公共长度存放起来。

例如:当nums1[i]==nums[j],那么该位置的公共长度则为nums1[i – 1] 与 nums[j – 1]的公共长度 + 1,如果nums1[i – 1] 与 nums[j – 1]不相等,那么nums1[i – 1] 与 nums[j – 1]为0,则nums1[i]与 nums[j] 的公共长度则为 1

代码:

 1public int findLength(int[] nums1, int[] nums2) {
 2    if (nums1 == null || nums2 == null) {
 3        return 0;
 4    }
 5    int n1 = nums1.length;
 6    int m2 = nums2.length;
 7    //注意 我采用的是从下往上的存储方法,
 8    // 即dp[i][j] 存储的是dp[i-1][j-1]的结果,所以申请的空间比原数组大一位
 9    int[][] dp = new int[n1 + 1][m2 + 1];
10    int res = 0;
11    //循环中 i小于等于n1,j 小于等于m2
12    for (int i = 1; i <= n1; i++) {
13        for (int j = 1; j <= m2; j++) {
14            //dp[i][j] 存储的是dp[i-1][j-1]的结果
15            if (nums1[i - 1] == nums2[j - 1]) {
16                dp[i][j] = dp[i - 1][j - 1] + 1;
17            }
18            //保留最大结果
19            res = Math.max(res, dp[i][j]);
20        }
21    }
22    return res;
23}

 

方法二:滑动窗口解题

思路:我们将两个数组分别想像成两把尺子,两个尺子相向而行,关系从不相交-相交-分开,咱们知道按位比较相交部分的相同部分长度即可,如下图

drf037

drf0037

drf00037

drf36

drf036

drf0036

drf00036

drf000036

drf0000036

代码:

 1public int findLength(int[] A, int[] B) {
 2    //确定两个数组谁长,
 3    // 短的在滑动的过程中有一段时间是整个数组与长的部分数组进行比较
 4    return A.length < B.length ? findMax(A, B) : findMax(B, A);
 5}
 6
 7int findMax(int[] A, int[] B) {
 8    int max = 0;
 9    int an = A.length, bn = B.length;
10    //开始相交时
11    for (int len = 1; len <= an; len++) {
12        max = Math.max(max, maxLen(A, 0, B, bn - len, len));
13    }
14    //包含时
15    for (int j = bn - an; j >= 0; j--) {
16        max = Math.max(max, maxLen(A, 0, B, j, an));
17    }
18    //分开时
19    for (int i = 1; i < an; i++) {
20        max = Math.max(max, maxLen(A, i, B, 0, an - i));
21    }
22    return max;
23}
24
25//两截数组的最大相同长度
26//两截位置分别为 i ~ i+len 和 j ~ j + len
27int maxLen(int[] a, int i, int[] b, int j, int len) {
28    int count = 0, max = 0;
29    for (int k = 0; k < len; k++) {
30        if (a[i + k] == b[j + k]) {
31            count++;
32        } else if (count > 0) {
33            max = Math.max(max, count);
34            count = 0;
35        }
36    }
37    return count > 0 ? Math.max(max, count) : max;
38}

以上仅是个人思路解法

转载请注明:XAMPP中文组官网 » 数组篇8_最长重复子数组[难度:中等]

您必须 登录 才能发表评论!