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

力扣017_最小覆盖字串题解----C++

题目描述

  1. 我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针,一个用于「延伸」现有窗口的 r 指针,和一个用于「收缩」窗口的 l 指针。在任意时刻,只有一个指针运动,而另一个保持静止。我们在 s 上滑动窗口,通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后,如果能收缩,我们就收缩窗口直到得到最小窗口。、
  2. 如何判断当前的窗口包含所有 t 所需的字符呢?我们可以用一个哈希表表示 t 中所有的字符以及它们的个数,用一个哈希表动态维护窗口中所有的字符以及它们的个数,如果这个动态表中包含 t 的哈希表中的所有字符,并且对应的个数都大于或等于t 的哈希表中各个字符的个数,那么当前的窗口是「可行」的。

假设这是我们对应的是s和t

创建unordered_map<char,int> hs,ht

我们定义两个指针,作为遍历s的窗口,再定义一个cnt作为窗口内的有效字符。

遍历s,用for循环,每循环一次r,把r指向的值存入到hs中,

 unordered_map<char,int> hs,ht;string ans;for(auto &c:t) ht[c]++; int l=0,r=0,cnt=0; //l为窗口的左边界,r为窗口的右边界for(;r<s.size();r++){ //每次循环右边界右移一次hs[s[r]]++;

此时有两种情况,当hs[s[r]]<=ht[s[r]] ,cnt++。

如果hs[s[l]]>ht[s[l]],说明hs里面已经存在两个相同的有效值了,如下图

ht:ABA,cnt=2 因为我们要找的是最小覆盖字串,且包含了A有效字符,所有这个时候我们的左窗口右移,并且减去一个A 

while(hs[s[l]]>ht[s[l]]){ //这个语句会右移左边界,比如这个边界字符不在t里,hs[s[l]]--;           //或者符合条件的边界值在后面又增加了一个且和左边界值相同,那么就可以右移左边界l++;

一次次的循环如下 

当我们的cnt 有效字符等于t.size()的时候,也就是这个窗口包含了t字符串的所有。

 if(cnt==t.size()){ //有效字符等于字符串t的长度,我们可以放入答案;if(ans.empty()||r-l+1<ans.size()) ans=s.substr(l,r-l+1);或者对比前窗口的大小和当前的大小,然后决定是否更新ans。}

如下即为全部的代码

class Solution {
public:string minWindow(string s, string t) {unordered_map<char,int> hs,ht;string ans;for(auto &c:t) ht[c]++; int l=0,r=0,cnt=0; //l为窗口的左边界,r为窗口的右边界for(;r<s.size();r++){ //每次循环右边界右移一次hs[s[r]]++;if(hs[s[r]]<=ht[s[r]]) cnt++; //在找到第一个符合条件的窗口后,这个语句不会再运行了。//ps.该语句的作用是统计窗口内的有效字符//左边界右移                              while(hs[s[l]]>ht[s[l]]){ //这个语句会右移左边界,比如这个边界字符不在t里,hs[s[l]]--;           //或者符合条件的边界值在后面又增加了一个且和左边界值相同,那么就可以右移左边界l++;}if(cnt==t.size()){ //有效字符等于字符串t的长度,我们可以放入答案;或者对比前窗口的大小和当前的大小,然后决定是否更新ans。if(ans.empty()||r-l+1<ans.size()) ans=s.substr(l,r-l+1); 对比前窗口的大小和当前的大小,然后决定是否更新ans。}}return ans;}
};

相关文章:

力扣017_最小覆盖字串题解----C++

题目描述 我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针&#xff0c;一个用于「延伸」现有窗口的 r 指针&#xff0c;和一个用于「收缩」窗口的 l 指针。在任意时刻&#xff0c;只有一个指针运动&#xff0c;而另一个保持静止。我们在 s 上滑动…...

C++:函数

在之前的博客中已经讲过了C语言中的函数概念了&#xff0c;重复的内容就不赘述了。C中的函数在C语言的基础上还有些补充&#xff0c;在这里说明一下。 一、引用 1.引用的概念 引用不是新定义一个变量&#xff0c;而是给已存在变量取了一个别名&#xff0c;编译器不会为引用变…...

linux asio网络编程理论及实现

最近在B站看了恋恋风辰大佬的asio网络编程&#xff0c;质量非常高。在本章中将对ASIO异步网络编程的整体及一些实现细节进行完整的梳理&#xff0c;用于复习与分享。大佬的博客&#xff1a;恋恋风辰官方博客 Preactor/Reactor模式 在网络编程中&#xff0c;通常根据事件处理的触…...

第一篇:数据库基础与概念

第一篇&#xff1a;数据库基础与概念 目标读者&#xff1a; 没有接触过数据库的初学者。 内容概述&#xff1a; 在本篇文章中&#xff0c;我们将从零开始&#xff0c;详细介绍数据库的基本概念、常见的数据库管理系统&#xff08;DBMS&#xff09;以及数据库设计的基础知识…...

从理论到实践:Django 业务日志配置与优化指南

在现代 Web 开发中,日志记录是确保系统可维护性和可观测性的重要手段。通过合理的日志配置,我们可以快速定位问题、分析系统性能,并进行安全审计。本文将围绕 Django 框架,详细介绍如何配置和优化业务日志,确保开发环境和生产环境都能高效地记录和管理日志。 © ivwdc…...

基于Python的药物相互作用预测模型AI构建与优化(上.文字部分)

一、引言 1.1 研究背景与意义 在临床用药过程中,药物相互作用(Drug - Drug Interaction, DDI)是一个不可忽视的重要问题。当患者同时服用两种或两种以上药物时,药物之间可能会发生相互作用,从而改变药物的疗效、增加不良反应的发生风险,甚至危及患者的生命安全。例如,…...

常用的 ASCII 码表字符

ASCII&#xff08;美国信息交换标准代码&#xff0c;American Standard Code for Information Interchange&#xff09;是一种字符编码标准&#xff0c;用于表示英文字符、数字、标点符号以及一些控制字符。ASCII 码表包含 128 个字符&#xff0c;每个字符用 7 位二进制数表示&…...

AI大模型开发原理篇-8:Transformer模型

近几年人工智能之所以能迅猛发展&#xff0c;主要是靠2个核心思想&#xff1a;注意力机制Attention Mechanism 和 Transformer模型。本次来浅谈下Transformer模型。 重要性 Transformer模型在自然语言处理领域具有极其重要的地位&#xff0c;为NLP带来了革命性的突破‌。可以…...

Golang 并发机制-2:Golang Goroutine 和竞争条件

在今天的软件开发中&#xff0c;我们正在使用并发的概念&#xff0c;它允许一次执行多个任务。在Go编程中&#xff0c;理解Go例程是至关重要的。本文试图详细解释什么是例程&#xff0c;它们有多轻&#xff0c;通过简单地使用“go”关键字创建它们&#xff0c;以及可能出现的竞…...

NVLink 拓扑、DGX 硬件渲染图

文章目录 一个 server 固定 8 个GPUP100&#xff08;4个NVL&#xff09;V100&#xff08;6个NVL&#xff09;A100&#xff08;12个NVL&#xff09;H100&#xff08;18个NVL&#xff09;【DGX-2 &#xff1a;2018年发布NVSwitch&#xff0c;实现full-mesh】【NVLink 拓扑&#x…...

Python XML 解析

Python XML 解析 引言 XML(可扩展标记语言)是一种用于存储和传输数据的标记语言。Python 作为一种功能强大的编程语言,拥有多种解析 XML 的库,如 xml.etree.ElementTree 和 lxml。本文将详细介绍 Python 中 XML 解析的方法、技巧和注意事项,帮助您更好地掌握 XML 数据的…...

java求职学习day22

MySQL 基础 &SQL 入门 1. 数据库的基本概念 1.1 什么是数据库 1. 数据库 (DataBase) 就是 存储 和 管理 数据的仓库 2. 其本质是一个文件系统, 还是以文件的方式,将数据保存在电脑上 1.2 为什么使用数据库 数据存储方式的比较 通过上面的比较 , 我们可以看出 , 使…...

stm32教程:EXTI外部中断应用

早上好啊大佬们&#xff0c;上一期我们讲了EXTI外部中断的原理以及基础代码的书写&#xff0c;这一期就来尝试一下用它来写一些有实际效能的工程吧。 这一期里&#xff0c;我用两个案例代码来让大家感受一下外部中断的作用和使用价值。 旋转编码器计数 整体思路讲解 这里&…...

OVS-DPDK

dpdk介绍及应用 DPDK介绍 DPDK&#xff08;Data Plane Development Kit&#xff09;是一组快速处理数据包的开发平台及接口。有intel主导开发&#xff0c;主要基于Linux系统&#xff0c;用于快速数据包处理的函 数库与驱动集合&#xff0c;可以极大提高数据处理性能和吞吐量&…...

快速分析LabVIEW主要特征进行判断

在LabVIEW中&#xff0c;快速分析程序特征进行判断是提升开发效率和减少调试时间的重要技巧。本文将介绍如何高效地识别和分析程序的关键特征&#xff0c;从而帮助开发者在编写和优化程序时做出及时的判断&#xff0c;避免不必要的错误。 ​ 数据流和并行性分析 LabVIEW的图形…...

MySQL数据库(二)

一 DDL (一 数据库操作 1 查询-数据库&#xff08;所有/当前&#xff09; 1 所有数据库&#xff1a; show databases; 2 查询当前数据库&#xff1a; select database(); 2 创建-数据库 可以定义数据库的编码方式 create database if not exists ax1; create database ax2…...

Python 梯度下降法(五):Adam Optimize

文章目录 Python 梯度下降法&#xff08;五&#xff09;&#xff1a;Adam Optimize一、数学原理1.1 介绍1.2 符号说明1.3 实现流程 二、代码实现2.1 函数代码2.2 总代码2.3 遇到的问题2.4 算法优化 三、优缺点3.1 优点3.2 缺点 Python 梯度下降法&#xff08;五&#xff09;&am…...

表格结构标签

<!-- thead表示表格的头部 tbody表示表格的主体 --> <thead></thead> <tbody></tbody> <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content&q…...

gcc和g++的区别以及明明函数有定义为何链接找不到

初级代码游戏的专栏介绍与文章目录-CSDN博客 我的github&#xff1a;codetoys&#xff0c;所有代码都将会位于ctfc库中。已经放入库中我会指出在库中的位置。 这些代码大部分以Linux为目标但部分代码是纯C的&#xff0c;可以在任何平台上使用。 源码指引&#xff1a;github源…...

Git进阶之旅:tag 标签 IDEA 整合 Git

第一章&#xff1a;tag 标签远程管理 git 标签 tag 管理&#xff1a; 标签有两种&#xff1a; 轻量级标签(lightweight)带有附注标签(annotated) git tag 标签名&#xff1a;创建一个标签git tag 标签名 -m 附注内容 &#xff1a;创建一个附注标签git tag -d 标签名…...

计算机网络一点事(24)

TCP可靠传输&#xff0c;流量控制 可靠传输&#xff1a;每字节对应一个序号 累计确认&#xff1a;收到ack则正确接收 返回ack推迟确认&#xff08;不超过0.5s&#xff09; 两种ack&#xff1a;专门确认&#xff08;只有首部无数据&#xff09; 捎带确认&#xff08;带数据…...

集合的奇妙世界:Python集合的经典、避坑与实战

集合的奇妙世界&#xff1a;Python集合的经典、避坑与实战 内容简介 本系列文章是为 Python3 学习者精心设计的一套全面、实用的学习指南&#xff0c;旨在帮助读者从基础入门到项目实战&#xff0c;全面提升编程能力。文章结构由 5 个版块组成&#xff0c;内容层层递进&#x…...

ubuntu20.04.6下运行VLC-Qt例子simple-player

下载examples-master.zip&#xff08;https://github.com/vlc-qt/examples&#xff09;&#xff0c;编译运行simple-player 参考链接&#xff1a; https://blog.csdn.net/szn1316159505/article/details/143743735 本文运行环境 Qt 5.15.2 Qt creator 5.0.2 主要步骤&#xf…...

Node.js MySQL:深度解析与最佳实践

Node.js MySQL:深度解析与最佳实践 引言 Node.js作为一种流行的JavaScript运行时环境,以其轻量级、高性能和事件驱动模型受到开发者的青睐。MySQL则是一款功能强大的关系型数据库管理系统,广泛应用于各种规模的应用程序中。本文将深入探讨Node.js与MySQL的集成,分析其优势…...

Linux网络 | 网络层IP报文解析、认识网段划分与IP地址

前言&#xff1a;本节内容为网络层。 主要讲解IP协议报文字段以及分离有效载荷。 另外&#xff0c; 本节也会带领友友认识一下IP地址的划分。 那么现在废话不多说&#xff0c; 开始我们的学习吧&#xff01;&#xff01; ps&#xff1a;本节正式进入网络层喽&#xff0c; 友友们…...

项目测试之Postman

文章目录 基础实战进行批量测试并输出报告 基础 实战 进行批量测试并输出报告 参考&#xff1a; https://blog.csdn.net/tyh_keephunger/article/details/109205191 概述 Newman是什么&#xff1f;Newman是Postman的命令行工具&#xff0c;用于执行接口测试集合。操作过程…...

C++——list的了解和使用

目录 引言 forward_list与list 标准库中的list 一、list的常用接口 1.list的迭代器 2.list的初始化 3.list的容量操作 4.list的访问操作 5.list的修改操作 6.list的其他操作 二、list与vector的对比 结束语 引言 本篇博客要介绍的是STL中的list。 求点赞收藏评论…...

MySQL基本架构SQL语句在数据库框架中的执行流程数据库的三范式

MySQL基本架构图&#xff1a; MySQL主要分为Server层和存储引擎层 Server层&#xff1a; 连接器&#xff1a;连接客户端&#xff0c;获取权限&#xff0c;管理连接 查询缓存&#xff08;可选&#xff09;&#xff1a;在执行查询语句之前会先到查询缓存中查看是否执行过这条语…...

(leetcode 213 打家劫舍ii)

代码随想录&#xff1a; 将一个线性数组换成两个线性数组&#xff08;去掉头&#xff0c;去掉尾&#xff09; 分别求两个线性数组的最大值 最后求这两个数组的最大值 代码随想录视频 #include<iostream> #include<vector> #include<algorithm> //nums:2,…...

如何用KushoAI提升API自动化测试效率:AI驱动的革命

在现代软件开发中,API测试已经成为确保系统稳定性和可靠性的关键。然而,传统的API测试往往依赖手动编写测试用例,每次修改API后都需要重新进行测试,这不仅耗时费力,还容易因人为疏忽而出现问题。想象一下,你是否曾因API在生产环境中出现微小错误而彻夜未眠?每次修改API后…...

docker安装nacos2.2.4详解(含:nacos容器启动参数、环境变量、常见问题整理)

一、镜像下载 1、在线下载 在一台能连外网的linux上执行docker镜像拉取命令 docker pull nacos:2.2.4 2、离线包下载 两种方式&#xff1a; 方式一&#xff1a; -&#xff09;在一台能连外网的linux上安装docker执行第一步的命令下载镜像 -&#xff09;导出 # 导出镜像到…...

DBeaver连接MySQL提示Access denied for user ‘‘@‘ip‘ (using password: YES)的解决方法

在使用DBeaver连接MySQL数据库时&#xff0c;如果遇到“Access denied for user ip (using password: YES)”的错误提示&#xff0c;说明用户认证失败。此问题通常与数据库用户权限、配置错误或网络设置有关。本文将详细介绍解决此问题的步骤。 一、检查用户名和密码 首先&am…...

VirtualBox:跨磁盘导入已存的vdi磁盘文件顺便测试冷迁移

目录 1.背景 2.目的 3.步骤 3.1 安装在移动硬盘上 3.2.接管现有主机磁盘上的虚拟机 3.3接管迁移到移动硬盘的虚拟机 4. 结论 1.背景 电脑重新做了系统&#xff0c;然后找不到virtualbox的启动程序了&#xff0c;另外电脑磁盘由于存储了其他文件已经爆红&#xff0c;无法…...

蓝桥杯思维训练营(一)

文章目录 题目总览题目详解翻之一起做很甜的梦 蓝桥杯的前几题用到的算法较少&#xff0c;大部分考察的都是思维能力&#xff0c;方法比较巧妙&#xff0c;所以我们要积累对应的题目&#xff0c;多训练 题目总览 翻之 一起做很甜的梦 题目详解 翻之 思维分析&#xff1a;一开…...

EchoMimicV2的部署使用

最近有一个录课的需要&#xff0c;我不想浪费人力&#xff0c;只想用技术解决。需求很简单&#xff0c;就是用别人现成的录课视频中的形象和声线&#xff0c;再结合我提供的讲稿去生成一个新的录课视频。我觉得应该有现成的技术了&#xff0c;我想要免费大批量生产。最近看到这…...

JVM深入学习(一)

目录 一.JVM概述 1.1 为什么要学jvm&#xff1f; 1.2 jvm的作用 1.3 jvm内部构造 二.JVM类加载 2.1类加载过程 2.2类加载器 2.3类加载器的分类 2.4双亲委派机制 三.运行时数据区 堆空间区域划分&#xff08;堆&#xff09; 为什么分区(代)&#xff1f;&#xff08…...

线段树(Segment Tree)和树状数组

线段树&#xff08;Segment Tree&#xff09;和树状数组 线段树的实现链式&#xff1a;数组实现 解题思路树状数组 线段树是 二叉树结构 的衍生&#xff0c;用于高效解决区间查询和动态修改的问题&#xff0c;其中区间查询的时间复杂度为 O(logN)&#xff0c;动态修改单个元素的…...

Teleporters( Educational Codeforces Round 126 (Rated for Div. 2) )

Teleporters&#xff08; Educational Codeforces Round 126 (Rated for Div. 2) &#xff09; There are n 1 n1 n1 teleporters on a straight line, located in points 0 0 0, a 1 a_1 a1​, a 2 a_2 a2​, a 3 a_3 a3​, …, a n a_n an​. It’s possible to tele…...

JavaScript 注释

JavaScript 注释 引言 JavaScript 注释是编写代码过程中不可或缺的一部分。它们不仅可以提高代码的可读性和可维护性,还能帮助其他开发者(或未来的自己)更好地理解代码的意图。本文将深入探讨 JavaScript 注释的多种类型、使用方法和最佳实践。 一、注释的分类 JavaScri…...

消息队列篇--原理篇--常见消息队列总结(RabbitMQ,Kafka,ActiveMQ,RocketMQ,Pulsar)

1、RabbitMQ 特点&#xff1a; AMQP协议&#xff1a;RabbitMQ是基于AMQP&#xff08;高级消息队列协议&#xff09;构建的&#xff0c;支持多种消息传递模式&#xff0c;如发布/订阅、路由、RPC等。多语言支持&#xff1a;支持多种编程语言的客户端库&#xff0c;包括Java、P…...

AVL搜索树

一、介绍 高度平衡的搜索二叉树&#xff0c;保证每个节点的左右子树高度差不超过1&#xff0c;降低搜索树的高度以提高搜索效率。 通过平衡因子和旋转来保证左右子树高度差不超过1 二、插入节点 1、插入规则 &#xff08;1&#xff09;搜按索树规则插入节点 &#xff08;…...

ELK模块封装starter

文章目录 1.combinations-elk-starter1.目录结构2.log4j2-spring.xml 从环境变量读取host和port3.ELKProperties.java 两个属性4.ELKAutoConfiguration.java 启用配置类5.ELKEnvironmentPreparedListener.java 监听器从application.yml中获取属性值6.spring.factories 注册监听…...

C# 与.NET 日志变革:JSON 让程序“开口说清话”

一、引言&#xff1a;日志新时代的开启 在软件开发的漫长旅程中&#xff0c;日志一直是我们不可或缺的伙伴。它就像是应用程序的 “黑匣子”&#xff0c;默默地记录着程序运行过程中的点点滴滴&#xff0c;为我们在调试、排查问题以及性能优化时提供关键线索。在早期&#xff…...

Ubuntu 系统,如何使用双Titan V跑AI

要在Ubuntu系统中使用双NVIDIA Titan V GPU来运行人工智能任务&#xff0c;你需要确保几个关键组件正确安装和配置。以下是基本步骤&#xff1a; 安装Ubuntu操作系统&#xff1a; 下载最新版本的Ubuntu服务器或桌面版ISO文件。使用工具如Rufus&#xff08;Windows&#xff09;或…...

CSDN的历史

CSDN(中国开发者网络,China Software Developer Network)是中国最具影响力的IT技术社区之一,其历史可追溯至1999年。以下是其发展历程和关键节点: --- **一、创立背景(1999年)** - **创始人**:蒋涛(国内知名技术人,曾参与金山软件早期开发)。 - **初衷**:为国内程…...

使用Pygame制作“贪吃蛇”游戏

贪吃蛇 是一款经典的休闲小游戏&#xff1a;玩家通过操控一条会不断变长的“蛇”在屏幕中移动&#xff0c;去吃随机出现的食物&#xff0c;同时要避免撞到墙壁或自己身体的其他部分。由于其逻辑相对简单&#xff0c;但可玩性和扩展性都不错&#xff0c;非常适合作为新手练习游戏…...

【详细教程】如何在Mac部署Deepseek R1?

DeepSeek是目前最火的国产大模型&#xff0c;官方App用户太多服务经常出现卡顿&#xff0c;部署一个本地DeepSeek R1可以方便使用。 1.系统最低要求 macOS 11 Big Sur 或更新 2.下载ollama https://ollama.com/ 3.安装DeepSeek R1 打开终端 运行命令 ollama run deepseek-…...

Java中的getInterfaces()方法:使用与原理详解

在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一个强大的工具&#xff0c;它允许程序在运行时动态地获取类的信息并操作类的属性和方法。getInterfaces()方法是Java反射API中的一个重要方法&#xff0c;用于获取类或接口直接实现的接口。本文将深入探讨getInt…...

PT站点自动签到

在站点下载一些视频电影资源&#xff0c;站点需要长期维护&#xff0c;每天自动签到。 两种方式&#xff1a; 一、保持浏览器登录状态&#xff0c;打开默认用户文件&#xff0c; 模拟点击签到&#xff08;点击按钮自行设置&#xff1a;根据href名称&#xff09; log日志 首次…...

计算机网络一点事(23)

传输层 端口作用&#xff1a;标识主机特定进程&#xff0c;TCP&#xff0c;UDP协议 端口号分类&#xff1a;服务器&#xff1a;0-1023&#xff0c;熟知 1024-49151 登记 客户端&#xff1a;49152-65535 功能&#xff1a;实现端到端&#xff0c;进程到进程的通信&#xff0c…...