【算法】滑动窗口——最小覆盖子串

本节博客是对“最小覆盖子串”题目由暴力求解到滑动窗口的思路解析,有需要借鉴即可。

目录

  • 1.题目
  • 2.滑动窗口解法
  • 3.总结

1.题目

题目链接:LINK
在这里插入图片描述
这个题目是困难难度,感觉是一个中等题目的感觉。

首先我肯定想到的是暴力求解的方法,大概就是下面这种思路:
在这里插入图片描述
在比较找出的子串是否满足条件时候,可以用有效字符的方法,比如下面代码的count计数。

class Solution {
public:
//暴力求解:string minWindow(string s, string t) {//定义一个哈希表,用来收集t的有关信息string ret = "";int hash_t[128] = {0};for(int i = 0; i < t.size(); i++){hash_t[t[i]]++;}int minlength = 0;for(int left = 0; left < s.size(); left++){int hash_s[128] = {0};int count = 0;for(int right = left; right < s.size(); right++){//进哈希表hash_s[s[right]]++;if(hash_s[s[right]] <= hash_t[s[right]])count++;//有效字符++//判断if(count == t.size() && (minlength==0 || minlength >= right - left + 1)){minlength = right - left + 1;//有结果就把这次的长度更新过来,下一次比较的时候用ret = s.substr(left, minlength);break;}}}return ret;}
};

count有效计数原理:
当我们进哈希数组时候,如果这个字符映射的数组值小于等于hash_t的对应数组,则就是需要的,那么count就++,反之则不是
同理,当我们出字符时候,也是这个道理。
在这里插入图片描述

2.滑动窗口解法

但是我们可以发现,left 和 right是可以不用回退一直向前的,这就满足双指针,滑动窗口算法的使用条件
在这里插入图片描述

所以,代码可以优化成下面代码:

class Solution {
public:string minWindow(string s, string t) {//统计t的有关信息int hash_t[128] = { 0 };int kinds = 0;for(auto ch : t){if(hash_t[ch]++ == 0)kinds++;}int start = -1;int length = INT_MAX;//统计s的有关信息int hash_s[128] = { 0 };for(int left = 0, right = 0, count = 0; right < s.size(); right++){//进窗口char in = s[right];hash_s[in]++;if(hash_s[in] == hash_t[in])count++;//判断while(count == kinds){//更新结果if(right - left + 1 < length){length = right - left + 1;start = left;}//出窗口char out = s[left];if(hash_s[out] == hash_t[out]) count--;hash_s[out]--;left++;}}if(start == -1)return "";else return s.substr(start, length);}
};

注:这个地方的count计数与暴力求解的计数区别是这里用的是字母种类个数。

3.总结

如果有前面“滑动窗口”的题目铺垫其实这道题并不难,需要用到count计数的优化以及滑动窗口的思想。


EOF

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

STM32(GPIO)

GPIO简介 GPIO&#xff08;General Purpose Input Output&#xff09;通用输入输出口 引脚电平&#xff1a;0V~3.3V&#xff0c;部分引脚可容忍5V 输出模式下可控制端口输出高低电平&#xff0c;用以驱动LED、控制蜂鸣器、模拟通信协议输出时序等 输入模式下可读取端口的高低电…

Java特性之设计模式【享元模式】

一、享元模式 概述 享元模式&#xff08;Flyweight Pattern&#xff09;主要用于减少创建对象的数量&#xff0c;以减少内存占用和提高性能。这种类型的设计模式属于结构型模式&#xff0c;它提供了减少对象数量从而改善应用所需的对象结构的方式 享元模式尝试重用现有的同类对…

OS复习笔记ch5-4-2

引言 承接上文我们介绍了信号量机制和应用信号量机制实现的进程同步和互斥&#xff0c;这一节我们将围绕一些经典问题对信号量机制展开更深入地探讨。 读者/写者问题 读者/写者问题与我们之前遇到的问题类型不同&#xff0c;它描述的是&#xff1a; 有读者和写者两组进程&am…

C++初阶学习第七弹——探索STL奥秘(二)——string的模拟实现

标准库中的string&#xff1a;C初阶学习第六弹——string&#xff08;1&#xff09;——标准库中的string类-CSDN博客 前言&#xff1a; 在前面我们已经学习了如何使用标准库中的string类&#xff0c;但作为一个合格的程序员&#xff0c;我们不仅要会用&#xff0c;还要知道如…

网络库-libevent介绍

1.简介 libevent是一个事件驱动的网络库&#xff0c;主要用于构建可扩展的网络服务器。它提供了跨平台的API&#xff0c;支持多种事件通知机制&#xff0c;如select、poll、epoll、kqueue等。 主要组件 event: 表示一个具体的事件&#xff0c;包括事件类型、事件回调等。eve…

房屋出租管理系统需求分析及功能介绍

房屋租赁管理系统适用于写字楼、办公楼、厂区、园区、商城、公寓等商办商业不动产的租赁管理及租赁营销&#xff1b;提供资产管理&#xff0c;合同管理&#xff0c;租赁管理&#xff0c; 物业管理&#xff0c;门禁管理等一体化的运营管理平台&#xff0c;提高项目方管理运营效率…

如何查看centos7是否安装nginx

要查看 CentOS 7 系统上是否安装了 Nginx&#xff0c;您可以使用多种方法来检查。以下是一些常见的方法&#xff1a; 通过 RPM 包管理器查询 在 CentOS 系统上&#xff0c;可以使用 RPM 包管理器来查询已安装的软件包。要查看是否安装了 Nginx&#xff0c;您可以在终端中运行以…

【C++】学习笔记——继承_1

文章目录 十一、模板进阶5. 模板的优缺点 十二、继承1. 继承的概念及定义2. 基类和派生类对象赋值转换3. 继承中的作用域4. 派生类的默认成员函数 未完待续 十一、模板进阶 5. 模板的优缺点 优点&#xff1a; 模板复用了代码&#xff0c;节省资源&#xff0c;更快的迭代开发&a…

某银行软件测试笔试题,满分一百你能得多少分?

时间90分钟&#xff0c;满分100分&#xff09; 考试要求&#xff1a;计算机相关专业试题 一、填空题&#xff08;每空1分&#xff0c;共10分&#xff09; 1. ______验证___是保证软件正确实现特定功能的一系列活动和过程。 2. 按开发阶段分&#xff0c;软件测试可分为&#x…

SSIM(Structural Similarity),结构相似性及MATLAB实现

参考文献 Wang, Zhou; Bovik, A.C.; Sheikh, H.R.; Simoncelli, E.P. (2004-04-01). “Image quality assessment: from error visibility to structural similarity”. IEEE Transactions on Image Processing. 13 (4): 600–612. Bibcode:2004ITIP…13…600W. CiteSeerX 10.…

YOLO数据集制作(二)|json文件转txt验证

以下教程用于验证转成YOLO使用的txt格式&#xff0c;适用场景&#xff1a;矩形框&#xff0c;配合json格式文件转成YOLO使用的txt格式脚本使用。 https://blog.csdn.net/StopAndGoyyy/article/details/138681454 使用方式&#xff1a;将img_path和label_path分别填入对应的图…

Android Studio开发之路(九)创建android library以及生成aar文件

一、需求 我做了一个camerax相机opencv图像处理图片上传服务器功能的android应用&#xff0c;应客户需求要将其改成一个SDK&#xff0c;由客户加到他们自己的app里边。 于是&#xff0c;我需要制作一个library&#xff0c;打包成aar文件&#xff08;jar:只有代码&#xff0c;没…

YOLOv5改进 | 注意力机制 | 用于移动端的高效坐标CA注意力机制

在深度学习目标检测领域&#xff0c;YOLOv5成为了备受关注的模型之一。本文给大家带来的是能用于移动端的高效坐标CA注意力机制。文章在介绍主要的原理后&#xff0c;将手把手教学如何进行模块的代码添加和修改&#xff0c;并将修改后的完整代码放在文章的最后&#xff0c;方便…

打破地域界限,HubSpot海外获客系统引领企业走向国际化

在全球化的浪潮中&#xff0c;企业如何精准把握海外市场、高效获取并转化目标客户&#xff0c;已成为决定其市场地位与未来发展的关键因素。HubSpot海外获客系统以其独特的视角、强大的功能和卓越的性能&#xff0c;正在引领全球营销进入一个新的时代。今天运营坛将深入剖析Hub…

交易复盘-20240513

仅用于记录当天的市场情况,用于统计交易策略的适用情况,以便程序回测 短线核心:不参与任何级别的调整,采用龙空龙模式 一支股票 10%的时候可以操作, 90%的时间适合空仓等待 双成药业 (1)|[9:30]|[3566万]|0.34 中通客车 (1)|[9:43]|[7678万]|0.15 嘉华股份 (2)|[9:30]|[36…

基于Springboot的大学生平时成绩量化管理系统(有报告)。Javaee项目,springboot项目。

演示视频&#xff1a; 基于Springboot的大学生平时成绩量化管理系统&#xff08;有报告&#xff09;。Javaee项目&#xff0c;springboot项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三…

Spring Boot日志

目录 一、日志概述 1、为什么要学习日志&#xff1f; 2、日志的用途 &#xff08;1&#xff09;系统监控 &#xff08;2&#xff09;数据采集 &#xff08;3&#xff09;日志审计 二、日志使用 1、打印日志 &#xff08;1&#xff09;在程序中得到日志对象 &#xf…

WebView基础知识以及Androidx-WebKit的使用

文章目录 摘要WebView基础一、启动调整模式二、WebChromeClient三、WebViewClient四、WebSettings五、WebView和Native交互 Androidx-WebKit一、启动安全浏览服务二、设置代理三、安全的 WebView 和 Native 通信支持四、文件传递五、深色主题的支持六、JavaScript and WebAssem…

自主实现Telnet流量抓取

自主实现Telnet流量抓取 根据测试需求&#xff0c;需要抓取Telnet流量包&#xff0c;使用wireshark Python&#xff08;socket、telnetlib库&#xff09;实现 实现代码 主要此处有坑&#xff0c; 根据协议规则&#xff0c;wireshark 默认端口为23 的是Telnet协议&#xff0…

3D模型实时变形算法

最近&#xff0c;在尝试渲染一些奇怪的形状后&#xff0c;我陷入了计算机图形学的困境。事实证明&#xff0c;对于我试图解决的具体问题&#xff0c;没有现有的选项完全适合我想要做的事情。几周后&#xff0c;我终于带着一些答案再次浮出水面&#xff0c;写了很多行代码&#…