数据与算法之美 2020-05-26
有看到一句话,我深以为然:“所有算法的终极数据结构只有两种:数组和链表!”其他所有数据结构都是数组或链表的衍生品,
不管是树还是图或者栈,至于算法就最终都落到了这两种结构的操作上,滑动窗口也不例外!滑动窗口的应用场景还是很多的:
HTTP的帧传输,滑动窗口限流算法、Flink中的滑动窗口等,今天,我们就来聊聊滑动窗口的算法框架!
作者原创文章,谢绝一切转载,违者必究!
准备:
Idea2019.03/JDK11.0.4
难度: 新手--战士--老兵--大师
目标:
先给出滑动窗口算法框架:
/* 滑动窗口算法框架 */private static void minWindow(String s,String t){ // 滑动窗口左右侧位置指针 int left = 0,right = 0; while (right < s.length()){ // 滑动窗口右边增加 right ++; if ( 滑动窗口满足目标){ //对窗口内元素操作 } // 滑动窗口左边缩小 while ( 滑动窗口缩小条件 ){ // left ++; } }}
我们以实际例子来加强理解,来个 hard 级别的玩一下,力扣第76题:
给你一个字符串 S、一个字符串 T,请在字符串 S 里面找出:包含 T 所有字符的最小子串:
示例,输入: S = "ADOBECODEBANC", T = "ABC",输出: "BANC",如果不存在则返回空串。
先直接写出解法如下(Java),略长,耐心看完必有收获:
public class SlideWindow { public static void main(String[] args) { String s = "DBABECFCAB"; String t = "ABC"; System.out.println(minWindow(s,t)); } private static String minWindow(String s,String t){ if (s.length()==0 || t.length() ==0){ return "NULL"; } // 目标字符串使用Map存储,如果有重复的,则数量累加 Map<Character,Integer> dictT = new HashMap<>(8); for (int i = 0; i < t.length(); i++) { int count = dictT.getOrDefault(t.charAt(i),0); dictT.put(t.charAt(i),count +1); } // 目标字符串的长度 int required = dictT.size(); // 滑动窗口左右侧位置指针 int left = 0,right = 0; // 滑动窗口中字符串统计 Map<Character,Integer> winStrMap = new HashMap<>(16); // 窗口内子串与目标串字符匹配的个数 int formed = 0; // 记录最小窗口长度,{窗口长,left,right} int[] ans = {-1,0,0}; //窗口进行滑动 while (right < s.length()){ char c = s.charAt(right); int count = winStrMap.getOrDefault(c,0); winStrMap.put(c,count + 1); // 匹配一个字符则记录一次 if (dictT.containsKey(c) && winStrMap.get(c).intValue() == dictT.get(c).intValue()){ formed ++; } while (left < right && formed == required){ c = s.charAt(left); //计算最小窗口长 if( ans[0] == -1 || (right - left + 1 < ans[0])){ ans[0] = right - left + 1; ans[1] = left; ans[2] = right; } winStrMap.put(c, winStrMap.get(c) -1); if (dictT.containsKey(c) && winStrMap.get(c) < dictT.get(c)){ formed --; } // 进行左侧缩小滑动 left ++; } //窗口向右滑动 right ++; } return ans[0] == -1 ? "NULL" : s.substring(ans[1],ans[2]+1); }}
以上代码解释:使用两个Map分别记录目标字符串和滑动窗口内字符串的字符数量,并进行对比;在窗口向右滑动的过程中,
如果满足目标条件则停下来进行窗口左侧缩小滑动,并记录下可行解的结果;窗口再向右滑动,并继续寻找可行解,直到右
侧到达终点。 此题有改良思路,即先对搜索字符串中去掉不存在于目标字符串中的字符,这样滑动匹配次数就更少了。
我做了一个动图,解释找到第一个可行解 {ABEC},既首次匹配到{A:1,B:1,C:1}的过程,注意此解不是最终解:
既然明白了算法框架思路,来做秒杀,题1,力扣第 567 题Medium级别:
给定两个字符串 s1 和 s2,写一个函数来判断 s2 是否包含 s1 的排列。示例,输入: s1 = "ab",
s2 = "eidbaooo",输出: True,解释: s2 包含 s1 的排列之一 ("ba").
参考上面的算法,直接裁剪一下就出来了(Java):
private static boolean subString(String s,String t){ if (s.length()==0 || t.length() ==0){ return false; } Map<Character,Integer> targetMap = new HashMap<>(8); for (int i = 0; i < t.length(); i++) { // 目标串中可能有重复字符, int count = targetMap.getOrDefault(t.charAt(i),0); targetMap.put(t.charAt(i),count + 1); } Map<Character,Integer> winMap = new HashMap<>(16); int left = 0,right = 0 ; int match = 0; while(right < s.length()){ char c = s.charAt(right); int count = winMap.getOrDefault(c,0); winMap.put(c,count + 1); // 右侧一直向右滑动,直到包含了目标串的所有字符排列 if (targetMap.containsKey(c) && targetMap.get(c).intValue() == winMap.get(c)){ match ++; } right ++; // 窗口左侧向右滑动,判断满足所有字符排列的子串 while (left < right && match == targetMap.size()){ // 如果子串长度等于目标串长度,即为可行解 if (right - left + 1 == targetMap.size()){ return true; } c = s.charAt(left); if (targetMap.containsKey(c) && targetMap.get(c).intValue() == winMap.get(c)){ count = winMap.getOrDefault(c,0); winMap.put(c,count -1); match --; } left ++; } } return false;}
代码解析:在窗口扩大滑动过程中,先找到包含了目标串所有字符的子串,然后左侧滑动缩小,如果同时满足
窗口中子串长度和目标串长度一样,因为既包含了所有字符且长度一样的子串肯定为一个排列,即为可行解!
秒杀题2,力扣第3题 Medium级别:
给定一个字符串,请你输出其中不含有重复字符的最长子串。示例: 输入, "ABEBCDEE", 输出:"EBCD",
我这里并非原题,做了个变形,要求输出子串,而不是给出个长度值,解法如下:
/**查找最长无重复子串*/private static String subString(String s) { if (s.length()==0){ return ""; } int left = 0,right = 0; Map<Character,Integer> winMap = new HashMap<>(8); int[] position={0,0,0}; while (right < s.length()){ char c = s.charAt(right); int count = winMap.getOrDefault(c,0); winMap.put(c, count + 1); if (right - left > position[0]){ position[0]= right - left; position[1]= left; position[2]= right; } while (winMap.get(c) > 1){ if (s.charAt(right) == s.charAt(left)){ count = winMap.get(c); winMap.put(c,count - 1); } left ++; } right ++; } return s.substring(position[1],position[2]);}
代码解析:如何找重复字符?即记录字符个数并累加,大于1的即存在重复。同样是滑动窗口,但注意使用一个
数组记录可行解,然后对比其他可行解,并只保留最优解。注意,最长无重复子串不唯一,如"ABEBCDEE",
可行解为"EBCD"或者"BCDE",故原题仅输出长度值而只有唯一解。另外,这里其实有个优化思路,每次窗口右
侧发现有重复字符,窗口左侧滑动时,可以不必逐字符滑动,可以直接定位到重复字符的下一位即可。
后记:总以为算法平时用的少,工作也不是算法岗,所以没必要去研究,可是遭到社会的毒打后,才知道算法是很重要的,共勉!
全文完!
我近期其他文章:
只写原创,敬请关注