住房和建设部网站,软件工程培训机构哪家好,上海开艺设计集团有限公司,怎么开发自己的商城718. 最长重复子数组 问题描述#xff1a;
给两个整数数组 nums1 和 nums2 #xff0c;返回 两个数组中 公共的 、长度最长 的 子数组 的 长度 。
示例 1#xff1a; 输入#xff1a;nums1 [1,2,3,2,1], nums2 [3,2,1,4,7] 输出#xff1a;3 解释#xff1a;长度最长… 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
问题分析
动态规划老题目了前面有 LeetCode:1143. 最长公共子序列 - Python , 求子序列的题目这个是子数组如果是字符串的话就求子串大家注意子串与子序列是有区别的哦。子序列 一般是指的是相对位置不变就是子序列而子串是严格连续的。这个时候其实可以转换成公共前缀或者公共后缀(以什么结尾)的问题设假设dp[i][j] 表示字符串text1[0:i]和字符串text2[0:j]的最长公共后缀串的长度现在讨论细节 (1) 很显然当i0 or j0时dp为0。 (2) text1[0:i] text2[0:j] 时很显然就上一个状态加上1即dp[i][j]dp[i-1][j-1]1 (3) text1[0:i] ! text2[0:j] 时不相等那就当前字符串text1[0:i]和text2[0:j] 没有公共后缀串所以就是0了即dp[i][j]0所以整体状态转移方差为
i0 or j0 : dp[i][j] 0
nums1[i-1] nums2[j-1]: dp[i][j] dp[i-1][j-1] 1
nums1[i-1] ! nums2[j-1]: dp[i][j] 0Python3实现
# Time :2023/09/02
# Author :Liu
# 动态规划class Solution:def findLength(self, nums1: List[int], nums2: List[int]) - int:m, n len(nums1), len(nums2)dp [[0] * (n 1) for _ in range(m 1)]ans, sub 0, # 最长公共子串长度最长公共子串for i in range(1, m 1):for j in range(1, n 1):if nums1[i - 1] nums2[j - 1]:dp[i][j] dp[i - 1][j - 1] 1# else:# dp[i][j] 0 # 这一步其实没必要本身就为0if ans dp[i][j]: # 更新最长子串ans dp[i][j]# sub nums1[i-ans: i] # 获取字符串return ans # , subif __name__ __main__:solu Solution()nums1, nums2 [1, 2, 3, 2, 1], [3, 2, 1, 4, 7]print(solu.findLength(nums1, nums2)) # 3 [3, 2, 1]相关参考题目链接 声明 总结学习有问题或不当之处可以批评指正哦谢谢。
