718. 最长重复子数组
718. 最长重复子数组
- 原题链接:
- 完成情况:
- 题解:
- 方法一:动态规划
- 方法二:滑动窗口
- 方法三:二分查找 + 哈希
原题链接:
718. 最长重复子数组
https://leetcode.cn/problems/maximum-length-of-repeated-subarray/description/
完成情况:

题解:
方法一:动态规划

package 西湖算法题解___中等题;public class __718最长重复子数组__动态规划 {//子数组的话,默认是连续的。public int findLength(int[] nums1, int[] nums2) {/*给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。当然了,肯定是要求顺序,而非连续。那么必然就需要用到动态数组,采取累积的形式*/int n = nums1.length,m = nums2.length;int dp_findLength [][] = new int[n+1][m+1];int res = 0;for (int i=n-1;i>=0;i--){for (int j=m-1;j>=0;j--){dp_findLength[i][j] = (nums1[i] == nums2[j] ? dp_findLength[i+1][j+1] + 1:0);res = Math.max(res,dp_findLength[i][j]);}}return res;}
}
方法二:滑动窗口


package 西湖算法题解___中等题;public class __718最长重复子数组__滑动窗口 {public int findLength(int[] nums1, int[] nums2) {int n = nums1.length,m = nums2.length;int res = 0;for (int i=0;i<n;i++){int len = Math.min(m,n-i);int maxLen = maxLength(nums1,nums2,i,0,len);res = Math.max(res,maxLen);}for (int i=0;i<m;i++){int len = Math.min(n,m-i);int maxLen = maxLength(nums1,nums2,0,i,len);res = Math.max(res,maxLen);}return res;}private int maxLength(int[] nums1, int[] nums2, int addA, int addB, int len) {int res = 0,k=0;for (int i=0;i<len;i++){if (nums1[addA+i] == nums2[addB+i]){k++;}else {k=0;}res = Math.max(res,k);}return res;}
}
方法三:二分查找 + 哈希

package 西湖算法题解___中等题;import java.util.HashSet;
import java.util.Set;public class __718最长重复子数组__二分查找_哈希表 {int mod = 1000000009;int base = 113;public int findLength(int[] nums1, int[] nums2) {int left = 1,right = Math.min(nums1.length,nums2.length)+1;while (left < right){int mid = (left + right) >> 1;if (myCheck(nums1,nums2,mid)){left = mid +1;}else {right = mid;}}return left - 1;}private boolean myCheck(int[] A, int[] B, int len) {long hashA = 0;for (int i=0;i<len;i++){hashA = (hashA * base + A[i]) % mod;}Set<Long> bucketA = new HashSet<Long>();bucketA.add(hashA);long mult = qPow(base,len - 1);for (int i = len;i < A.length;i++){hashA = ((hashA - A[i - len] * mult % mod + mod) % mod * base + A[i]) % mod;bucketA.add(hashA);}long hashB = 0;for (int i=0;i<len;i++){hashB = (hashB * base +B[i])%mod;}if (bucketA.contains(hashB)){return true;}for (int i=len;i<B.length;i++){hashB = ((hashB - B[i - len] * mult % mod + mod) % mod * base + B[i]) % mod;if (bucketA.contains(hashB)){return true;}}return false;}/*** 使用快速幂计算x^n % mod 的值* @param x* @param n* @return*/private long qPow(long x, long n) {long res = 1L;while (n != 0){if ((n&1) != 0){res = res * x % mod;}x = x*x % mod;n >>= 1;}return res;}
}相关文章:
718. 最长重复子数组
718. 最长重复子数组 原题链接:完成情况:题解:方法一:动态规划方法二:滑动窗口方法三:二分查找 哈希 原题链接: 718. 最长重复子数组 https://leetcode.cn/problems/maximum-length-of-repe…...
Mysql join加多条件与where的区别
最近在项目中遇到一个问题,感觉有点意思,在解决问题及查阅了相关资料后,打算写篇文章给朋友们分享一下。 问题现象: 问题是很常见的空指针问题,后端查询数据库数据,遍历进行相关业务处理时报空指针。通过…...
div滚动条自动滚动到底部
<div id"center"></div>// 滚动条到最底部scrollToBottom(){var box document.getElementById(center);this.$nextTick(() > {box.scrollTop box.scrollHeight})},...
【深度学习】实验02 鸢尾花数据集分析
文章目录 鸢尾花数据集分析决策树K-means 鸢尾花数据集分析 决策树 # 导入机器学习相关库 from sklearn import datasets from sklearn import treeimport matplotlib.pyplot as plt import numpy as np# Iris数据集是常用的分类实验数据集, # 由Fisher, 1936收集…...
AI大模型潮水中,医疗数字化加速「求解」
蝴蝶挥动翅膀,医疗行业每个角落开始连锁反应,曾经被忽视的问题也愈发明显。但与之对应的是,对数字化和AI大模型的价值认可,在中国医疗赛道也正在加速来临。 作者|斗斗 编辑|皮爷 出品|产业家 重庆市某地方人民医院…...
【安卓】自定义View实现画板涂鸦等功能
一、实现效果 二、代码 1、MainActivity.class package com.lsl.mydrawingboarddemo;import androidx.appcompat.app.AppCompatActivity; import androidx.core.content.ContextCompat;import android.os.Bundle; import android.os.Handler; import android.view.View; impo…...
面试题. 搜索旋转数组
搜索旋转数组。给定一个排序后的数组,包含n个整数,但这个数组已被旋转过很多次了,次数不详。请编写代码找出数组中的某个元素,假设数组元素原先是按升序排列的。若有多个相同元素,返回索引值最小的一个。 示例1: 输入…...
前端需要理解的数据治理与异常监控知识
1 数据治理 前端数据治理的重要指标是准确性和数据,一个数据对象包括数据值和其他元数据。 2 数据上报方式 2.1 Image 通过将采集的数据拼接在图片请求的后面,向服务端请求一个 1*1 px 大小的图片(gif)实现的,设置…...
ip_vs 原理解析 (四)hook 后的开始 一
文章目录 ip_vs hook 后NF_INET_LOCAL_IN 本章重点: k8s 如何利用 ip_vs 实现源 IP 会话亲和性。 ip_vs hook 后 NF_INET_LOCAL_IN 根据优先级依次是 ip_vs_reply4,ip_vs_remote_request4 ip_vs_reply4| -- ip_vs_out| -- skb_to_full_sk(skb…...
【论文解读】基于图的自监督学习联合嵌入预测架构
一、简要介绍 本文演示了一种学习高度语义的图像表示的方法,而不依赖于手工制作的数据增强。论文介绍了基于图像的联合嵌入预测架构(I-JEPA),这是一种用于从图像中进行自监督学习的非生成性方法。I-JEPA背后的idea很简单ÿ…...
C++ 容器
string 1. 构造 string s1(); // 1 string s2("hello"); // hello string s3(3, k); // kkk string s4("hellohello", 2, 4); // lloh2. 赋值 string s1 "hellohello"; // hellohello string s2.assign(s1); // he…...
【PHP】PHP文件操作详解
PHP是一种广泛使用的服务器端脚本语言,用于开发Web应用程序。在PHP中,文件操作是一项重要的功能,包括文件的读取、写入、删除和其他操作。本文将详细介绍PHP文件操作的各个方面,并通过示例代码进行说明。 一、文件读取 要读取一…...
硬核旗舰南卡OE CC开放式耳机发布,重新定义百元开放式耳机新标杆!
随着现在健康意识的不断提高,人们对于日常用品的要求越来越高,在耳机市场中,健康因素也逐渐成为消费者所考虑的因素之一,入耳式耳机因为会引发中耳炎、耳膜炎等疾病,正在逐渐被开放式蓝牙耳机所取代,南卡…...
785. 判断二分图
785. 判断二分图 原题链接:完成情况:解题思路:参考代码: 原题链接: 785. 判断二分图 https://leetcode.cn/problems/is-graph-bipartite/description/ 完成情况: 解题思路: 题目解释&#x…...
限时 180 天,微软为 RHEL 9 和 Ubuntu 22.04 推出 SQL Server 2022 预览评估版
导读近日消息,微软公司今天发布新闻稿,宣布面向 Red Hat Enterprise Linux(RHEL)9 和 Ubuntu 22.04 两大发行版,以预览模式推出 SQL Server 2022 评估版。 近日消息,微软公司今天发布新闻稿,宣布…...
一款ccm的功率因素校正控制器ncp1654
产品概述: NCP1654是用于连续传导模式的控制器(CCM)功率因数校正升压预转换器。它控制固定频率模式下的电源开关导通时间(PWM)并且取决于瞬时线圈电流。 该电路封装在SO8封装中,最大限度地减少了外部组件&a…...
4.若依框架上传文件
1.服务端代码-控制器 /*** 上传文件*/PostMapping("/upload")Operation(summary "上传")public AjaxResult uploadFile(MultipartFile file) throws Exception {try {// 上传文件路径String filePath RuoYiConfig.getUploadPath();// 上传并返回新文件名…...
Property ‘sqlSessionFactory‘ or ‘sqlSessionTemplate‘ are required
项目场景: 最近因为公司业务需要在搭一个新架构,用的springboot3和jdk17,在整合mybatis多数据源的时候报错 (引用的mybatisplus 和 mybatisplusjion的是最新的包-2023-08-26) Error creating bean with name ‘XXXServiceImpl’:…...
idea的debug断点的使用
添加断点(目前不知道如何添加断点,就给AutoConfigurationImportSelector的每个方法都加上断点): 然后将StockApplication启动类以debug方式运行,然后程序就会停在119行 点击上边的step over让程序往下运行一行&#x…...
【UE】蓝图通信——事件分发器
目标 比如我现在希望点击控件蓝图A中的按钮后,蓝图B能够马上做出响应 实现步骤 1. 这里控件蓝图A叫“UI_按钮”,我在该蓝图中创建了一个名为“btnIsClicked”的事件分发器 当按钮被点击时,就会调用“btnIsClicked” 2. 蓝图B这里叫做“BP_…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Caliper 负载(Workload)详细解析
Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...
PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...
Python 训练营打卡 Day 47
注意力热力图可视化 在day 46代码的基础上,对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...
