Sliding Window

滑动窗口算法：

滑动窗口一般用于一个数组中，使用该窗口在数组合法区间内滑动，动态记录相关信息，从而提高算法复杂度

题目1：不包含相同元素的最长子串

题目描述：给定一个字符串，找出其中不含有重复字符的 最长子串 的长度。
输入：“abcgbef”
输出：5

  • 算法思想
    数组模拟队列，front标记窗口左端，i记录窗口右端，i从0遍历到数组末端.
    map<char,int>存放不同元素出现在窗口中的次数.

    1
    map<char, int> mp;

  • 开始front=0，i一直右移,map记录元素直至出现重复字符name，有mp[name]==2，记下字串长度res.
    i再要后移，则需舍去之前出现的重复字符，于是front右移至 a[front]==name.
    每次出现重复字符时就考虑更新字串长度res.

——————————————————————————————————————
·代码如下·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
int Sliding (string a)
{
	if(a == "")         //串为空时返回0
		return 0;
	int len = a.size();
	int front = 0, res = -1;
	char name;
	map<char, int> mp;
	for(int i=0; i<len; i++)
	{
		name = a[i];
		++mp[name];             //i右移，mp记录元素出现次数
		if(mp[name]==2)         //出现重复字符
		{
			res = max(res, i-front);    //更新res，重复的a[i]不能算，所以是i-front
			while(name != a[front])
			{
				--mp[a[front]];
				++front;
			}                //为保证没有重复字符，front后移至 name==a[front] 
			++front;         //front再右移一位，窗口内就不再有重复字符name了
			--mp[name];      //恢复至mp[name]=1，窗口i继续后移
		}
		else
		{
			if(i == len-1)      //特殊情况：i移至末尾但无重复字符
				res = max(res, i-front+1);  //此时若要更新长度为 i-front+1
		}
	}
	return res;
}

题目2：至少包含k个相同元素的最短子串

题目描述
给长度为n的一段字符，要求截取一段连续字串，满足至少包含k个相同字符，求该字串长度的最小值
输入：9 2
abebeabee
输出：2

  • 算法思想
    该题求至少k个字符的最短长度，即窗口内仅包含k个字符，并且
    k=1时,显然最短res为1；
    k>1时,最短时应满足a[front]=a[i]=name,name即重复的字符.
  • 直接说窗口在移动时和上题的不同之处吧.
    同样i右移至 mp[name]==k ,front右移直至 mp[name]==k(即a[front]==name).
    这是为了将长度尽可能缩短至 a[front]=a[i]=name.
    ——————————————————————————————————————————

·代码如下·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main()
{
	map<char, int> mp;
	char a[200005];
	int n, k, front = 0, res = -1;
	cin>>n>>k>>a;
	for(int i=0; i<n; i++)
	{
		char name = a[i];
		++mp[name];
		while(mp[name] == k)         //front右移至mp[name]=k-1 结束循环
		{
			if(res == -1)
				res = i-front+1;    //包含k=1,求res的情况
			else
				res = min(res, i-front+1);  //res最短要包含a[i],所以是 i-front+1
			--mp[a[front]];
			++front;
		}           
	}
	cout<< res <<endl; 
	return 0;

题目3：最多包含k个相同元素的最长子串

问题描述
链接：https://ac.nowcoder.com/acm/contest/3002/H
来源：牛客网
对于一个“01”串而言，每次操作可以把’0’字符改为’1’字符，或者把’1’字符改为’0’字符。所谓“01”串，即只含字符’0’和字符’1’的字符串。
nozomi有最多 k 次操作的机会。她想在操作之后找出一个尽可能长的连续子串，这个子串上的所有字符都相同。
这个子串的长度最大值是多少？ (注：k次操作机会可以不全部用完)
输入： 6 1
101110
输出： 5
(注将’0’改为’1’可得到子串最长为5，即“111110”; 将’1’改为’0’子串最长为2，即“001110”.
两者取最长 max(5,2)=5)

  • 问题分析
    分两种情况：
    1)将’0’改为’1’,得到子串字符全为’1’
    2)将’1’改为’0’,得到子串字符全为’0’
    最后求 max(Slide(‘1’), Slide(‘0’))

    1
    int Slide(char a)	//函数返回的是更改字符a后的最长子串长度

  • 算法思想
    如 Slide(‘1’) 最终得到子串字符全为’0’,更改’1’的次数不超过k.
    这里需要转化一下思想,即更改多少次字符’1’ 就是寻找’1’出现的次数.
    那么该问题即转化为 “01”串中最多包含k个’1’字符的最长子串.
    该问题类似题目1,稍微一点不同在于:
    更改字符次数mp(也就是包含题目1中重复字符个数mp)小于等于k,而不是小于2.

——————————————————————————————————————————

·代码如下·

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <map> 
using namespace std;
int n, k;
char c[200005];
int Slide(char a)					//change a
{									//其实并没有更改a,而是在滑动窗口同时查找a出现次数
	map<char, int> mp;
	mp[a]=0;
	int front=0, ans = 0, res = 0;
	for(int i=0; i<n; i++)
	{
		++mp[c[i]];
		if(mp[a]>k)						//出现重复字符a个数大于k(即更改次数超过k时)
		{
			while(c[front]!=a)
			{
				res = max(res, i-front); //其实移动过程不会更新，因为求的是最长长度
				++front;				//窗口左端开始移动,front移动和题目1一样
			}
			--mp[a];
			++front;
		}
		res = max(res, i-front+1);		//更新max,保证每次得到窗口内a出现次数不超过k
	}
	return res;
}
int main()
{
	cin>>n>>k>>c;
	cout<< max(Slide('1'), Slide('0'));
	return 0;
}

最后小结：

滑动窗口的算法思想：
窗口滑动时,始终保证窗口内是元素是满足要求的,这样滑动结束,最终就能找到问题最优解
算法时间复杂度为 窗口最大长度O(n).

数据结构与算法
字符串

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！