Java实现 LeetCode 718 最长重复子数组(动态规划)
2023-09-14 08:58:02 时间
718. 最长重复子数组
给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。
示例 1:
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
说明:
1 <= len(A), len(B) <= 1000
0 <= A[i], B[i] < 100
class Solution {
public int findLength(int[] A, int[] B) {
int[] dp = new int[B.length];
int max = 0;
for(int j = 0; j < B.length; j++) {
if(A[0] == B[j]) {
dp[j] = 1;
max = 1;
}
}
for(int i = 1; i < A.length; i++) {
for(int j = B.length - 1; j > 0; j--) {
if(A[i] == B[j]) {
dp[j] = dp[j - 1] + 1;
if(dp[j] > max) {
max = dp[j];
}
} else {
dp[j] = 0;
}
}
dp[0] = (A[i] == B[0]) ? 1 : 0;
}
return max;
}
// public int findLength(int[] A, int[] B) {
// if (A == null || B == null) {
// return 0;
// }
// int res = 0;
// int[][] dp = new int[A.length + 1][B.length + 1];
// for (int i = 1; i < dp.length; i++) {
// for (int j = 1; j < dp[i].length; j++) {
// dp[i][j] = A[i - 1] == B[j - 1] ? dp[i - 1][j - 1] + 1 : 0;
// res = Math.max(res, dp[i][j]);
// }
// }
// return res;
// }
}
相关文章
- java stream流操作_java流式处理
- java启动器_JAVA基础:Java 启动器如何查找类
- java编写一个学生类和教师类,Java创建一个学生类[通俗易懂]
- java extends runtimeexception_Java中RuntimeException和Exception的区别
- 编写java判断闰年_Java 判断闰年代码实例
- java jersey使用总结_jersey Java Jersey配置「建议收藏」
- 【说站】java环境变量配置path
- 【说站】java注解的本质探究
- 深入解析java虚拟机:编译概述,即时编译技术
- Java集合面试题_java是什么
- java事务的使用_Java跨库事务
- java 设置400错误_Java项目报400错误的原因与解决方法
- Java中运算符 "|" 和 "||" 以及 "&" 和 "&&" 区别
- Java学习-如何编译适配java版本的jar包
- Java 近期新闻:JDK 20的JEP提升为Targeted状态,亚马逊云科技推出Lambda SnapStart特性
- java中常用的时间处理类TimeUtil详解编程语言
- Java 实现ftp 文件上传、下载和删除详解编程语言
- java sql: PrepareStatement详解编程语言
- java克隆clone(深拷贝/浅拷贝)介绍详解编程语言
- 服务器使用Java进行Linux服务器监控(java监控linux)
- Linux重装Java:给你的操作系统新的灵魂(linux重装java)
- 策略深入解读Redis带来的Java过期策略.(redisjava过期)
- 策略解决Redis Java应用过期策略问题(redisjava过期)
- Linux下快速安装Java开发环境(linux安装java)
- 在Linux上编译Java 实用教程指南(linux上编译java)
- Using Java to Work with MongoDB: A Guide for Developers(java操作mongodb)
- MySQL与Java结合,构建高效多功能缓存系统(MySQL java缓存)
- 深入认识Java面试与MySQL及其思考(java面试mysql)
- Linux测试搭配Java快速实现稳定性验证(linux测试java)
- Java编程从Oracle中读取数据(java读取oracle)
- Java中Oracle使用实践(java中oracle题)
- 并发Redis锁保障Java并发性(redis锁实现java)
- java父类和子类初始化顺序的深入理解
- java随机生成字符串(字符随机生成类生成随机字符组合)
- 谈谈Java中this的使用方法
- java使用poi读取ppt文件和poi读取excel、word示例