blog
blog copied to clipboard
[LeetCode] sliding window algorithm
学习过程记录
第一次接触滑动窗口算法是在 TCP 协议中, 超时重发机制. 用的就是滑动窗口算法, 用于保证丢失的数据能够重传.
模板
var slidingWindow = function(s, t) {
let l = 0
let r = 0
const sz = s.length
while(r<sz) { // 是否需要扩张窗口
const currR = s[r]
r++
console.log(s.slice(l,r)) // debug here
while(isShrink()) { // 是否需要缩小窗口
const currL = s[l]
l++
}
}
};
要点
-
left 和 right 两个指针
-
外层 while 代表是否需要扩张窗口, 当右边指针到边之前都是 right++
-
里层 while 代表是否需要缩小窗口, 当窗口内的数据不符合要求 left++
-
当窗口内的数据符合要求的时候, 记录下来窗口长度, 并输出记录过的最短长度.
来一题: 76. Minimum Window Substring
思路
按照上面的模板写出来并不难, 但这题的优化策略如下
-
用 start 和 end 参数分别记录 最短窗口位置的起点和窗口长度. 只有当需要更新最短窗口的时候才更新他们. 这样可以避免多次截取字符串来拿到窗口内的字符串.
-
如何高效的判断窗口内的字符串是否符合要求? 第一思路自然是for循环某个字符串, 查看他的每一个字符是否在另一个里面, 但这样是
O(n^2)
了, 我们可以将 目标字符串 t 转化成map, 然后滑动窗口每次有新的字符串进入,map[key]--
, 如果窗口收缩的时候,map[key]++
, 这样时时刻刻更新map, 最后我们只需要校验map中的每个值是否大于0即可高效的校验当前窗口内的字符串是否符合要求.
答案
var minWindow = function(s, t) {
let l=0
let r=0
let start = 0
let len = Infinity
const t_map = {}
for(let letter of t) {
if (t_map[letter]) {
t_map[letter]++
}else{
t_map[letter] = 1
}
}
function isInclude(a) {
for(let key in t_map) {
if (t_map[key]>0) {
return false
}
}
return true
}
while(r<s.length) {
// open
if (t_map.hasOwnProperty(s[r])) {
t_map[s[r]]--
}
r++
while(isInclude()) {
// shirly
if (len>r-l) {
start = l
len = r-l
}
if (t_map.hasOwnProperty(s[l])) {
t_map[s[l]]++
}
l++
}
}
return len == Infinity ? '' : s.slice(start, start+len)
};
再来一题: 567. Permutation in String
思路
-
基本上和上面的是一模一样, 基本抛弃原先的多次遍历循环的解法了, 太低效了.
-
维护一个滑动的窗口, 这个窗口由 l, r 作为左节点和右节点进行维护.
-
针对
s1
, 由于它是可以任意排序的, 因此对它生成一个map用于记录各个字母出现的次数. -
滑动窗口什么时候扩张? 当r节点小于s2字符长度,
-
滑动窗口什么时候收缩? 当窗口长度小于 s1.length就收缩
-
滑动窗口扩张的时候, 拿到推入的那个字符串, 如果存在于 map, 则 map[key]--
-
滑动窗口收缩的时候, 拿到推出的那个字符串, 如果存在于 map, 则 map[key]++
-
收缩的同时, 校验map是否每个字符串都为 0, 如果为0, 则直接return true.
-
在最后return false, 即找不到符合条件的字符串.
答案
var checkInclusion = function(s1, s2,l=0,r=0) {
const s1_map = s1.split('').reduce((m,l)=>{
!m[l] && (m[l] = 0)
m[l]++
return m
},{})
while(r<s2.length) {
// need to open
if (s1_map.hasOwnProperty(s2[r])) {
s1_map[s2[r]]--
}
r++
while(r-l>=s1.length) {
// console.log(s1_map)
if (Object.values(s1_map).every(e=>e==0)) {
return true
}
if (s1_map.hasOwnProperty(s2[l])) {
s1_map[s2[l]]++
}
// need to shrink
l++
}
}
return false
};
再来一题: 438. Find All Anagrams in a String
思路
和上面的基本一致, 维护一个滑动窗口, 有符合条件直接把当前坐标推入 res 数组中.
答案
var findAnagrams = function (s, p) {
const map = p.split('').reduce((map, e) => {
if (map[e]) {
map[e]++
} else {
map[e] = 1
}
return map
}, {})
const res = []
let l = 0
let r = 0
while (r < s.length) {
// open
if (map.hasOwnProperty(s[r])) {
map[s[r]]--
}
r++
while (r - l >= p.length) {
// reduce
if (Object.values(map).every(val=>val==0)) {
res.push(l)
}
if (map.hasOwnProperty(s[l])) {
map[s[l]]++
}
l++
}
}
return res
};
3. Longest Substring Without Repeating Characters
思路
同样是滑动窗口算法, 不过位置需要调转一下.
答案
/**
* @param {string} s
* @return {number}
*/
var lengthOfLongestSubstring = function(s,max=0,l=0,r=0,map={}) {
while(r<s.length) {
if (map[s[r]]) {
map[s[r]]++
}else{
map[s[r]] = 1
}
while(map[s[r]] > 1) {
map[s[l]]--
l++
}
r++
max = Math.max(r-l,max)
}
return max
};
424. Longest Repeating Character Replacement
思路
这题我也不知道为什么对了, 反正框架写出来修修改改就是对的.
答案
/**
* @param {string} s
* @param {number} k
* @return {number}
*/
var characterReplacement = function(s, k) {
const map = {}
for(let le of s){
map[le] = 0
}
let l = 0;
let r = 0;
let res = 0
function isRepeatStringMoreThanK(map) {
const arr = Object.values(map)
arr.sort((a,b)=>b-a)
return arr.slice(1).reduce((t,e)=>t+e,0) > k
}
while(r<s.length) { // grow
map[s[r]]++
r++
while(isRepeatStringMoreThanK(map)) { //shrink
map[s[l]]--
l++
}
res = Math.max(res, r-l)
}
return res
};