首页 > 其他分享 >718 最长重复数组

718 最长重复数组

时间:2023-03-14 20:36:44浏览次数:52  
标签:718 res 最长 nums2 数组 nums1 dp

题目 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

思路

  • 动态规划
  • 公式:dp[i][j] = dp[i-1][j-1] + 1
    只有当nums[i-1] == nums[j-1]时才会运行公式
  • 一定要自己画出来矩阵走走就特别清晰了

代码

class Solution:
    def findLength(self, nums1: List[int], nums2: List[int]) -> int:
        row = len(nums1)+1
        col = len(nums2)+1
        dp = [[0]*col for i in range(row)]
        res = 0
        for i in range(1, row):
            for j in range(1, col):
                if nums1[i-1] == nums2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
            res = max(res, max(dp[i]))
        return res

标签:718,res,最长,nums2,数组,nums1,dp
From: https://www.cnblogs.com/edkong/p/17216219.html

相关文章

  • # 909 -「java」一维数组展开+ BFS解决 -蛇梯棋- 最短步进次数 的详细思路
    Tags:中等数组BFSjava 题目链接:909.蛇梯棋 注意事项[题目中的坑]:【"S形"的概念】:题目开头举例的N*N的数组,其内标示的1~N²数字,指代的是......
  • 800. 数组元素的目标和(双指针,二分)
    https://www.acwing.com/problem/content/802/二分:枚举a,对于每一个a[i],都二分一下求x-a[i],是否在b数组中#include<iostream>usingnamespacestd;constintN=1......
  • HJ83 二维数组操作 -数组
        importsysdefinitialize(m,n):if0<n<10and0<m<10:return0else:return-1definsert_line(m,up):ifm<9and0<=......
  • 数组之长度最小的子数组
    1、给定一个含有 n 个正整数的数组和一个正整数target。找出该数组中满足其和≥target的长度最小的连续子数组 [numsl,numsl+1,...,numsr-1,numsr],并返回其......
  • 树状数组入门
    前言树状数组作为维护序列区间修改与查询的利器是每一个 “OIer” 都应该要掌握的知识点今天,我们来详细的整理一下树状数组的知识脉络目录一.树状数组简介二.树状......
  • 32位汇编语言实现求数组的最大值
    INCLUDEIrvine32.inc.dataarrdd99,2,3,1,22,188,7,77,54,10;定义数组 lendd($-arr)/4;用当前地址减去数组首元素地址除以4得到数组的长度.codemainPROC......
  • 差分数组
    题目难度要点拼车●不需要构造原始数组,直接判断即可航班预定统计●构造原始数组区间加法●构造原始数组拼车classSolution{publicboo......
  • 【LeetCode回溯算法#11】解数独,这次是真的用回溯法处理二维数组
    解数独力扣题目链接(opensnewwindow)编写一个程序,通过填充空格来解决数独问题。一个数独的解法需遵循如下规则:数字1-9在每一行只能出现一次。数字1-9在每一列只......
  • 剑指 Offer 11.旋转数组的最小数字
    题目描述   解法二分查找思路:设i为左界,j为右界,中点为mid;将number[mid]与number[j]进行比较,会出现一下情况:number[mid]<number[j]时,说明number[mid]是最......
  • Java数组
    Java数组1.数组概述数组的定义数组是相同类型数据的有序集合数组描述的是相同类型的若干个数据,按照一定的先后次序排列组合而成。其中,每一个数据称作一个数组元......