算法通关村第十六关—滑动窗口经典问题(白银)

发布时间:2024年01月15日

??滑动窗口经典问题

一、最长子串专题

1.1 无重复字符的最长子串

?LeetCode3给定一个字符串s,请你找出其中不含有重复字符的最长子串的长度。例如:

输入:s="abcabcbb"
输出:3
解释:因为无重复字符的最长子串是"abc",所以其长度为3

?要找最长子串,必然要知道无重复字符串的首和尾,然后再从中确定最长的那个,因此至少两个指针才可以,这就想到了滑动窗口思想。
?定义一个K-V形式的map,key表示的是当前正在访问的字符串,value,是其下标索引值。我们每访问一个新元素,都将其下标更新成对应的索引值。具体过程如下图:
image.png
?如果是已经出现过的,例如上述示例中的abcabc,当第二次遇到a时,我们就更新left成为第一个b所在的位置,此时发现left要移动的位置恰好就是map.get(‘a’)+1=1,将’a’用序列来表示,放在一起就是map.get(s.charAt(i)+1。其他情况可以参考图示依次类推。
?有一种特殊情况是需要考虑的,例如abba,我们第二次访问b时, left=map.get('b)+1=2。然后继续访问第二个a,此时left=map.get('a‘)+1=1,也就是left后退了,显然不对。
?我们应该让t在2的基础上继续向前,那该怎么办呢?和原来的对比一下,将最大的加1就可以了,也就是:left=Math.max(left,map.get(s.charAt(i))+1);
完整的代码如下:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(),max = 0; 
        Map<Character, Integer> map = new HashMap<>(); 
        for(int end = 0, start = 0; end < n; end++){ 
            char element = s.charAt(end); 
            if(map.containsKey(element)){ 
                start = Math.max(map.get(element)+1, start);
            }
            max = Math.max(max, end - start + 1);  
            map.put(element, end);  
        }
        return max;
    }
}

1.2 至多包含两个不同字符的最长子串

?LeetCode159题 给定一个字符串S,找出至多包含两个不同字符的最长子串t,并返回该子串的长度。例如:

输入:"eceba"
输出:3
解释:t是"ece",长度为3

?我们仍然使用Ieft和ight来锁定一个窗口,然后一边向右移动一边分析。我们用一个序列来看一下:aabbcccd。
image.png
?我们接下来需要解决两个问题,一个是怎么判断只有2个元素,另一个是移除的时候怎么知道移除谁,以及移除之后left是什么。
?要判断只有2个元素,还是Hash好用,每一个时刻,这个hashmap包括不超过3个元素。这里还要考虑到要移除谁,所以我们要设计一下Hash的Key-Valuet的含义。我们把字符串里的字符都当做键,在窗口中的最右边的字符位置作为值。此时使用下面的代码就可以确定要删除谁,以及窗口left的新位置:

//伪码,从Hash中找最小值
del_idx = Collections.min(hashmap.values());
left = del_idx + 1;

image.png

public int lengthofLongestSubstringTwoDistinct(String s){
if(s.length() < 3){
    return s.length();
}
int left = 0, right = 0;
HashMap<Character,Integer> hashmap = new HashMap();
int maxLen = 2;
while(right < s.length()){
    if(hashmap.size() < 3)
        hashmap.put(s.charAt(right),right++);
    //如果大小达到了3个
    if(hashmap.size()==3){
        //最左侧要删除的位置
        int del_idx = Collections.min(hashmap.values());
        hashmap.remove(s.charAt(delidx));
        //窗口left的新位置
        left = del_idx + 1;
    }
    maxLen = Math.max(maxLen, right -left);
}
return maxLen;
}

1.3 至多包含K个不同字符的最长子串

?如果再提高一下难度,至多包含K个不同字符的最长子串该怎么办呢?这是LeetCode340题。题目的完整要求是:给定一个字符串S,找出至多包含k个不同字符的最长子串T。示例:

输入:S="eceba",k=2
输出:3
解释:则T"ece",所以长度为3

?本题与上面的题几乎没有区别,只要将判断hash大小为2改成k就可以,超过2就是k+1。十分钟实现:

public int lengthofLongestSubstringTwoDistinct(String s, int k){
if(s.length() < k + 1){
    return s.length();
}
int left = 0, right = 0;
HashMap<Character,Integer> hashmap = new HashMap();
int maxLen = k;
while(right < s.length()){
    if(hashmap.size() < k + 1)
        hashmap.put(s.charAt(right),right++);
    //如果大小达到了k+1个
    if(hashmap.size()== k + 1){
        //最左侧要删除的位置
        int del_idx = Collections.min(hashmap.values());
        hashmap.remove(s.charAt(delidx));
        //窗口left的新位置
        left = del_idx + 1;
    }
    maxLen = Math.max(maxLen, right -left);
}
return maxLen;
}

二、长度最小的子数组

?LeetCode209.长度最小的子数组,给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其和≥target的长度最小的连续子数组[numsl,numsl±1,numsr-1,numsr],并返回其长度。如果不存在符合条件的子数组,返回0。

输入:target=7,nums=[2,3,1,2,4,3]
输出:2
解释:子数组[4,3]是该条件下的长度最小的子数组。

?本题可以使用双指针来解决,也可以视为队列法,基本思路是先让元素不断入队,当入队元素和等于target时就记录一下此时队列的容量,如果队列元素之和大于target则开始出队,直到小于target则再入队。
?如果出现等于target的情况,则记录一下此时队列的大小,之后继续先入队再出队。每当出现元素之和等于target时我们就保留容量最小的那个。

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, right = 0;
        int sum = 0;
        int min = nums.length + 1;
        for(right = 0; right < nums.length; right++){
            sum+= nums[right];
            if(sum >= target){
                for(;left < right; left++){
                    if(sum - nums[left]>= target) sum -= nums[left];
                    else break;
                }
                min = Math.min(min, right - left + 1);
            }
        }
        
        return min == nums.length + 1? 0 : min;
    }
}

三.盛水最多的容器

?LeetCode11.给定一个长度为n的整数数组height。有n条垂线,第i条线的两个端点是(i,0)和(i,height[i])。找出其中的两条线,使得它们与×轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。
image.png
平平无奇双指针,下面自己的解法

class Solution {
    public int maxArea(int[] height) {
        int left = 0,right = height.length-1; //创建左右指针,分别指向数组的开端和末端
        int max = 0; //max用于记录最大值
        while(left < right){ //当左右指针还未重合时
            int v = (right - left) * Math.min(height[left] , height[right]); //计算当前的容水量
            max = max > v ? max : v; //利用三目运算符判断最大值是否需要改变
            if(height[left] < height[right]) left++;  //对指向 高度比较低 的指针进行移动
            else right--;
        }
        return max; //返回最大值
    }
}

讲义解法,压缩版

public int maxArea(int[] height){
    int i=0,j=height.length -1,res 0;
    while(i<j){
        res = height[i] < height[j] ?
        	Math.max(res,(j-i)*height[i++]):
        	Math.max(res,(j-i)height [j--]);
    }
    return res;
}

四、寻找子串异位词(排列)

4.1 字符串的排列

?LeetCode567.给你两个字符串s1和s2,写一个函数来判断s2是否包含s1的排列。如果是,返回true;否则,返回flse。换句话说,s1的排列之一是s2的子串。其中s1和s2都只包含小写字母。

示例:
输入:s1="ab"s2="eidba00o"
输出:true
解释:s2包含s1的排列之一("ba").
public boolean checkInclusion(String s1, String s2) {
        if(s1.length() > s2.length()) return false;
        int[] arr1 = new int[26];
        int[] arr2 = new int[26];
        for(int i = 0; i < s1.length(); i++){
            arr1[s1.charAt(i) - 'a']++;
            arr2[s2.charAt(i) - 'a']++;
        }
        if(Arrays.equals(arr1,arr2)) return true;
        int j = 0;
        for(int i = s1.length(); i < s2.length(); i++){
             arr2[s2.charAt(i) - 'a']++;
             arr2[s2.charAt(j) - 'a']--;
             j++;
             if(Arrays.equals(arr1,arr2)) return true;
        }
        return false;
    }
}

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

?LeetCode438.找到字符串中所有字母异位词,给定两个字符串s和p,找到s中所有p的异位词的子串,返回这些子串的起始索引。不考虑答案输出的顺序。注意s和ρ仅包含小写字母。异位词指由相同字母重排列形成的字符串(包括相同的字符串)。
例如:

输入:s="cbaebabacd",p="abc"
输出:[0,6]
解释:
起始索引等于0的子串是
"cba",它是"abc"的异位词。
起始索引等于6的子串是"bac",它是"abc"的异位词。

?本题的思路和实现与上面几乎一模一样,唯一不同的是需要用一个List,如果出现异位词,还要记录其开始位置,那直接将其add到List中就可以了。完整代码:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList();
        if(s.length() < p.length()) return list;
        int[] arr1 = new int[26]; //保存p
        int[] arr2 = new int[26]; //保存s
        for(int i = 0; i < p.length(); i++){
            arr1[p.charAt(i) - 'a']++;
            arr2[s.charAt(i) - 'a']++;
        }
        if(Arrays.equals(arr1,arr2)) list.add(0);
        int left = 0;
        for(int right = p.length(); right < s.length(); right++){
            arr2[s.charAt(right) - 'a']++;
            arr2[s.charAt(left) - 'a']--;
            left++;
            if(Arrays.equals(arr1,arr2)) list.add(left);
        }
        return list;
    }
}
文章来源:https://blog.csdn.net/m0_73709096/article/details/135612713
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。