20200701
题目(难度:中等):
给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
示例
输入:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
输出: 3
解释:
长度最长的公共子数组是 [3, 2, 1]。
说明
1 1 <= len(A), len(B) <= 10000 <= A[i], B[i] < 100
抛砖引玉
首先我的思路是两层循环分别以数组 A 中的元素做起点如果在数组 B 中找到相同的元素(假设 A 中索引为 i，B 中索引为 j)，则比较 A[i]与 B[j]是否相同 声明个中间变量记录，如果相同+1，不然重置为 0 如果不同继续向后查找相同的元素
上面逻辑实现后会发现：
var findLength = function (A, B) {
let _result
= 0
if (!A.length
|| !B.length
) return _result
for (let i
= 0; i
< A.length
; i
++) {
let index
= i
,
middle
= 0,
j
= 0
while (j
< B.length
) {
if (A[index
] === B[j
]) {
middle
++
index
++
_result
= Math
.max(_result
, middle
)
} else {
index
= i
middle
= 0
}
j
++
}
}
return _result
}
当 B 中有多个数据与 A 中相同，即一个 A 的起点，可以再 B 中出现多个 A[i]=B[j]，此时 i 是向后继续迭代还是重置
i 重置，则会使 A 之后的元素只能计算到首次与 B 相同的连续长度；i 不重置，则 B 中当前 j 之后的数据可能与 index 之前的数据匹配长度才最长(及 j 之后的数据第一个与 A 相同的索引在 index 之前)
惊不惊喜，意不意外，上来就是一个错误的解法
皮归皮，上面的思路有问题的是：
声明个中间变量记录，如果相同+1，不然重置为 0 如果不同继续向后查找相同的元素
那重新换下这部分思路尝试下：
固定 A 元素在 B 的固定起点查找，B 元素在 A 的固定起点查找更换记录值的方式
固定 A 元素在 B 的固定起点查找，B 元素在 A 的固定起点查找
分别以 A 中每个元素为起点在 B 的固定起点查找相同连续数量(上面的逻辑用到喽)
注意当 n 小于 m 时,B 可能会越界，则限制长度为 n随着 A 的起点向后移动，查询的范围也会缩小(n-i)场景与上面 i 重置一致，优化了搜索范围 分别以 B 中每个元素为起点在 A 的固定起点查找相同连续数量
逻辑一直，主要解决上面 index 不重置带来的问题
var findLength = function (A, B) {
let n
= A.length
,
m
= B.length
,
_result
= 0
if (!n
|| !m
) return _result
for (let i
= 0; i
< n
; i
++) {
let end
= Math
.min(m
, n
- i
)
let maxlen
= maxLength(A, B, i
, 0, end
)
_result
= Math
.max(_result
, maxlen
)
}
for (let j
= 0; j
< m
; j
++) {
let end
= Math
.min(n
, m
- j
)
let maxlen
= maxLength(A, B, 0, j
, end
)
_result
= Math
.max(_result
, maxlen
)
}
function maxLength(A, B, a
, b
, len
) {
let num
= 0,
middle
= 0
for (let i
= 0; i
< len
; i
++) {
if (A[a
+ i
] == B[b
+ i
]) {
middle
++
num
= Math
.max(num
, middle
)
} else {
middle
= 0
}
}
return num
}
return _result
}
更换记录值的方式
使用 map 的形式记录在循环 B 时，为了避免多次起点的问题：
假设 B 的某一个元素已经知道上一个元素的连续相等数(存放在 map->j 中)当前这个元素继续连续，则在 map->j 基础上+1，存到 map 中：map->j+1 value:(map->j)value +1这个追溯到 j = 0, value 也为 0(倒序循环)一次循环生产一次 map 对应的 key-value，_result 取多次循环的最大值
var findLength = function (A, B) {
let n
= A.length
,
m
= B.length
,
_result
= 0,
map
= new Map()
if (!n
|| !m
) return _result
for (let i
= 0; i
< n
; i
++) {
for (let j
= m
- 1; j
>= 0; j
--) {
let prev
= map
.get(j
) || 0
if (A[i
] === B[j
]) {
map
.set(j
+ 1, prev
+ 1)
} else {
map
.set(j
+ 1, 0)
}
_result
= Math
.max(_result
, map
.get(j
+ 1))
}
}
return _result
}
官方答案
动态规划
声明一个 n+1 长的数组，每个子集长 m+1，其中 f[0][0]为初始值 0，用于推算如果 A 中一个元素(索引 i)与 B 中一个元素相同(索引 j),f[i][j]默认填充 1当 A 和 B 循环到下一个元素时 i+1,与 j+1 也相同那 f[i+1][j+1]则为 f[i][j]+1,这样会记录 A 任意指针与 B 任意指针时连续子集数，取其最大值返回
var findLength = function (A, B) {
const m
= A.length
const n
= B.length
const dp
= new Array(m
+ 1)
for (let i
= 0; i
<= m
; i
++) {
dp
[i
] = new Array(n
+ 1).fill(0)
}
let ans
= 0
for (let i
= 1; i
<= m
; i
++) {
for (let j
= 1; j
<= n
; j
++) {
if (A[i
- 1] == B[j
- 1]) {
dp
[i
][j
] = dp
[i
- 1][j
- 1] + 1
}
ans
= Math
.max(dp
[i
][j
], ans
)
}
}
return ans
}
博客: 小书童博客(http://gaowenju.com)
公号: 坑人的小书童
