TOC
最近好久没写文章了，大量的时间都花在了刷LeetCode上，最近开始重拾博客。
最短摘要
假设我们拥有一个分词数组W = [w1,w2,w3,w4,w5…] 并拥有一个query数组 Q= [q1,q2,q3…], 求w的中一个sub array, sw 内部包含我们所有的query子项，并要求是所有满足条件的sub array中最短的一个。
举个例子 W = [‘a’, ‘b’, ‘c’, ‘1’, ’d’, ‘e’, ‘2’, ‘f’, ‘g’, ‘1’, ‘h’, ‘2’] Q = [‘2’,‘1’] 其最短摘要为 [‘1’,‘h’,‘2’] = length(3)
这个问题是在《编程之美》中看到的，书中有描述解法，但是不是特别完整， 我这里做了具体实现并进行一下简单解释
解法1 暴力
第一种解法就是从w1开始搜索W数组，一直到包含所有我们的关键词为止，我们记录下他的最短摘要长度，然后从w2开始，重新开始搜索，反复重复，直到找出最短摘要的长度为止，复杂度为(N ^ 2 * m)
解法2 建立前后关联
[‘a’, ‘b’, ‘c’, ‘1’, ’d’, ‘e’, ‘2’, ‘f’, ‘g’, ‘1’, ‘h’, ‘2’]
第二种方法的核心在于建立起搜索之间的关联，
- 我们假设中w1也就是’a’开始搜索，一直到满足我们的摘要结束，完成我们第一次的搜索 这时候的结果应该为 [‘1’, ’d’, ‘e’, ‘2’] = Length(4)
- 这时候我们进行第二次搜索 把搜索位置变成上一次摘要起始的索引+1开始，也就是 ’d’ 的位置 这里的关键在于我们利用了上一次的搜索结果
- 如此反复
代码的实现有几点关键，第一是要记录我们摘要的起始位置，方便下次循环作为起始标识，第二是可以利用一个Map来存放当前从start到end这个区间内部到底包含了多少关键词，通过空间换时间
下面是具体代码
const minAbs = (words, query) => {
let n = words.length
let start = 0
let end = 0
let firstFoudIndex = -1
let minStart = 0
let minEnd = 0
let minAbsRange = Infinity
// 建立查询是否是目标关键词的Map O(1)查询时间 空间换时间
let queryMap = new Map()
query.forEach((element) => {
queryMap.set(element, true)
})
let containMap = new Map()
while (true) {
if (end >= n) break
// 检查END指针是否指向一个存在的关键词
// 如果属于关键词，那么放入start - end 区间的关键词列表Map中
// 如果是start - end 区间内的第一个关键词 记录其索引
if (queryMap.has(words[end])) {
containMap.set([words[end]], true)
if (firstFoudIndex === -1) firstFoudIndex = end
}
// 区间内并未包含所有关键词 继续向下搜索
if (containMap.size < queryMap.size) {
end++
} else if (containMap.size === queryMap.size) {
// 包含所有关键词 检测是否是更短的区间长度
if (end - firstFoudIndex < minAbsRange) {
minStart = firstFoudIndex
minEnd = end
minAbsRange = end - firstFoudIndex + 1
}
// 重置所有属性
// 下次搜索将会从这次搜索的第一个关键词所在的位置+1的地方上继续搜索
start = firstFoudIndex + 1
end = firstFoudIndex + 1
firstFoudIndex = -1
containMap.clear()
}
}
console.log(minStart, minEnd, minAbsRange)
return minAbsRange
}
console.log(minAbs(['a', 'b', 'c', '1', 'd', 'e', '2', 'f', 'g', '1', 'h', '2'], ['2', '1']))
总结
在构建最优算法的过程很难直接找到一个最优解，所以不妨从一个不够好的暴力算法开始，不断优化，提升，提炼问题本质，方能找到更好的算法替代，如此反复，才是算法编程之真谛。