滑动窗口:
程序员文章站
2022-03-11 20:06:11
...
滑动窗口:
框架:
/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
//自己创建两个有映射关系的数组
//HashMap<Character,Integer> needs = new HashMap<>();
//HashMap<Character,Integer> windows = new HashMap<>();
//可以选择性讲s和t转换成字符串
//,会方便一些,读取好像也会快一点
char[] str1=s.toCharArray();
char[] str2=t.toCharArray();
//保存对应字母的个数
int[] sArr=new int[128];
int[] tArr=new int[128];
//更新窗口
for (char c : str2) tArr[c]++;
int left = 0, right = 0;
int valid = 0;
while (right < s.size()) {
// c 是将移入窗口的字符
char c = str1[right];
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
...
// 判断左侧窗口是否要收缩
while (window needs shrink) {
// d 是将移出窗口的字符
char d = str1[left];
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
...
}
}
}
例题:
一、LeetCode 76 题,Minimum Window Substring,难度 Hard,
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串。
示例:
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
换句话说,第一个字符串的排列之一是第二个字符串的子串。
滑动窗口算法的思路是这样:
***1、***我们在字符串S
中使用双指针中的左右指针技巧,初始化left = right = 0
,把索引左闭右开区间[left, right)
称为一个「窗口」。
***2、***我们先不断地增加right
指针扩大窗口[left, right)
,直到窗口中的字符串符合要求(包含了T
中的所有字符)。
***3、***此时,我们停止增加right
,转而不断增加left
指针缩小窗口[left, right)
,直到窗口中的字符串不再符合要求(不包含T
中的所有字符了)。同时,每次增加left
,我们都要更新一轮结果。
***4、***重复第 2 和第 3 步,直到right
到达字符串S
的尽头。
初始状态:
增加right
,直到窗口[left, right)
包含了T
中所有字符:
现在开始增加left
,缩小窗口[left, right)
。
直到窗口中的字符串不再符合要求,left
不再继续移动。
代码如下:
public static String minWindow(String s, String t){
char[] str1=s.toCharArray();
char[] str2=t.toCharArray();
int[] sArr=new int[128];
int[] tArr=new int[128];
//初始化
int valid=0;
for (int i = 0; i < t.length(); i++) {
tArr[str2[i]]++;
if(tArr[str2[i]]==1){
valid++;
}
}
int left=0,right=0;
int count=0;
int start=0;//保存结果
int len= Integer.MAX_VALUE;
while(right<str1.length){
char ch=str1[right];
right++;
if(tArr[ch]!=0){//包含
sArr[ch]++;
if(sArr[ch]==tArr[ch]){//相同元素且个数相同
count++;
}
}
while (valid==count){
if(right-left<len){//更新结果
len=right-left;
start=left;
}
char temp=str1[left];
left++;
if(tArr[temp]!=0){//同时移动左边界,到窗口不满足条件!
if(sArr[temp]==tArr[temp]){
count--;
}
sArr[temp]--;
}
}
}
return
len==Integer.MAX_VALUE?"":s.substring(start,start+len);
}
二、找所有字母异位词
这是 LeetCode 第567题, 字符串的排列,难度 Medium:
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。
换句话说,第一个字符串的排列之一是第二个字符串的子串。
示例1:
输入: s1 = "ab" s2 = "eidbaooo"
输出: True
解释: s2 包含 s1 的排列之一 ("ba").
示例2:
输入: s1= "ab" s2 = "eidboaoo"
输出: False
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/permutation-in-string
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
代码如下:
public static List<Integer> findAnagrams(String s, String p){
if(s.length()<p.length()){
return new ArrayList<>();
}
List<Integer> list=new ArrayList<>();
char[] str1=s.toCharArray();
char[] str2=p.toCharArray();
//
int[] sArr=new int[26];
int[] tArr=new int[26];
//初始化
int valid=0;
for (int i = 0; i < p.length(); i++) {
tArr[str2[i]-'a']++;
}
int left=0,right=0;
//遍历
while(right<s.length()){
int ch=str1[right]-'a';
right++;
sArr[ch]++;
while(sArr[ch]>tArr[ch]){//超出窗口范围
sArr[str1[left]-'a']--;
left++;
}
if(right-left==p.length()){
list.add(left);
}
}
return list;
}
使用滑动窗口的题还有LeetCode 567 题、LeetCode 3 题等等。。
t++;
}
if(right-left==p.length()){
list.add(left);
}
}
return list;
}
使用滑动窗口的题还有LeetCode 567 题、LeetCode 3 题等等。。
上一篇: Angular CLI中的在线和离线安装
下一篇: 生成n位伪随机字符串