问题描述:
给两个整数数组 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
提示:文章来源:https://www.toymoban.com/news/detail-693796.html
1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 100
问题分析:
- 动态规划老题目了,前面有 LeetCode:1143. 最长公共子序列 - Python , 求
子序列
的题目,这个是子数组
,如果是字符串
的话就求子串
,大家注意子串
与子序列
是有区别的哦。子序列
一般是指的是相对位置不变就是子序列
而子串
是严格连续
的。 - 这个时候其实可以转换成
公共前缀
或者公共后缀
(以什么结尾)的问题,设假设dp[i][j]
表示字符串text1[0:i]
和字符串text2[0:j]
的最长公共后缀串
的长度,现在讨论细节:
(1) 很显然当i=0 or j=0
时,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
,所以整体状态转移方差为:
i=0 or j=0 : 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] = 0
Python3实现:
# @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 # 这一步其实没必要,本身就为0
if ans < dp[i][j]: # 更新最长子串
ans = dp[i][j]
# sub = nums1[i-ans: i] # 获取字符串
return ans # , sub
if __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]
相关参考:题目链接
声明: 总结学习,有问题或不当之处,可以批评指正哦,谢谢。文章来源地址https://www.toymoban.com/news/detail-693796.html
到了这里,关于LeetCode:718. 最长重复子数组 - Python的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!