718. 最长重复子数组

给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。

目录

1、题目分析

2、解题分析

3、代码


示例 1:

输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释: 
长度最长的公共子数组是 [3, 2, 1]。

1、题目分析

求两个数组公共的子数组的长度,那么可以用较短的那个字符串去匹配长的字符串,使用枚举法。像最长最短的往往都可以用动态规划,不过要找出动态转移方程来。

2、解题分析

主要说一下滑窗法,选取较短的那个作为滑动的数组。

  • 声明一个临时数组,遍历较短的那个数组
  • 将遍历到的元素添加到临时数组中去,然后判断得到的字符串有没有在较长的数组中
    • 如果在的话就更新公共子数组的长度
    • 如果不在的话那就从头开始,不要之前的元素
  • 最后返回更新的最大长度

3、代码

class Solution:
    def findLength(self, A: List[int], B: List[int]) -> int:
        
        # 动态规划算法
        l1 = len(A) 
        l2 = len(B) 
        #dp[i][j]代表以A[i-1]与B[j-1]结尾的公共字串的长度,公共字串必须以A[i-1],B[j-1]结束
        dp = [[0 for _ in range(l2+1)] for _ in range(l1+1)] 
        for i in range(1,l1+1): 
            for j in range(1,l2+1): 
                if A[i-1] == B[j-1]: 
                    dp[i][j] = dp[i-1][j-1] + 1 
        return max(max(row) for row in dp)

        '''
          3 2 1 4 7
        1 0 0 1 0 0
        2 0 1 0 0 0
        3 1 0 0 0 0
        2 0 2 0 0 0
        1 0 0 3 0 0
        '''


        #如果A或者B有一个数组是空的就直接返回None
        if not A or not B:
            return None
        #如果A的长度是大于B的长度,那就交换一下,因为我想让A当滑窗的那个数组
        if len(A)>len(B):
            A,B = B,A
        #对A和B做处理
        A = [str(i) for i in A]
        B = ','+','.join([str(i) for i in B])+','
        # B:',3,2,1,4,7,'
        # 为啥把B搞成这个鬼样子呢?因为避免出现歧义
        # 举个例子A=[7] B=[17]
        # temp = 7->',7,' 这样就不会出现歧义,否则就这样
        # temp = 7->7, 因为B是字符串呀,所以‘7,’ in B中,这样结果就出现误判了
        # 因此必须要把B和Temp搞成',xx,x,x,xx,'这个鬼样子
        
        
        #初始化结果和一个临时数组
        res = 0
        temp=[]

        for i in A:
            temp.append(i)
            if ','+','.join(temp)+',' in B:
                res = max(res,len(temp))
            else:
                temp = temp[1:]
        return res

总结:这个题目应该是考察的动态规划,但是在实际的操作中动态规划的时间复杂度和空间复杂度更高。

热门文章

暂无图片
编程学习 ·

Spring Boot整合Zookeeper实现配置中心

简介 使用背景 说到配置中心,目前市面上用的较多的配置中心都广为人知,比如百度的Disconf、Spring Cloud Config、携程的Apollo、阿里的Nacos等。由于项目组一直是使用的zookeeper作为配置中心,所以来学习使用。 实现原理在Zookeeper建立一个根节点,比如/CONFIG,代表某个配…
暂无图片
编程学习 ·

java 中的反射技术

java代码 @SpringBootTest(classes = {ShujiegouApplication.class}) @RunWith(SpringJUnit4ClassRunner.class) public class FansheTest {@Testpublic void test1() throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {SysColumn sysColumn …
暂无图片
编程学习 ·

JS面试题

霖呆呆的近期面试128题汇总(含超详细答案) | 掘金技术征文 由浅入深,66条JavaScript面试知识点 2020 前端面试 | 第一波面试题总结 2020 前端面试 | 第二波面试题总结 window.onload和$(document).ready()区别 window.onload必须等到页面内的所有元素加载完毕后才能执行 所有元…
暂无图片
编程学习 ·

Prometheus的安装与配置

一、什么是PrometheusPrometheus是由SoundCloud开发的开源监控报警系统和时序列数据库(TSDB)。Prometheus使用Go语言开发,是Google BorgMon监控系统的开源版本。2016年由Google发起Linux基金会旗下的原生云基金会(Cloud Native Computing Foundation), 将Prometheus纳入其下第…
暂无图片
中恒嘉业 ·

关于主从复制的超详细解析(全)

目录前言1. 主从复制1.1 方式2. Mysql的主从复制2.1 一主一从2.1.1 window和linux通讯2.1.2 linux和linux的通讯2.2 双主双从3. Redis的主从复制3.1 哨兵模式3.2 java代码结合前言 主要介绍mysql的主从复制以及redis的主从复制 能由浅入深的明白原理以及如何操作 再者&#xf…
暂无图片
郑州普通话 ·

Android面试心得必备技能储备详解,直接上干货

组件化 1.1 组件化初衷APP版本不断的迭代,新功能的不断增加,业务也会变的越来越复杂,维护成本高。 业务耦合度高,代码越来越臃肿,团队内部多人协作开发困难。 Android项目在编译代码的时候电脑会非常卡,又因为单一工程下代码耦合严重,每修改一处代码后都要重新编译打包测…
暂无图片
郑州普通话 ·

Android 数据存储(二)-SharedPreferences or MMKV

一、SharedPreferences 不同于文件的存储方式,如果要保存的键值集合相对较小,则应使用SharedReferences API。SharedReferences对象指向一个包含键值对的文件,并提供简单的读写方法。 本文从SharedReferences开始逐步引入Preference、MMKV。 …
暂无图片
代理记账 ·

在web应用中发送和接收Jakarta消息

Running the websimplemessage Example To Package and Deploy websimplemessage Using Maven _1、Make sure that GlassFish Server has been started (see Starting and Stopping GlassFish Server). _2、In a terminal window, go to: tut-install/examples/jms/websimp…
暂无图片
cgfy ·

C++学习日记2——函数、封装、对象特性

一、函数 1.1 函数默认参数 1.1.1 简介 在C中&#xff0c;函数的形参列表中的形参是可以有默认值的 1.1.2 语法 返回值类型 函数名 (参数 默认值) {} 1.1.3 代码 #include <iostream> using namespace std;// 函数的默认参数 int func(int a, int b 20, int c 30…
暂无图片
coreui ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
coreui ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
未来博客 ·

视频水印怎么去除?超简单 千万不要错过

小编在知乎看到很多大佬分享的视频去水印的方法&#xff0c;但是感觉都有点太复杂了&#xff0c;今天就来分享一下小编自己私藏的几个针对于视频去水印的软件和网站~建议大家收藏哦~ 1、爱给网-视频去水印小工具&#xff08;免费 在线&#xff09; 推荐点 1、在线操作&#…
暂无图片
未来博客 ·

Mac 安装 tomcat10

Mac 安装 tomcat10 1、下载tomcat tomcat官网&#xff1a;https://tomcat.apache.org/ 点击我下载的tomcat10&#xff1a; 2、下载解压,给bin下的*.sh文件添加可执行权限 3、修改webapps下的ROOT中的index文件查看效果
暂无图片
建站日记 ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
建站日记 ·

NLP聊天机器人原理(seq2seq模型)

一、seq2seq模型 1.概念 seq2seq是一个Encoder-Decoder结构的网络&#xff0c;它的输入是一个序列&#xff0c;输出也是一个序列。Encoder中将一个可变长度的信号序列变为固定长度的向量表达&#xff0c;Decoder将这个固定长度的向量变成可变长度的目标的信号序列。这个结构最…
暂无图片
mfbz ·

惠州实验室建设选址、勘察事项

惠州实验室建设选址、勘察事项&#xff0c;SICOLAB技术员带您从实验室建设启动前思考问题考虑如下&#xff1a;一、不同实验室建设选址要求 1.化学实验室 &#xff08;1&#xff09;清洁安静环境 &#xff08;2&#xff09;远离住宅、生活区 &#xff08;3&#xff09;锅炉房与…
暂无图片
mfbz ·

全渠道会员通-天猫会员通3: 会员运营内容准备

在天猫会员通技术对接开发过程中&#xff0c;为了通知存量会员的通知工作&#xff0c;发挥会员通的优势&#xff0c;品牌需要做好以下事宜&#xff1a; 会员体系暂停公告&#xff1a;因会员通技术升级期间&#xff0c;会员服务将被暂停&#xff0c;店铺tab中会员入口将被下线&…
暂无图片
珊珊日记 ·

C# 执行Javascript脚本

c#教程https://www.xin3721.com/eschool/CSharpxin3721/ 前一阵子使用C#编写SCXML状态机&#xff0c;需要解析EMCScript表达式&#xff0c;使用了Jint库&#xff08;https://github.com/sebastienros/jint/)&#xff0c;当时感觉与C#之间的数据转换不是很方便。这两天有时间又关…
暂无图片
珊珊日记 ·

第九届“图灵杯”NEUQ-ACM程序设计竞赛个人赛

A.大学期末现状 题目描述 作为一名大学生的你&#xff0c;现在又到了期末查成绩的时候&#xff0c;当你的成绩大于等于60时请输出“jige,haoye!”,否则输出"laoshi,caicai,laolao"。 输入描述: 一行&#xff0c;一个整数x代表你的成绩&#xff08;0<x<100&a…