[LeetCode] sliding window algorithm

[plh97]

学习过程记录

第一次接触滑动窗口算法是在 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++
        }
    }
};

要点

0. left 和 right 两个指针

1. 外层 while 代表是否需要扩张窗口, 当右边指针到边之前都是 right++

2. 里层 while 代表是否需要缩小窗口, 当窗口内的数据不符合要求 left++

3. 当窗口内的数据符合要求的时候, 记录下来窗口长度, 并输出记录过的最短长度.

---

来一题: 76. Minimum Window Substring

思路

按照上面的模板写出来并不难, 但这题的优化策略如下

1. 用 start 和 end 参数分别记录 最短窗口位置的起点和窗口长度. 只有当需要更新最短窗口的时候才更新他们. 这样可以避免多次截取字符串来拿到窗口内的字符串.

2. 如何高效的判断窗口内的字符串是否符合要求? 第一思路自然是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

思路

0. 基本上和上面的是一模一样, 基本抛弃原先的多次遍历循环的解法了, 太低效了.

1. 维护一个滑动的窗口, 这个窗口由 l, r 作为左节点和右节点进行维护.

2. 针对 s1, 由于它是可以任意排序的, 因此对它生成一个map用于记录各个字母出现的次数.

3. 滑动窗口什么时候扩张? 当r节点小于s2字符长度,

4. 滑动窗口什么时候收缩? 当窗口长度小于 s1.length就收缩

5. 滑动窗口扩张的时候, 拿到推入的那个字符串, 如果存在于 map, 则 map[key]--

6. 滑动窗口收缩的时候, 拿到推出的那个字符串, 如果存在于 map, 则 map[key]++

7. 收缩的同时, 校验map是否每个字符串都为 0, 如果为0, 则直接return true.

8. 在最后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
};

Reference

我写了套框架，把滑动窗口算法变成了默写题