leetcode 718.最长重复子数组

原题

718.最长重复子数组
2020年7月1日 每日一题
在这里插入图片描述

题解

方法一

暴力法。

/*暴力法
@v7fgg
执行用时:2265 ms, 在所有 Java 提交中击败了5.00%的用户
内存消耗:39.3 MB, 在所有 Java 提交中击败了100.00%的用户
2020年7月1日 8:03
*/
class Solution {
    public int findLength(int[] A, int[] B) {
        int ans=0;
        for(int i=0;i<A.length;i++){
            for(int j=0;j<B.length;j++){
                if(A[i]==B[j]){
                    int ansT=0;
                    int i1=i;
                    int j1=j;
                    while(i1<A.length&&j1<B.length&&A[i1]==B[j1]){
                        ansT++;
                        i1++;
                        j1++;
                    }
                    ans=Math.max(ans,ansT);
                }
            }
        }
        return ans;
    }
}

方法二 动态规划

建立一个二维数组ans(行列数分别为A的长度加1和B的长度加1),其中ans[i][j]的含义为从之前的最早可能位置到A的i位置和B的j位置的最长的相同部分子序列。当移动到ans[i+1][j+1]的时候,有
ans[i+1][j+1]=A[i]==B[j]?ans[i][j]+1:0
通过遍历所有可能的i和j的组合从小到大,二层循环即可算出整个矩阵,取其中最大值。
本思路java代码示例:

/*dp
@v7fgg
执行用时:73 ms, 在所有 Java 提交中击败了24.50%的用户
内存消耗:48.8 MB, 在所有 Java 提交中击败了100.00%的用户
2020年7月1日 8:34
*/
class Solution {
    public int findLength(int[] A, int[] B) {
        int daan=0;
        int ans[][]=new int[A.length+1][B.length+1];
        for(int i=1;i<=A.length;i++){
            for(int j=1;j<=B.length;j++){
                ans[i][j]=A[i-1]==B[j-1]?ans[i-1][j-1]+1:0;
                daan=Math.max(daan,ans[i][j]);
            }
        }
        return daan;
    }
}
/*sliding window
@v7fgg
执行用时:55 ms, 在所有 Java 提交中击败了67.44%的用户
内存消耗:39.4 MB, 在所有 Java 提交中击败了100.00%的用户
2020年7月1日 10:15
*/
class Solution {
    public int findLength(int[] A, int[] B) {
        int ans=0;        
        for(int i=0;i<A.length;i++){
            int ansT=0;
            for(int j=0;j<Math.min(B.length,A.length-i);j++){
                if(A[i+j]==B[j]){ansT++;}
                else{ansT=0;}
                ans=Math.max(ans,ansT);
            }
        }
        for(int i=0;i<B.length;i++){
            int ansT=0;
            for(int j=0;j<Math.min(A.length,B.length-i);j++){
                if(B[i+j]==A[j]){ansT++;}
                else{ansT=0;}
                ans=Math.max(ans,ansT);
            }
        }
        return ans;
    }
}
/*sliding window simplifeid version
@v7fgg
执行用时:61 ms, 在所有 Java 提交中击败了46.43%的用户
内存消耗:39.5 MB, 在所有 Java 提交中击败了100.00%的用户
2020年7月1日 12:16
*/
class Solution {
    public int findLength(int[] A, int[] B) {
        int ans=0;
        int ansT=0;
        //i表示的滑动的数字范围
        for(int i=0;i<=A.length+B.length-2;i++){
            //以下j先以A的坐标为准
            for(int j=Math.max(0,i+1-B.length);j<=Math.min(A.length-1,i);j++){
                if(A[j]==B[B.length-1-i+j]){ansT++;}
                else{ansT=0;}
                ans=Math.max(ans,ansT);
            }
            ansT=0;//注意初始化
        }
        return ans;
    }
}

热门文章

暂无图片
编程学习 ·

Python:% 和 .format() 的使用

目录基本的格式化值转换填充和对齐字符串截断长串结合截断与填充数字填充数字带符号的数字有名字的占位符Getitem 和 Getattr日期时间参数化的格式自定义对象多年来,Python 具有出色的字符串格式化程序,但是有关它们的文档在理论和技术上都太过严格了。通过此站点,我们尝试通…
暂无图片
编程学习 ·

搭建一个完整的微服务系统(四):微服务的公共依赖

任何一个系统中,都有一个或多个基础项目,可生成jar包给所有服务依赖。在本示例(工程basejar)中,我给大家找了一些常用的进行说明,这些内容和业务无关,大家可以直接使用。 幂等相关这部分包括:AutoIdempotent.java、AutoIdempotentInterceptor.java、TokenService.java三个…
暂无图片
编程学习 ·

Qt QTreeWidget的级联选中

在使用QTreeWidget显示文件树时,需要对树的节点做一些功能的限制:勾选某一节点时,该节点的子项自动全部选中 子项部分勾选时,父节点状态为部分勾选 子项全部勾选时,父节点自动设置勾选首先,查看了Qt文档,发现竟然没有提供这个功能,所以自己写了一个简单的例子。 先看效…
暂无图片
编程学习 ·

单例和枚举原理

单例和枚举原理 枚举 简单介绍枚举类能够统一管理一些全局的变量,封装对于他们的逻辑与方法。还能和switch-case结合,简化大量的if-else,让代码更加优雅。直接Demo public enum Week {//本文的枚举类变量,枚举类实例,name属性指的就是MONDAY//这类的变量MONDAY(0,"星…
暂无图片
编程学习 ·

2020年陆月份生活随笔

今天是建党99年,党的生日,不是党员,要按照党员的标准严格要求自己。昨天看了一下月跑量,计划着跑一个总里程171.99,计算了一下今天跑一个8.48就可以,今天跑步特意戴上耳机听跑步软件播报公里数,到了八公里就放满了速度,跑着距离感觉快到了,心想过了这个路口再看手机,…
暂无图片
编程学习 ·

如何将PDF转换成jpg图片?教你2种免费方法

如何将PDF格式的文件转换成JPG图片?有时为了方便需要将PDF转成图片来使用,直接截图不仅耗费时间,而且像素很不清晰,有没有其他方便快捷转出高清图片的方法呢? 方法1: 这个方法最方便就在于不用下载安装软件,甚至都不需要注册登录,只要有网络,手机和电脑都能快速操作完…
暂无图片
编程学习 ·

unordered_map/unorderd_set使用与哈希介绍

在C++98中,STL提供了底层为红黑树结构的一系列关联式容器,在查询时效率可达到 O(logN),即最差情况下 需要比较红黑树的高度次,当树中的节点非常多时,查询效率也不理想。最好的查询是,进行很少的比较次 数就能够将元素找到,因此在C++11中,STL又提供了4个unordered系列的…
暂无图片
编程学习 ·

centos7.5通过yum安装docker

1.docker安装 1.安装docker yum install -y yum-utils device-mapper-persistent-data lvm2 yum-utils:yum管理工具包 device-mapper-persistent-data:设备映射包 lvm2:lvm包 2.安装docker源 yum-config-manager --add-repo http://mirrors.aliyun.com/docker-ce/linux/cent…
暂无图片
编程学习 ·

SpringBoot问题集锦

问题一: SpringBoot应用部署在外置Tomcat中没有启动,无任何反应 解决办法:启动类继承SpringBootServletInitializer并实现configure方法;@SpringBootApplication public class PaysApplication extends SpringBootServletInitializer {@Overrideprotected SpringApplicatio…
暂无图片
编程学习 ·

Go map的增删改查及遍历

map的增删改查map 增加和更新map["key"] = value 如果 key 还没有,就是增加,如果 key 存在就是修改cities := make(map[string]string) cities["no1"] = "北京" cities["no2"] = "天津" cities["no3"] = "…
暂无图片
编程学习 ·

直播带货系统开发机遇与挑战并存

如今,直播带货正逐渐取代以往传统的营销方式,各大电商也因此纷纷踏入直播带货系统开发热门,开发出多个功能为一体的直播带货系统。2020年,面临着直播带货的空前盛况,不仅是直播带货系统开发的机遇,同时也是一个挑战。所谓的直播带货,顾名思义,就是商家以及直播通过直播…
暂无图片
编程学习 ·

「Python 秘籍」在正则式中使用 Unicode

关注RPA请访问网站: www.i-search.com.cn 学Python,用RPA,欢迎下载使用 www.i-search.com.cn/index.html?from=line1 问题 你正在使用正则表达式处理文本,但是关注的是 Unicode 字符处理。 解决方案 默认情况下 re 模块已经对一些 Unicode 字符类有了基本的支持。 比如, \d…
暂无图片
编程学习 ·

qtdesigner-请假(仅仅是尝试使用软件)

下面是我给他们起的名字。现在修改完名字之后,导出成MainWindow.ui文件打开anaconda的shell现在就产生了MainWindow.py,打开它 打开pycharm,创建一个新的名为askForLeave的project,把MainWindow.py移进来。 创建Leave.py作为主程序(起名废) 现在给MainWindow.py配置环境写…
暂无图片
编程学习 ·

Leetcode 349. 两个数组的交集 C++

Leetcode 349. 两个数组的交集 题目 给定两个数组,编写一个函数来计算它们的交集。 测试样例 示例 1: 输入:nums1 = [1,2,2,1], nums2 = [2,2] 输出:[2]示例 2: 输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4] 输出:[9,4]说明:输出结果中的每个元素一定是唯一的。 我们可以…
暂无图片
编程学习 ·

通过小项目学习23种设计模式(四)

通过读取文件导入数据库功能学习23种设计模式 第一次重构代码 目前代码写的很随性,导致以后业务增加时拓展起来繁杂,所以我们将已有逻辑进行第一重构: 抽取公共的行为生成接口 package com.xiaoma.fileimport.common;/*** 任务主执行类* 使用工厂模式,首先将任务共同行为抽象出…
暂无图片
编程学习 ·

Linux下core dump学习

参考链接 在linux下开发时,如果程序突然崩溃了,也没有任何日志。这时可以查看core文件。从core文件中分析原因,通过gdb看出程序挂在哪里,分析前后的变量,找出问题的原因。 1 查看linux下core dump是否开启 在linux上coredump默认是关闭的,可以通过ulimit -c查看,如果输出…