LC 718. Maximum Length of Repeated Subarray
2024-09-05 07:30:28
Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.
Example 1:
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation:
The repeated subarray with maximum length is [3, 2, 1].
Note:
- 1 <= len(A), len(B) <= 1000
- 0 <= A[i], B[i] < 100
Runtime: 78 ms, faster than 40.98% of Java online submissions for Maximum Length of Repeated Subarray.
class Solution {
public int findLength(int[] A, int[] B) {
int[][] dp = new int[A.length+1][B.length+1];
int ret = 0;
for(int i=1; i<dp.length; i++){
for(int j=1; j<dp[0].length; j++){
if(A[i-1] == B[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
ret = Math.max(ret, dp[i][j]);
}
}
}
return ret;
}
}
a better solution
Runtime: 26 ms, faster than 99.59% of Java online submissions for Maximum Length of Repeated Subarray.
有两个关键点，
第一个是内层循环从后往前遍历，如果从前往后遍历就是错误的，因为我们每一次更新dp的时候是dp[j+1] = dp[j] + 1，所以在更新j+1的时候要用到j的信息，而这个j应该是之前的j，也就是上一行的j，可以参考上面一个解法中矩阵的上一行。
第二个是如果没有匹配到，应该把j+1变成０，否则会产生错误的计数。
class Solution {
public int findLength(int[] A, int[] B) {
int[] dp = new int[A.length+1];
int max = 0;
for(int i=0; i<A.length; i++) {
for(int j=B.length-1; j>=0; j--) {
if (A[i] == B[j]) {
dp[j+1] = dp[j] + 1;
if (max < dp[j+1]) {
max = dp[j+1];
}
} else {
dp[j+1] = 0;
}
}
}
return max;
}
}
最新文章
- Angularjs+node+Mysql实现地图上的多点标注
- 关于jQuery新的事件绑定机制on()的使用技巧
- mysql sort 性能优化
- MVC去掉传参时的验证：从客户端中检测到有潜在危险的Request.QueryString值
- html 头部正常用法
- Using Nini .NET Configuration Library
- 解决比较Oracle中CLOB字段问题
- [Android]Eclipse的使用
- laravel会话驱动扩展—连接自定义会话管理系统
- Effective C++ ——模板和泛型编程
- Dynamics CRM 2011/2013 section的隐藏
- stl源码剖析 详细学习笔记 hashtable
- [转帖] Kubernetes如何使用ReplicationController、Replica Set、Deployment管理Pod ----文章很好 但是还没具体操作实践 也还没记住.
- .NetCore 中扩展ExceptionLess 实现链式方法添加操作日志
- 【神经网络】神经网络结构在命名实体识别（NER）中的应用
- java-事务-案例
- 微软雅黑的Unicode码和英文名
- luogu P1162 填涂颜色
- DropDownList控件的使用方法
- Tomcat中容器是什么以及容器与容器之间的数量关系。