(leetcode算法题)76. 最小覆盖子串

 以s = "ADOBECODEBANC", t = "ABC"为例,进行如下演示

对于上图的说明:

1. 上面八个状态是在从左往右滑动窗口时,每发现一个窗口满足以下条件就进行状态暂停

     条件:s[l, r] 覆盖了 t 这个字符串

2. 只有出窗口之后才有可能更新结果

滑动窗口需要问以下几个问题

Q1. 什么情况需要考虑开始从 r 所指的位置循环执行进窗口动作?

       r 遍历到的当前字符是 s[r], 无论 s[r] 是否在 t中,都需要不断进窗口

Q2. 什么时候需要暂停执行进窗口动作?

       r 遍历到的当前字符是 s[r], 无论 s[r] 是否在 t中,都需要不断进窗口

Q3. 什么时候需要考虑开始从 l 所指的位置循环执行出窗口动作?

       当发现 s[l, r] 已经覆盖了 t 这个字符串

Q4. 什么时候需要暂停执行出窗口动作?

       当发现 s[l] 存在于 t中,而且当前s[l, r]的中 s[l]的个数小于等于 t中 s[l]的个数

Q5. 什么时候更新结果?

        当前窗口中包含了t中的所有字符时,更新结果

class Solution {
    #define BIGINT -200000
public:
    string minWindow(string s, string t) {
        // record记录t中的某个字符还有多少个没被找到,
        // 若为负数,表明当前的字符串中这个字符找多了
        // unordered_map<char, int> record;
        int record[58] = {BIGINT};
        for(auto& ch : t){
            if(record[ch - 'A'] < 0){
                record[ch - 'A'] = 0;
            }
            record[ch - 'A']++;
        }
        int slen = s.size();
        string ret;
        int l = 0, r = 0;
        while(r <= slen){
            bool flag = false;
            for(int i = 0; i < 58; ++i){
                if(record[i] != BIGINT && record[i] > 0){
                    flag = true;
                    break;
                }
            }

            if(flag == false){
                while(record[s[l] - 'A'] == BIGINT || (record[s[l] - 'A'] != BIGINT && record[s[l] - 'A'] < 0)){
                    if(record[s[l] - 'A'] != BIGINT){
                        record[s[l] - 'A']++;
                    }
                    l++;
                }

                if(ret.size() == 0 || ret.size() > (r - l)){
                    ret.clear();
                    for(int i = l; i < r; ++i){
                        ret.push_back(s[i]);
                    }
                }
            }

            if(r < slen && record[s[r] - 'A'] != BIGINT){
                record[s[r] - 'A']--;
            }
            r++;
        }
        return ret;
    }
};

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

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

相关文章

二、BIO、NIO编程与直接内存、零拷贝

一、网络通信 1、什么是socket&#xff1f; Socket 是应用层与 TCP/IP 协议族通信的中间软件抽象层&#xff0c;它是一组接口&#xff0c;一般由操作 系统提供。客户端连接上一个服务端&#xff0c;就会在客户端中产生一个 socket 接口实例&#xff0c;服务端每接受 一个客户端…

HDFS架构原理

一、HDFS架构整体概述 HDFS是Hadoop Distribute File System 的简称&#xff0c;意为&#xff1a;Hadoop分布式文件系统。HDFS是Hadoop核心组件之一&#xff0c;作为大数据生态圈最底层的分布式存储服务而存在。HDFS解决的问题就是大数据如何存储,它是横跨在多台计算机上的文件…

Qt项目打包成绿色软件

Qt项目打包成绿色软件 一、图标添加与配置二、编译后打包文件附录有朋友将程序发给别人后运行,发现各种问题,如: 1.无法定位程序输入点__cxa_thread_atexit于动态链接库…。 2.缺少各种**.dll文件。 问‌我运行环境上Microsoft Visual C++ Redistributable运行环境都有,版本…

自动驾驶相关知识学习笔记

一、概要 因为想知道SIL、HIL是什么仿真工具&#xff0c;故而浏览了自动驾驶相关的知识。 资料来源《自动驾驶——人工智能理论与实践》胡波 林青 陈强 著&#xff1b;出版时间&#xff1a;2023年3月 二、图像的分类、分割与检测任务区别 如图所示&#xff0c;这些更高阶的…

C# 之某度协议登录,JS逆向,手机号绑定,获取CK

.NET兼职社区 .NET兼职社区 .NET兼职社区 .NET兼职社区 有需要指导&#xff0c;请私信我留言V或者去社区找客服。

数值分析速成复习笔记

请确保你有10hour的有效学习时间&#xff0c;保你拿90 证明部分 编程部分

06-RabbitMQ基础

目录 1.初识MQ 1.1.同步调用 1.2.异步调用 1.3.技术选型 2.RabbitMQ 2.1.安装 2.2.收发消息 2.2.1.交换机 2.2.2.队列 2.2.3.绑定关系 2.2.4.发送消息 2.3.数据隔离 2.3.1.用户管理 2.3.2.virtual host 3.SpringAMQP 3.1.导入Demo工程 3.2.快速入门 3.2.1.消…

Ungoogled Chromium127 编译指南 MacOS 篇(二)- 项目要求

1. 引言 在开始编译 Ungoogled Chromium 之前&#xff0c;我们需要确保系统满足所有必要的硬件和软件要求。由于浏览器编译是一个资源密集型的任务&#xff0c;合适的硬件配置和完整的软件环境至关重要。本文将详细介绍编译 Ungoogled Chromium 所需的各项要求。 2. 硬件要求…

springBoot整合ELK Windowsb版本 (elasticsearch+logstash+kibana)

springBoot整合ELK Windowsb版本 【elasticsearchlogstashkibana】 下载软件启动服务1、elasticsearch2、kibana3、logstash 集成springboot1、添加依赖2、在logback.xml添加相关配置3、修改logstash 配置4、重启logstash 最后测试 下载软件 elasticsearch 官网 https://www.…

vulnhub靶场【DC系列】之5

前言 靶机&#xff1a;DC-5&#xff0c;IP地址为192.168.10.4 攻击&#xff1a;kali&#xff0c;IP地址为192.168.10.2 都采用VMWare&#xff0c;网卡为桥接模式 对于文章中涉及到的靶场以及工具&#xff0c;我放置网盘中https://pan.quark.cn/s/2fcf53ade985 主机发现 使用…

Postman接口测试02|接口用例设计

目录 六、接口用例设计 1、接口测试的测试点&#xff08;测试维度&#xff09; 1️⃣功能测试 2️⃣性能测试 3️⃣安全测试 2、设计方法与思路 3、单接口测试用例 4、业务场景测试用例 1️⃣分析测试点 2️⃣添加员工 3️⃣查询员工、修改员工 4️⃣删除员工、查询…

计算机网络 (29)网络地址转换NAT

前言 网络地址转换&#xff08;Network Address Translation&#xff0c;NAT&#xff09;是计算机网络中的一种重要协议&#xff0c;它主要用于将私有IP地址转换为公共IP地址&#xff0c;以实现内部网络与外部网络之间的通信。 一、基本概念 NAT是一种在局域网&#xff08;LAN&…

BloombergGPT: A Large Language Model for Finance——面向金融领域的大语言模型

这篇文章介绍了BloombergGPT&#xff0c;一个专门为金融领域设计的大语言模型&#xff08;LLM&#xff09;。以下是文章的主要内容总结&#xff1a; 背景与动机&#xff1a; 大语言模型&#xff08;如GPT-3&#xff09;在多个任务上表现出色&#xff0c;但尚未有针对金融领域的…

jQuery的基本使用学习笔记

文章目录 jQuery的基本使用jQuery的入口函数jQuery的顶级对象 $jQuery对象和DOM对象jQuery对象和DOM对象的互相转换 jQuery选择器jQuery基础选择器jQuery层级选择器隐式迭代jQuery筛选选择器jQuery筛选方法&#xff01;&#xff01;&#xff01;jQuery里面的排他思想jQuery的链…

Android存储方案对比(SharedPreferences 、 MMKV 、 DataStore)

简介&#xff1a;本文介绍了Android开发中常用的键值对存储方案&#xff0c;包括SharedPreferences、MMKV和DataStore&#xff0c;并且对比了它们在性能、并发处理、易用性和稳定性上的特点。通过实际代码示例&#xff0c;帮助开发者根据项目需求选择最适合的存储方案&#xff…

[微服务]redis主从集群搭建与优化

搭建主从集群 单节点Redis的并发能力是有上限的&#xff0c;要进一步提高Redis的并发能力&#xff0c;就需要搭建主从集群&#xff0c;实现读写分离。 1. 主从集群结构 下图就是一个简单的Redis主从集群结构&#xff1a; 如图所示&#xff0c;集群中有一个master节点、两个s…

vue3 react使用高德离线地图

下载离线资源 下载地址 https://download.csdn.net/download/u010843503/90234612 2、部署私有化瓦片资源 ngxin中配置如下 server{listen 18082;server_name localhost;location / {root D:/GisMap/_alllayers;#try_files $uri $uri/ /index.html;#index index.html;} }下载…

【数据结构-堆】力扣2530. 执行 K 次操作后的最大分数

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。你的 起始分数 为 0 。 在一步 操作 中&#xff1a; 选出一个满足 0 < i < nums.length 的下标 i &#xff0c; 将你的 分数 增加 nums[i] &#xff0c;并且 将 nums[i] 替换为 ceil(nums[i] / 3) 。 返回在 恰好…

基于华为ENSP的OSPF状态机、工作过程、配置保姆级别详解(2)

本篇技术博文摘要 &#x1f31f; 基于华为enspOSPF状态机、OSPF工作过程、.OSPF基本配置等保姆级别具体详解步骤&#xff1b;精典图示举例说明、注意点及常见报错问题所对应的解决方法 引言 &#x1f4d8; 在这个快速发展的技术时代&#xff0c;与时俱进是每个IT人的必修课。我…

运动相机拍摄的视频打不开怎么办

3-10 GoPro和大疆DJI运动相机的特点&#xff0c;小巧、高清、续航长、拍摄稳定&#xff0c;很多人会在一些重要场合用来拍摄视频&#xff0c;比如可以用来拿在手里拍摄快速运动中的人等等。 但是毕竟是电子产品&#xff0c;有时候是会出点问题的&#xff0c;比如意外断电、摔重…