0

算法学习-滑动窗口

 2 years ago
source link: https://silasmichealson.github.io/2022/03/12/%E7%AE%97%E6%B3%95%E5%AD%A6%E4%B9%A0-%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

滑动窗口算法

滑动窗口是一种基于双指针的一种思想，两个指针指向的元素之间形成一个窗口。

窗口有两类，一种是固定大小类的窗口，一类是大小动态变化的窗口。

3.应用场景

利用滑动窗口获取平滑的数据，如一段连续时间的数据平均值，能够有更好的稳定性，如温度监测。

什么情况可以用滑动窗口来解决实际问题呢？

  • 一般给出的数据结构是数组或者字符串
  • 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
  • 该问题本身可以通过暴力求解

4.算法思想

  1. 在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。
  1. 先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。

3. 此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。

4. 重复第 2 和第 3 步，直到 right 到达序列的尽头。
思路其实很简单：第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

5.算法模板

(1)单循环–适用于固定窗口大小

def template():
# 初始化滑动窗口两端
left = right = 0

# 序列及序列长度
seq, seq_len = xx, xx

# 滑动窗口序列
slide_win = []

# 结果值
rst = xx

while right < seq_len:
    slide_win.append(seq[right])
    # 还没找到一个可行解
    if not avaliable(slide_win):
        # 扩大窗口
        right += 1
    else:
        # 找到一个可行解，更新结果值
        rst = update()
        # 缩小窗口
        left += 1

(2)双层循环 – 适用于动态窗口

def template():
# 初始化滑动窗口两端
left = right = 0

# 序列及序列长度
seq, seq_len = xx, xx

# 滑动窗口序列
slide_win = []

# 结果值
rst = xx

while right < seq_len:
    slide_win.append(seq[right])
    # 还没找到一个可行解
    if not avaliable(slide_win):
        # 扩大窗口
        right += 1
        continue

    # 循环更新可行解
    while avaliable(slide_win):
        # 找到一个可行解，更新结果值
        rst = update()
        # 缩小窗口
        left += 1

6.实战代码

(1) 固定窗口 LC438_找到字符串中所有字母异位词

vector<int> findAnagrams(string s, string p) 
{
//窗口:字母和p相同的字串  窗口大小 p的长度
//当窗口小于n 则first++
//当窗口大于等于n  则second++

////异位词即字母出现相同

vector<int> ans=vector<int>(26,0);
vector<int> ver=vector<int>(26,0);
vector<int> res;
    for(int i = 0 ;i < p.size();i++)
    {
        ans[p[i]-'a']++;
    }
    for(int i = 0;i <s.size();i++ )
    {
        ver[s[i]-'a']++;
        if(i >= p.size()) ver[s[i-p.size()]-'a']--;
        if(ans == ver) res.push_back(i-p.size()+1);
    }
    return res;
}

(2) 动态窗口 LC76_最小覆盖子串

string minWindow(string s, string t)
{
//窗口:s字串的子串能覆盖住t  窗口大小 至少为t.length()
//当窗口小于 t.length() 则first++
//当窗口大于等于t.length()  若满足则second++

//覆盖即 s的字符出现数 >= p的字符出现数
//当使用unordermap 来存储<字符,字符出现次数>

string result;
if(s.empty()||t.empty()) return result;

unordered_map<char,int> map;
unordered_map<char,int> window;
for(char c:t)
{
    map[c]++;
}
int minlength = INT_MAX;
int lettercount =0;
for(int slow = 0 ,fast =0;fast < s.length();fast++)
{
    char c =s[fast];
    if(map.find(c) != map.end())//若此字符是目标串出现过的字符
    {
        window[c]++;
        if(window[c]<= map[c])
        lettercount++;//第一次遇到时 让count++
    }
    if(lettercount >= t.length())//全部的字符已经覆盖到了
    {
        while(map.find(s[slow])==map.end() || window[slow]> map[slow])
    //slow的字符没在目标串中出现的字母或者字符出现次数多与需要
    //在满足基恩本条件下缩小窗口
        {
            window[s[slow]]--;
            slow++;
        }
        if((fast - slow + 1 )< minlength)
        {
            minlength = fast-slow+1;
            result = s.substr(slow,minlength);
        }
    }
}
return result;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK