【LeetCode】718. 最长重复子数组
2023-09-14 09:13:24 时间
1 题目
- 注意子数组和子序列的区别
- 本题如果不加限制就使用动态规划做,很容易变成求最长的子序列的长度
2 思想
使用动态规划解决这个问题。
- 令
dp[i,j]
为nums1中前i个数中和nums2中前j个数中最长的重复子数组。 - 递推公式:
因为是最长子数组,也就是要求连续,所以dp[i,j]
的推导一定和dp[i-1,j-1]
紧密联系在一起。 也就是必须要求nums1[i-1] == nums2[j-1]
才能保证满足递增。递推公式可以参考下面代码。
3 代码
class Solution:
def findLength(self, nums1: List[int], nums2: List[int]) -> int:
dp = [[0]*len(nums2) for i in range(len(nums1))] # dp[i,j] 表示nums1中以第i个数结尾的数和nums2的第j个结尾数的最大值
l1 = len(nums1)
l2 = len(nums2)
max_res = 0
#初始化
for i in range(l2):
if nums1[0] == nums2[i]:
dp[0][i] = 1
max_res = max(max_res,dp[0][i]) # 更新得到最大值
for i in range(l1):
if nums2[0] == nums1[i]:
dp[i][0] = 1
max_res = max(max_res,dp[i][0]) # 更新得到最大值
for i in range(1,len(nums1)):
for j in range(1,len(nums2)):
if nums1[i] == nums2[j]:
if nums1[i-1] == nums2[j-1]:
dp[i][j] = dp[i-1][j-1] + int(nums1[i]==nums2[j])
else:
dp[i][j] = 1
max_res = max(max_res,dp[i][j]) # 更新得到最大值
# print(dp)
return max_res
相关文章
- Java实现LeetCode 839. 相似字符串组 (深度优先搜索,并查集,图)
- Java实现 LeetCode 718 最长重复子数组(动态规划)
- Java实现 LeetCode 706 设计哈希映射(数组+链表)
- Java实现 LeetCode 689 三个无重叠子数组的最大和(换方向筛选)
- Java实现 LeetCode 617 合并二叉树(遍历树)
- Java实现 LeetCode 558 四叉树交集(四叉树,第一次遇到,研究了半天)
- Java实现 LeetCode 457 环形数组循环
- Java实现 LeetCode 442 数组中重复的数据
- Java实现 LeetCode 1013 将数组分成和相等的三个部分
- Java实现 LeetCode 86 分割链表
- Java实现 LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
- Java实现 LeetCode 24 两两交换链表中的节点
- Java实现 Leetcode 88 合并两个有序数组
- LeetCode(26): 删除排序数组中的重复项
- leetcode - 子数组最大平均值
- LeetCode-1144. 递减元素使数组呈锯齿状【贪心,数组】
- LeetCode-1773. 统计匹配检索规则的物品数量【数组,字符串】
- leetcode 1438. 绝对差不超过限制的最长连续子数组----双指针篇3,滑动窗口篇2
- 【leetcode 33】搜索旋转排序数组(第二遍)
- Leetcode 845. 数组中的最长山脉(可以,被我做出来了)
- Leetcode 718. 最长重复子数组(暴力枚举,待解决)
- Leetcode 1328. 破坏回文串(可以,已解决)
- Leetcode 2270. 分割数组的方案数(可以,已解决)
- [LeetCode] 152. 乘积最大子数组 ☆☆☆(动态规划)
- [LeetCode] 26. Remove Duplicates from Sorted Array ☆(从有序数组中删除重复项)
- [Leetcode]-Rotate Array