邢台学校网站建设,织梦如何仿手机网站,成品免费ppt网站,惠州建设工程造价管理协会网站718. 最长重复子数组 原题链接#xff1a;完成情况#xff1a;题解#xff1a;方法一#xff1a;动态规划方法二#xff1a;滑动窗口方法三#xff1a;二分查找 哈希 原题链接#xff1a;
718. 最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repe… 718. 最长重复子数组 原题链接完成情况题解方法一动态规划方法二滑动窗口方法三二分查找 哈希 原题链接
718. 最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
完成情况 题解
方法一动态规划 package 西湖算法题解___中等题;public class __718最长重复子数组__动态规划 {//子数组的话默认是连续的。public int findLength(int[] nums1, int[] nums2) {/*给两个整数数组 nums1 和 nums2 返回 两个数组中 公共的 、长度最长的子数组的长度 。当然了肯定是要求顺序而非连续。那么必然就需要用到动态数组采取累积的形式*/int n nums1.length,m nums2.length;int dp_findLength [][] new int[n1][m1];int res 0;for (int in-1;i0;i--){for (int jm-1;j0;j--){dp_findLength[i][j] (nums1[i] nums2[j] ? dp_findLength[i1][j1] 1:0);res Math.max(res,dp_findLength[i][j]);}}return res;}
}
方法二滑动窗口 package 西湖算法题解___中等题;public class __718最长重复子数组__滑动窗口 {public int findLength(int[] nums1, int[] nums2) {int n nums1.length,m nums2.length;int res 0;for (int i0;in;i){int len Math.min(m,n-i);int maxLen maxLength(nums1,nums2,i,0,len);res Math.max(res,maxLen);}for (int i0;im;i){int len Math.min(n,m-i);int maxLen maxLength(nums1,nums2,0,i,len);res Math.max(res,maxLen);}return res;}private int maxLength(int[] nums1, int[] nums2, int addA, int addB, int len) {int res 0,k0;for (int i0;ilen;i){if (nums1[addAi] nums2[addBi]){k;}else {k0;}res Math.max(res,k);}return res;}
}
方法三二分查找 哈希 package 西湖算法题解___中等题;import java.util.HashSet;
import java.util.Set;public class __718最长重复子数组__二分查找_哈希表 {int mod 1000000009;int base 113;public int findLength(int[] nums1, int[] nums2) {int left 1,right Math.min(nums1.length,nums2.length)1;while (left right){int mid (left right) 1;if (myCheck(nums1,nums2,mid)){left mid 1;}else {right mid;}}return left - 1;}private boolean myCheck(int[] A, int[] B, int len) {long hashA 0;for (int i0;ilen;i){hashA (hashA * base A[i]) % mod;}SetLong bucketA new HashSetLong();bucketA.add(hashA);long mult qPow(base,len - 1);for (int i len;i A.length;i){hashA ((hashA - A[i - len] * mult % mod mod) % mod * base A[i]) % mod;bucketA.add(hashA);}long hashB 0;for (int i0;ilen;i){hashB (hashB * base B[i])%mod;}if (bucketA.contains(hashB)){return true;}for (int ilen;iB.length;i){hashB ((hashB - B[i - len] * mult % mod mod) % mod * base B[i]) % mod;if (bucketA.contains(hashB)){return true;}}return false;}/*** 使用快速幂计算x^n % mod 的值* param x* param n* return*/private long qPow(long x, long n) {long res 1L;while (n ! 0){if ((n1) ! 0){res res * x % mod;}x x*x % mod;n 1;}return res;}
}
