resin-notes
算法

滑动窗口

leetcode100滑动窗口

找到字符串中所有字母异位词

  1. 暴力解法 s是长的,p是短的 先统计字符长度小的,用map记录,然后外层循环遍历,i<=s.len-p.len,定义指针 l=i,r=i+p.len-1,内层while循环去判断l<=r,如果map.get(s[l]),map.set(xx,-1),l++ 如果不存在,直接brack退出循环。那么怎么判断是否执行了p.length次,定义一个count去判断 这种方法,map要每次i变化的时候都要重置
var findAnagrams = function(s, p) {
    const map = new Map()
    function reset(map){
        map.clear()
        for(let i=0;i<p.length;i++){
        map.set(p[i], (map.get(p[i]) || 0) + 1)
        }
    }
     let res=[]
    for(let i=0;i<=s.length-p.length;i++){
        reset(map)
        let l=i;
        let r=i+p.length-1
        let count = 0
        while(l<=r){
            //<=?
            if(map.get(s[l])){
                map.set(s[l],map.get(s[l])-1)
                count++
                l++
            }else{
                break
            }
        }
        if(count===p.length){
            res.push(i)
        }
    }
    return res
};
  1. 优秀解法

    固定滑动窗口模板

function fixedWindow(nums,k){
    let l=0
    let sum==0
    let res=-Infinity
    for(let r=0;r<nums.length;r++){
        //进窗口
        //xxx
        if(r-l+1===k){
            //出窗口
            //xxx
            //移除nums[l]的元素
            //l++ 指针移动
        }
    }
}
var findAnagrams = function (s, p) {
  const res = [];
  const m = s.length,
    n = p.length;
  if (m < n) return res;

  const need = new Map();
  for (const c of p) need.set(c, (need.get(c) || 0) + 1);

  const win = new Map();
  let left = 0,
    valid = 0;

  for (let right = 0; right < m; right++) {
    const c = s[right];
    if (need.has(c)) {
      win.set(c, (win.get(c) || 0) + 1);
      if (win.get(c) === need.get(c)) valid++; // 该字符刚好满足
    }

    if (right - left + 1 === n) {
      if (valid === need.size) res.push(left); // 全部字符满足

      const d = s[left++];
      if (need.has(d)) {
        if (win.get(d) === need.get(d)) valid--; // 移出前破坏满足
        win.set(d, win.get(d) - 1);
      }
    }
  }
  return res;
};

滑动窗口最大值

这个题目首先的思路就是外层循环遍历每一个元素,然后内层循环小于等于k,在内层循环里面做判断取最大值,然后加入输出数组

这个题目的最优解是单调队列,为什么会想出这个数据结构?是因为它每次的窗口都是固定的为k,也就是说在k中最大值。 起初我的想法从每k个,为一个单元组去遍历,每一次的外层循环其实就是遍历每一个单元组,也就是去记录出去的元素和进来的元素。 但是如果碰到了边界值这一部分就不是很好处理了。

所以在我看完答案之后这个题目就是用单调队列去进行比值当时我也想到了但我没有写出来

let deque = []; //队列记录索引
let ans = [];
for (let i = 0; i < nums.length; i++) {
  //这里的i作为右边界
  //1.进
  if (nums[deque[deque.length - 1]] <= nums[i]) {
    deque.pop();
  }
  deque.push(i);
  //2.出
  if (deque[0] <= i - k) {
    deque.shift();
  }
  //3.记录答案
  if (i - k + 1 >= 0) {
    ans.push(nums[deque[0]]);
  }
}
return xx;

On this page