当前位置: 首页 > article >正文

算法016——最小覆盖子串

力扣——最小覆盖子串(点击跳转)
在这里插入图片描述
分析题目
在这里插入图片描述
我们先随便从一个位置开始,让 right 右移,直到找到符合题目的位置停下
在这里插入图片描述
之后,让 left 右移,此时会出现两种情况

  1. 仍然符合要求,right 不需要动
  2. 不符合要求,此时让 right 右移,知道找到符合要求的位置

所以我们使用滑动窗口 + 哈希表的方式来解决此问题。

此时,窗口满足出窗口,让 left 右移
在这里插入图片描述

  1. left = 0,right = 0
  2. 进窗口: hash2[in]++
  3. 判断:check(hash1,hash2)
    更新结果:起始位置,最短长度
    出窗口:hash2[out]–

跟上两篇博客一样,我们可以对判断条件做出优化
前两篇博客找到字符串中所有的字母异位词

定义一个变量 count 表示有效字符的种类

进窗口,要在相等的时候比较,相等说明此时进窗口的字符为有效字符,之后让 count++,如果按照上一道题,大于等于来比较的话,会有重复
在这里插入图片描述

出窗口时,加入 left 与 right 在如图所示的位置上,我们要在出窗口之前判断,等于说明出窗口的为有效字符,让 count–

最后判断 count 是否等于 hash1的长度

  1. 进窗口:hash2[in] == hash1[in] ——> count++
  2. 出窗口:hash2[out] == hash1[out] ——> count–
  3. 判断条件: count == hash1.size()

代码如下:

class Solution {
    public String minWindow(String s, String t) {
        char[] s1 = s.toCharArray();
        char[] t1 = t.toCharArray();
        int[] hash1 = new int[128];
        int kind = 0;//用于统计 t 字符串中的字符种类的个数
        for(char ch : t1){
            if(hash1[ch]++ == 0){
                kind++; 
            }
        } 
        int[] hash2 = new int[128];
        int minlen = Integer.MAX_VALUE;
        int begin = -1;
        for(int left = 0,right = 0,count = 0;right < s1.length;right++){
            char in = s1[right];
            if(++hash2[in] == hash1[in]){
                count++;  
            }
            while(kind == count){
                if(right - left + 1 < minlen){
                    begin = left;
                    minlen = right - left + 1;
                }
                char out = s1[left++];
                if(hash2[out]-- == hash1[out]){
                    count--;
                }
            }
        }
        if(begin == -1){
            return new String();
        }else{
            return s.substring(begin,begin + minlen);
        }
    }
}

完成了,我要累死了,休息
在这里插入图片描述


http://www.kler.cn/a/589427.html

相关文章:

  • ABAP OPEN DATASET
  • nginx处理跨域问题以及隐藏第三方地址
  • 适配iOS 18:检测并移除三方库中的 bitcode 部分
  • CentOS高性能数据处理优化指南
  • 微服务存在的问题及解决方案
  • 设计模式之外观模式:原理、实现与应用
  • C++ primer plus 使用类上
  • 【Agent】OpenManus-Flow-PlanningFlow设计分析
  • golang-方法
  • 创建表空间和表
  • 优选算法的匠心之艺:二分查找专题(二)
  • C++洛谷基础练习题及解答
  • TCP简单链接的编程实现
  • 关于Redis的集群(上)
  • 高主频GPU+RTX4090:AI生图性能优化超150%
  • Netty基础—7.Netty实现消息推送服务一
  • llama.cpp 和 LLM(大语言模型)
  • 图 最 短 路
  • 【嵌入式学习】计算机组成原理-二进制存储基础
  • 【从零开始】Air780EPM的LuatOS二次开发——OneWire协议调试注意事项!