最小覆盖子串 ---- 滑动窗口

题目链接

题目:

分析:

  • 当我们找到一组符合的子字符串时, 找下一组让left++, 那么剩余的子字符串要么还符合条件, 要么少了一种字符, right一定不用回退, 所以可以使用滑动窗口
  • 因为题目中说字符串中自包含英文字母, 所以我们可以使用hash数组
  •  定义left = 0;right = 0;
  • 进窗口
  • 进窗口后, 更新有效字符的个数, 只有当hash2中out的数量 == hash2中out的数量时, 它才是有效字符, 此时count应该加上他们的数量, 作为有效字符的数量, 因为如果tt有重复字符, 重复字符都包括时, 才算有效字符
  • 判断 有效字符count的数量和tt数组的长度是否相等, 相等才算
  • 更新结果  因为只有找到子字符串才更新, 不是所有的都要记录, 所以在判断条件里更新结果, 记录子字符串开始的下标及长度
  • 出窗口前,  更新有效字符的个数, 只有当hash2中out的数量 == hash2中out的数量时, 它才是有效字符, 此时count应该减去他们的数量, 作为有效字符的数量, 因为如果tt有重复字符, 重复字符都包括时, 才算有效字符
  • 出窗口

代码:

class Solution {
    public String minWindow(String s, String t) {
        char[] tt = t.toCharArray();
        char[] ss = s.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int kinds = 0;
        for (char x : tt)
            if (hash1[x]++ == 0)
                kinds++;
        int left = 0;
        int right = 0;
        int count = 0;
        int minLen = Integer.MAX_VALUE;
        int begin = -1;
        while (right < ss.length) {
            char in = ss[right];
            hash2[in]++;
            if (hash1[in] == hash2[in])
                count++;
            while (count == kinds) {
                // 更新结果
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    begin = left;
                }
                char out = ss[left];
                if (hash2[out] == hash1[out])
                    count--;
                hash2[out]--;
                left++;
            }
            right++;
        }
        if (begin == -1)
            return new String();
        return s.substring(begin, begin + minLen);
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/630366.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

如何为没有域名的IP地址申请SSL证书

为没有域名的IP地址申请SSL证书的流程相对直接&#xff0c;但需要确保满足一些特定条件。以下是简化的步骤&#xff1a; 1、确保IP地址是公网IP&#xff1a;你必须拥有一个固定的公网IP地址&#xff0c;因为私有IP地址无法用于申请SSL证书。 2、选择证书颁发机构&#xff08;…

什么是Zoho CRM客户关系系统管理?

以客户为中心的商业时代&#xff0c;卓越的客户体验已成为企业持续增长与成功的关键,为了在这场激烈的市场竞争中脱颖而出&#xff0c;企业需要一套强大、灵活且智能的客户关系管理系统——Zoho CRM应运而生&#xff0c;它不仅是管理客户信息的工具箱&#xff0c;更是驱动业务增…

利用远程控制软件FinalShell远程连接虚拟机上的Linux系统(Windows)

一. VMware Workstation 安装CentOS Linux操作系统 传送门&#xff1a;VMware Workstation 安装CentOS Linux操作系统 1.右键打开终端 2.输入ifconfig 找到ens33对应 inet的id&#xff0c;这个就是虚拟机的ip地址图中所示为&#xff1a;192.168.5.128 3.打开finalshell 如…

[ciscn 2022 东北赛区]math

1.题目 import gmpy2 from Crypto.Util.number import * from flag import flag assert flag.startswith(b"flag{") assert flag.endswith(b"}") messagebytes_to_long(flag) def keygen(nbit, dbit):if 2*dbit < nbit:while True:a1 getRandomNBitIn…

渲染农场是什么意思?瑞云渲染为你解答

渲染农场是一种通过集合多台计算机的计算能力来加速图像渲染过程的系统。它尤其适用于动画、电影特效和高端视觉效果的制作&#xff0c;这些领域通常需要处理非常复杂和计算密集型的渲染任务。 渲染农场就是一大群电脑&#xff0c;他们一起可以快速渲染出漂亮的图像。在做动画片…

【Linux进程通信 —— 管道】

Linux进程通信 —— 管道 进程间通信介绍进程间通信的概念进程间通信的目的进程间通信的本质进程间通信的分类 管道什么是管道匿名管道匿名管道的原理pipe用fork来共享管道原理站在文件描述符角度-深度理解管道站在内核角度-管道本质管道读写规则管道的特点管道的四种特殊情况管…

K210开发板MicroPython开发环境搭建

一、安装CanMV IDE开发软件 1、进入如下连接 https://developer.canaan-creative.com/resource 2、点击下载 3、下一步 4、修改安装路径&#xff0c;下一步 5、接受许可下一步 6、下一步 7、安装 8、完成 9、区域①菜单栏&#xff1a;操作文件&#xff0c;使用工具等。…

HCIP【VLAN综合实验】

目录 一、实验拓扑图&#xff1a; 二、实验要求&#xff1a; 三、实验思路&#xff1a; 四、实验步骤&#xff1a; 1、在交换机SW1,SW2,SW3配置VLAN和各个接口对应类型的配置 2、在路由器上面配置DHCP服务 一、实验拓扑图&#xff1a; 二、实验要求&#xff1a; 1、PC1 …

【动态规划五】回文串问题

目录 leetcode题目 一、回文子串 二、最长回文子串 三、分割回文串 IV 四、分割回文串 II 五、最长回文子序列 六、让字符串成为回文串的最少插入次数 leetcode题目 一、回文子串 647. 回文子串 - 力扣&#xff08;LeetCode&#xff09;https://leetcode.cn/problems/…

Linux网络编程——HTTP协议的理解与运用

目录 前言 一、认识URL 二、认识HTTP样例 三、HTTP的报头内容 1.url 2. Content-Type 3.Method 方法 1.GET方法 2.POST方法 4、状态码 5.cookie和session 前言 我们知道&#xff0c;协议就是一种约定&#xff0c;客户端与服务端统一的用这种约定进行传输数据。我们…

deepin V23 RC 正式发布!

deepin 是一款基于 Linux 的开源桌面操作系统&#xff0c;就在今天&#xff0c;deepin V23 RC 来了&#xff0c;欢迎体验与反馈&#xff01; 感谢每一位 deepiner 提供想法与建议&#xff0c;让我们一起为打造美观易用、安全可靠的开源操作系统而努力&#xff01; 重要提示&a…

用docker命令行操作远程的Dockerd daemon服务

本地安装 Dockerd 服务太耗本机磁盘空间了&#xff0c;共用已有的Dockerd服务能够节省一部分空间 修改 Dockerd 服务启动文件&#xff0c;增加TCP监听方式 Dockerd 服务默认监听方式为 Unix Domain Socket &#xff0c;只允许本机连接&#xff0c;想要能够远程连接&#xff0…

一文说通用户故事点数是什么?

一文说通用户故事点数是什么&#xff1f; 第26期&#xff1a;一文说通用户故事点数是什么&#xff1f; 用户故事点数是一种采用相对估算法进行估算的一种工具&#xff0c;一般采用斐波那契数列表征用户故事里说的大小&#xff0c;采用0 1 2 3 5 8 13这样的一些数字来表征用户…

使用人人开源renren-fast快捷搭建后台管理系统

https://gitee.com/renrenio/renren-fast https://gitee.com/renrenio/renren-fast 初始化项目数据库 导入项目运行 期间遇到的坑 024-04-25 01:30:27.638 ERROR 25228 --- [ main] com.alibaba.druid.pool.DruidDataSource : init datasource error, url: jdbc:…

Postman基础功能-接口返回值获取

大家好&#xff0c;之前给大家分享关于Postman的接口关联&#xff0c;我们平时在做接口测试时&#xff0c;请求接口返回的数据都是很复杂的 JSON 数据&#xff0c;有着多层嵌套&#xff0c;这样的数据层级在 Postman 中要怎么获取呢&#xff1f; 接下来给大家展示几个获取 JSO…

计算机系列之排序算法

20、排序算法 1、直接插入排序&#xff08;这里以从小到大排序为例&#xff09; ◆要注意的是&#xff0c;前提条件是前i-1个元素是有序的&#xff0c;第i个元素依次从第i-1个元素往前比较&#xff0c;直到找到一个比第i个元素值小的元素&#xff0c;而后插入&#xff0c;插入…

免费SSL证书:适合你的网站吗?

随着互联网的发展&#xff0c;安全性已经成为了网站运营不可或缺的一部分。而SSL证书作为保障网站数据传输安全的重要手段&#xff0c;被越来越多的网站所采纳。然而&#xff0c;对于很多小型网站或者个人博客来说&#xff0c;付费购买SSL证书可能会带来一定的经济压力。因此&a…

Linux---编辑器vim的认识与简单配置

前言 我们在自己的电脑上所用的编译软件&#xff0c;就拿vs2022来说&#xff0c;我们可以在上面写C/C语言、python、甚至java也可以在上面进行编译&#xff0c;这种既可以用来编辑、运行编译&#xff0c;又可以支持很多种语言的编译器是一种集成式开发环境&#xff0c;集众多于…

UIKit之图片浏览器

功能需求 实现一个图片浏览器&#xff0c;点击左右按钮可以切换背景图&#xff0c;且更新背景图对应的索引页和图片描述内容。 分析&#xff1a; 实现一个UIView的子类即可&#xff0c;该子类包含多个按钮。 实现步骤&#xff1a; 使用OC语言&#xff0c;故创建cocoa Touch类…

解决kali Linux安装后如何将语言修改为中文

开启虚拟机 用root用户进入终端 进入终端执行dpkg-reconfigure locales命令 选择en_US.UTF-8 UTF-8选项&#xff0c;按空格键将其取消。 选择zh_CN.UTF-8 UTP-8&#xff0c;按空格选择&#xff0c;按tab键选择ok。 选择zh_CN.UTF-8字符编码&#xff0c;按tab键选择ok&#xff0…