力扣718-最长重复子数组(Java详细题解)

news/2024/9/22 18:01:36/

题目链接:718. 最长重复子数组 - 力扣(LeetCode)

前情提要:

因为本人最近都来刷dp类的题目所以该题就默认用dp方法来做。

dp五部曲。

1.确定dp数组和i下标的含义。

2.确定递推公式。

3.dp初始化。

4.确定dp的遍历顺序。

5.如果没有ac打印dp数组 利于debug。

每一个dp题目如果都用这五步分析清楚,那么这道题就能解出来了。

题目思路:

如果没有接触过子序列问题,那么第一次做这个题还是很有难度。

本题要求俩个数组中的公共最长连续子序列。

注意这里是要求连续的。

那么如果你做过674. 最长连续递增序列 - 力扣(LeetCode)或者看了我的题解力扣674-最长连续递增序列(Java详细题解)-CSDN博客,那么会好理解这道题一点。

话不多说,直接开始我们的dp五部曲。

1.确定dp数组和i下标的含义。

该题是要求俩个数组公共的子数组长度,那我们就要比较俩个数组的任意俩个元素。那我们是不是要用二维的dp数组来记录下这个状态呀。

用二维dp数组来记录每一个数组元素和另一个数组元素相比较的结果。

所以就要用到dp[i] [j]了。

注意这里dp[i] [j]的含义是指以i - 1结尾的数组和j - 1为结尾的数组俩个数组的最长公共子序列。

这里的dp含义在下面很多篇都会用到,大家要牢记这点。

至于为什么要设置i - 1和j - 1这样的含义,我们在初始化那个环节会讲,这里大家记住这个定义就好。

2.确定递推公式。

因为是要求公共的子数组,所以可能是当nums[i - 1] == nums[j - 1]的时候加入我们的结果。

为什么是i - 1和j - 1?

因为dp数组定义的就是i - 1结尾的数组和j - 1为结尾的数组俩个数组的最长公共子序列,所以只有nums[i - 1] == nums[j - 1]时,他们的dp[i] [j]才能被推出。

dp[i] [j] = 什么呢?

当nums[i - 1] == nums[j - 1]的时候,dp[i] [j] = dp[i - 1] [j - 1] + 1。

因为是求连续的公共数组,所以dp[i] [j] 只与他们前面一个状态dp[i - 1] [j - 1]有关。

当nums[i - 1] == nums[j - 1],dp[i] [j]是由dp[i - 1] [j - 1](下标i - 2结尾的数组和j - 2为结尾的数组俩个数组的最长公共子序列长度)加上 nums[i - 1] nums[j - 1]这俩个元素相同的长度,也就是1。

所以dp[i] [j] = dp[i - 1] [j - 1] + 1。

3.dp初始化。

该题的初始化部分很重要。

由递推公式可以看出,每一个dp[i] [j]在二维数组中都是由它左上的位置得出,所以要初始化dp[i] [0]和dp[0] [i]。也就是第一排和第一列。

由于dp数组定义的是以i - 1结尾的数组和j - 1为结尾的数组俩个数组的最长公共子序列。

所以第一排(dp[0] [i])是以下标-1为结尾的数组和i - 1为结尾的数组俩个数组的最长公共子序列。

以下标-1为结尾的数组不存在,所以他们的最长公共子序列自然就为0。

第一列同理可以得出也都初始化为0。

这就是我们为什么将dp数组定义为以i - 1和j - 1为结尾的数组的最长公共子序列。

这样便于初始化。如果定义为以i和j为结尾的数组最长公共子序列。

那么第一排第一列初始化就不一样了。

他们第一排和第一列是有意义的,并且他们还可能相同。

所以要遍历一遍第一列和第一排,如果nums[i] == nums[j] 那么dp[i] [j] = 1。

因为他们的值相同,第一排和第一列的最长公共子序列就为该元素。

4.确定dp的遍历顺序。

由递推公式可以看出dp[i] [j] 由dp[i - 1] [j - 1]可得。所以要从左到右,从上到下去遍历。

5.如果没有ac打印dp数组 利于debug。

在这里插入图片描述

最终代码:

java">class Solution {public int findLength(int[] nums1, int[] nums2) {//这里的dp含义是 以i - 1和j - 1为结尾的俩个数组最长子数组的长度。//为什么 定义 i- 1和 j - 1呢 是为了初始化方便。//递推公式 当nums1[i - 1] == nums2[j - 1] 说明俩个数组出现相等的值了 既然出现相等的值了//那我的dp[i][j] 就要加1了 因为我dp[i][j]是记录的i - 1和j - 1为结尾的俩个数组最长子数组的长度//那么在哪个状态上家呢?//其实子数组就是一种连续子序列 他的状态只与他的前一状态有关  所以与dp[i - 1][j - 1]有关//那么dp[i][j] = dp[i - 1][j - 1] + 1//紧接着我们就要进行初始化了//int [][] dp = new int [nums1.length + 1][nums2.length + 1];int result = 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;}//因为只有nums1[i - 1] == nums2[j - 1]才会进入我们的dp数组,所以任意位置的dp数组都可能是最大的,所以我们要遍历一遍求最大的。result = Math.max(result,dp[i][j]);}}return result;}
}

这一篇博客就到这了,如果你有什么疑问和想法可以打在评论区,或者私信我。

我很乐意为你解答。那么我们下篇再见!


http://www.ppmy.cn/news/1528944.html

相关文章

硬件(驱动开发概念)

驱动程序开发 裸机驱动&#xff08;无操作系统&#xff09; Linux驱动 以计算机技术为基础&#xff0c;在软件和硬件层间可以被剪裁的专业硬件计算机系统 SOC&#xff1a;片上系统 Kernel&#xff1a;内核 x86 &#xff08;CISC:complex instruction set computer 复杂指令…

【Proteus仿真】基于51单片机的L298N电机电速调节

目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机&#xff0c;L298N电机驱动连接电机&#xff0c;采用调节PWM占空比来控制电机速度转动。 仿真图&#xff1a; 编辑 二、硬件资源 基于KEIL5编写C代码&#xff0c;PROTEUS8.15进行…

图卷积网络(GCN)与图注意力网络(GAT)基础实现及其应用

创作不易&#xff0c;您的打赏、关注、点赞、收藏和转发是我坚持下去的动力&#xff01; 图卷积网络&#xff08;Graph Convolutional Networks, GCN&#xff09;是一种能够直接在图结构数据上进行操作的神经网络模型。它能够处理不规则的数据结构&#xff0c;捕获节点之间的依…

负载均衡服务由几部分组成?分别是什么

负载均衡服务由几部分组成?分别是什么&#xff1f;均衡服务通常由六部分组成&#xff0c;分别是客户端、负载均衡器、后端服务器、负载均衡算法、监控和健康检查及会话保持。这六者互相协同工作&#xff0c;实现了流量的有效分发和系统的高可用性。这种结构不仅提高了系统的容…

opc服务器与opc服务器如何通讯

OPC&#xff08;OLE for Process Control&#xff0c;即过程控制对象链接&#xff09;是一种工业自动化领域常用的通讯协议&#xff0c;它提供了一种标准化的方式&#xff0c;使得不同厂家的设备可以互相通讯。OPC服务器是运行在计算机上的软件程序&#xff0c;用于接收和处理来…

深度学习-从零基础快速入门到项目实践,这本书上市了!!!

此书地址&#xff1a; 《【2024新书】深度学习 从零基础快速入门到项目实践 文青山 跟我一起学人工智能 机器学习算法原理代码实现教程 深度学习项目分析 深度学习 从零基础快速入门到项目实践》【摘要 书评 试读】- 京东图书 除深度学习外我还写了一本软件测试书。我大概是国…

音频左右声道数据传输_2024年9月6日

如下为音频数据传输标准I2S总线的基本时序图 I2S slave将I2S master发送来的左右声道的串行数据DATA转变为16bit的并行数据 WS为左右声道选择信号&#xff0c;WS高代表左声道&#xff0c;WS低代表右声道; WS为高和为低都持续18个周期&#xff0c;前面16个周期用来传输数据。 I2…

windows安装docker 本地打包代码

参考文章1&#xff1a;https://gitcode.csdn.net/65ea814b1a836825ed792f4a.html 参考文章2&#xff1a; Windows 安装docker&#xff08;详细图解&#xff09;-CSDN博客 一 下载 Docker Desktop 在官网上下载 Docker Desktop&#xff0c;可以从以下链接下载最新版本&#x…