欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

滑动窗口:

程序员文章站 2022-03-11 20:00:34
...

滑动窗口:

框架:

/* 滑动窗口算法框架 */
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 第 438 题,Find All Anagrams in a String,难度 Medium:

滑动窗口:

相当于,输入一个串S,一个串T,找到S中所有T的排列,返回它们的起始索引

跟寻找字符串的排列一样,只是找到一个合法异位词(排列)之后将起始索引加入res即可。

代码如下:
public static boolean checkInclusion(String s1, String s2) {
        if(s1.length()>s2.length()){
            return false;
        }
        char[] str1=s1.toCharArray();
        char[] str2=s2.toCharArray();
        //
        int[] sArr=new int[26];//26是因为值包含小写字母
        int[] tArr=new int[26];
        //初始化
        int valid=0;
        for (int i = 0; i < s1.length(); i++) {
            sArr[str1[i]-'a']++;
            if(sArr[str1[i]-'a']==1){
                valid++;//有效的
            }
        }
        int left=0,right=0;
        int count=0;
        //遍历
        while(right<s2.length()){
            int ch=str2[right]-'a';
            right++;
            if(sArr[ch]!=0){//判断是否存在
                tArr[ch]++;
                if(tArr[ch]==sArr[ch]){
                    count++;
                }
            }
            while(right-left>=s1.length()){//超出窗口范围
                if(valid==count){
                    return true;
                }
                int temp=str2[left]-'a';
                left++;
                if(sArr[temp]!=0){
                    if(tArr[temp]==sArr[temp]){
                        count--;
                    }
                    tArr[temp]--;
                }

            }

        }
        return false;
}

LeetCode 438题、LeetCode 567 题、LeetCode 3 题等等。。

相关标签: 学习 笔记