Leetcode 718 最长重复子数组

news/2024/4/17 7:57:28

题意理解:

        给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 

        如:

        nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]

        则最长重复子序列为: 321   

        长度为3

        这里采用动态规划解决这个问题。最长公共子序列,涉及从nums1的i位置和nums2的j位置,长度为x的公共子序列。

        所以:我们这里定义一个二维数组来统计状态。

解题思路:

        (1)定义二维dp数组

           dp[i][j]表示从nums1中到第i个位置之前,即nums1[i-1]的位置, 从nums2中到第j个位置以前,即nums2[j-1]的位置,所获得的最长公共子序列。

        (2)初始化

           dp[0][i] 和dp[0][j]都是拿一个空数组和一个数组求最长公共子序列,所以都初始化为0

           其余位置在尚未操作之前都初始化为0。

        (3)递推公式

          对dp[i][j]进行赋值

          首先判断到当前位置的数值是否一致:

          即:nums1[i-1]==nums[j-1]

          若满足条件则有:  dp[i][j]=dp[i-1][j-1]+1

           (4)遍历顺序:先便利哪个数组都是可以的

          由于dp[i][j]表示的是到nums1的第i个位置以前,即nums1[i-1],nums2的第j个位置以前,即nums[j-1]的最长公共子序列的,所以i<=num1.size,j<=nums2.size

1.解题

public int findLength(int[] nums1, int[] nums2) {int[][] dp=new int[nums1.length+1][nums2.length+1];for(int i=0;i<nums1.length;i++){Arrays.fill(dp[i],0);}int max=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;}max=Math.max(dp[i][j],max);}}return max;}

2.分析

时间复杂度:O(n^2)

空间复杂度:O(n)


https://www.xjx100.cn/news/3271426.html

相关文章

使用word2vec+tensorflow自然语言处理NLP

目录 介绍&#xff1a; 搭建上下文或预测目标词来学习词向量 建模1&#xff1a; 建模2&#xff1a; 预测&#xff1a; 介绍&#xff1a; Word2Vec是一种用于将文本转换为向量表示的技术。它是由谷歌团队于2013年提出的一种神经网络模型。Word2Vec可以将单词表示为高维空间…

ctfshow-php特性(web102-web115)

目录 web102 web103 web104 web105 web106 web107 web108 web109 web110 web111 web112 web113 web114 web115 实践是检验真理的 要多多尝试 web102 <?php highlight_file(__FILE__); $v1$_POST[V1]; $v2$_GET[v2]; $v3$_GET[v3]; $v4is_numeric($v2)and is…

MATLAB Coder从入门到放弃

一、MATLAB Coder入门 1 MATLAB Coder是什么 从 MATLAB 代码生成 C 和 C 代码 MATLAB Coder™ 可从 MATLAB 代码生成适用于各种硬件平台&#xff08;从桌面计算机系统到嵌入式硬件&#xff09;的 C 和 C 代码。它支持大多数 MATLAB 语言和广泛的工具箱。您可以将生成的代码作…

Android 移动应用开发 创建第一个Android项目

文章目录 一、创建第一个Android项目1.1 准备好Android Studio1.2 运行程序1.3 程序结构是什么app下的结构res - 子目录&#xff08;所有图片、布局、字AndroidManifest.xml 有四大组件&#xff0c;程序添加权限声明 Project下的结构 二、开发android时&#xff0c;部分库下载异…

STM32 寄存器操作 GPIO 与中断

一、如何使用stm32寄存器点灯&#xff1f; 1.1 寄存器映射表 寄存器本质就是一个开关&#xff0c;当我们把芯片寄存器配置指定的状态时即可使用芯片的硬件能力。 寄存器映射表则是开关的地址说明。对于我们希望点亮 GPIO_B 的一个灯来说&#xff0c;需要关注以下的两个寄存器…

搜索二维矩阵[中等]

一、题目 给你一个满足下述两条属性的m x n整数矩阵&#xff1a; 【1】每行中的整数从左到右按非严格递增顺序排列。 【2】每行的第一个整数大于前一行的最后一个整数。 给你一个整数target&#xff0c;如果target在矩阵中&#xff0c;返回true&#xff1b;否则&#xff0c;返…

Linux第50步_移植ST公司的linux内核第2步_编译ST公司的linux源码和修改网络驱动

1、修改“linux-5.4.31”目录下的“Makefile” 1)、使用VSCode打开“linux-5.4.31.code-workspace” 2)、点击“linux-5.4.31”目录下的“Makefile” 3)、点击“编辑”&#xff0c;点击“查找”&#xff0c;输入“CROSS_COMPILE回车”&#xff0c;找到“ARCH ? $(SUBARCH)”…

Transformer实战-系列教程16:DETR 源码解读3(DETR类)

&#x1f6a9;&#x1f6a9;&#x1f6a9;Transformer实战-系列教程总目录 有任何问题欢迎在下面留言 本篇文章的代码运行界面均在Pycharm中进行 本篇文章配套的代码资源已经上传 点我下载源码 DETR 算法解读 DETR 源码解读1&#xff08;项目配置/CocoDetection类&#xff09; …