企业官网建设流程全解析

百度公司的发展历程,上海网站建设优化公司,网站页面需求,免费建立手机网站吗718.最长重复子数组 给两个整数数组 nums1 和 nums2 #xff0c;返回 两个数组中 公共的 、长度最长的子数组的长度 。 示例 1#xff1a; 输入#xff1a;nums1 [1,2,3,2,1], nums2 [3,2,1,4,7] 输出#xff1a;3 解释#xff1a;长度最长的公共子数组是 [3,2,1] 。示…718.最长重复子数组给两个整数数组nums1和nums2返回两个数组中公共的、长度最长的子数组的长度。示例 1输入nums1 [1,2,3,2,1], nums2 [3,2,1,4,7]输出3解释长度最长的公共子数组是 [3,2,1] 。示例 2输入nums1 [0,0,0,0,0], nums2 [0,0,0,0,0]输出5提示1 nums1.length, nums2.length 10000 nums1[i], nums2[i] 100该题使用暴力解法明显时间复杂度较多可以使用动态规划以空间换时间定义动态规划数组dp[i][j] 以下标i - 1为结尾的nums1和以下标j - 1为结尾的nums2最长重复子数组长度为dp[i][j]两层循环遍历若num1[i - 1] nums2[j - 1] 则说明当前的nums1中的i - 1的位置和j - 1相同在两者之前的长度上加一即可例如nums1 [1,2,3,2,1], nums2 [3,2,1,4,7]i 2,j 2时 nums1[1] nums[1] 在动态规划数组中说明在当前nums1的下标1位置和nums2的下标1相同最长子序列只需在nums1的下标0和nums2的下表0的位置处的最长子数组加一即可即dp[i][j] dp[i - 1][j - 1] 1public static void main(String[] args) { // 测试用 int[] nums1 {1,2,3,2,1}; int[] nums2 {3,2,1,4,7}; System.out.println(findLength(nums1, nums2)); } public static int findLength(int[] nums1, int[] nums2) { int[][] dp new int[nums1.length 1][nums2.length 1]; int res 0; for (int i 1; i nums1.length; i) { for (int j 1; j nums2.length; j) { if (nums1[i - 1] nums2[j - 1]){ dp[i][j] dp[i - 1][j - 1] 1; } res Math.max(res, dp[i][j]); } } return res; }以上为记录分享用代码较差请见谅