滑动窗口最终弹

简介: 滑动窗口最终弹

力扣30.串联所有单词的子串(巨困难)

这个最难的是什么

1.代码的编写

2.容器的使用

class Solution {
    List<Integer>ret=new LinkedList<>();
    //保存字典中所有单词的频次
    public List<Integer> findSubstring(String s, String[] words) {
     Map<String,Integer>hash=new HashMap<String,Integer>();
     for(String str: words){
       hash.put(str,hash.getOrDefault(str,0)+1);
         }
     int len=words[0].length();
     //表示word一个字符串的长度
     int m=words.length;
     //count应该是代表有效的字符串个数
     //用于存储字符串
   
     for(int i=0;i<len;i++){
         //进窗口,count每次循环之后都恢复为0
           Map<String,Integer>hash2=new HashMap<String,Integer>();
         for(int left=i,right=i,count=0;right+len<=s.length();right+=len){
             String in=s.substring(right,right+len);
             hash2.put(in,hash2.getOrDefault(in,0)+1);
             //因为是一个字符串,我在hash里已经把全部的字符串存进去了,我最后要求的
             //所有字符串的组合起来,然后看s里面有没有
             //换句话说,必须是组合,那么假如s里面存在重复的有效子串但是words里面没有这些子串
             //那么就说明一件事情,这个不是有效长度,不给予count++
             //注意这里的小于等于不是说让你添加,他此时假如说正好等于那么我有效字符串的数量还是要+1的
             if(hash2.get(in)<=hash.getOrDefault(in,0)){
                 count++;
             }
//看现在包含的长度,是不是有效字符串的长度,假如说比他要大了
             if(right-left+1>len*m ){
                 //出窗口
                 String out=s.substring(left,left+len);
                //还是要判断出去的是不是有效的子串
                 if(hash2.get(out)<=hash.getOrDefault(out,0))
            //注意这里的小于等于不是说让你添加,他此时假如说正好等于那么我有效字符串的数量还是要-1的
                     count--;
               hash2.put(out,hash2.get(out)-1);
                 left+=len;
             }
             if(count==m) ret.add(left);
         }
     }
        return ret;
   }
   }

力扣76.最小覆盖子串(较苦难)

这种题都很锻炼代码的编写

left=0,right=0

1.进窗口 hash[in]++

判断条件:check(hash1,hash2)

更新结果-起始位置,最短长度

2.出窗口 hash2[out]--

优化:判断条件

使用count标记有效字符的种类

能明白啥意思,但是不好写,建议明天回顾一手

class Solution {
    public String minWindow(String ss, String tt) {
    int minlen=Integer.MAX_VALUE;
    //假如说大写小写都包括,那么就直接128
    //统计字符串t中字符的频次
    int []hash1=new int[128];
    //统计窗口中字符的频次
    int []hash2=new int[128];
    //用来表示字符串字符有多少种
    int kinds=0;
    char[]t1=tt.toCharArray();
    char[]s=ss.toCharArray();
    int count=0;
    int begin=-1;
    //统计字符串t中字符的频次,kinds用来表示字符有多少种
    for(char a:t1){
        //如果之前没有存储这个字符串,那么kinds就++
        if(hash1[a]==0)kinds++;
        hash1[a]++;
    }
        for(int left=0,right=0;right<s.length;right++){
            char in=s[right];
            //java好像是可以自动转化,可以把字符自动转化成对应的ac数值
            hash2[in]++;//进窗口
            //假如两个哈希表里面的值相同count才会++,因为记录的是有效字符
            if(hash2[in]==hash1[in])count++;
            while(kinds==count){
 
                if(right-left+1<minlen){
                    //保留当前值
                    begin=left;
                    //更新最短的长度
                    minlen=right-left+1;
                }
                //出窗口
                char out=s[left];
                //假如出的是有效字符,才会count--
                if(hash1[out]==hash2[out])count--;
                 left++;
                 //出窗口
                 hash2[out]--;
            }
            //假如说count和t存储的字符种类一样,那么
            if(count==tt.length()){
               begin=left;
               left=right+1;
            }
        }
     if(begin==-1) return new String();
     else return ss.substring(begin,begin+minlen);
    }
}


相关文章
|
API
代码随想录 Day10 栈与队列 LeetCode T239 滑动窗口的最大值 T347 前K个高频元素
代码随想录 Day10 栈与队列 LeetCode T239 滑动窗口的最大值 T347 前K个高频元素
49 0
|
4月前
|
算法
【算法】滑动窗口——将x减到0的最小操作数
【算法】滑动窗口——将x减到0的最小操作数
|
3月前
回推和递推
回推和递推。
37 5
|
6月前
滑动窗口第二弹
滑动窗口第二弹
|
7月前
|
算法
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
【优选算法】——滑动窗口——1004. 最大连续1的个数 III
|
7月前
|
算法 C语言
[优选算法]------滑动窗⼝——209. 长度最小的子数组
[优选算法]------滑动窗⼝——209. 长度最小的子数组
|
6月前
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
【LeetCode刷题】滑动窗口思想解决:最大连续1的个数 III、将x减到0的最小操作数
|
7月前
leetcode代码记录(下一个更大元素 II
leetcode代码记录(下一个更大元素 II
27 0
|
7月前
|
索引
leetcode代码记录(下一个更大元素 I
leetcode代码记录(下一个更大元素 I
25 0
|
7月前
leetcode代码记录(滑动窗口最大值
leetcode代码记录(滑动窗口最大值
34 0