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

剑指 Offer II 017. 含有所有字符的最短字符串

题目链接

剑指 Offer II 017. 含有所有字符的最短字符串 hard

题目描述

给定两个字符串 st。返回 s中包含 t的所有字符的最短子字符串。如果 s中不存在符合条件的子字符串,则返回空字符串 ""

如果 s中存在多个符合条件的子字符串,返回任意一个。

注意: 对于 t中重复字符,我们寻找的子字符串中该字符数量必须不少于 t中该字符数量。

示例 1:

输入:s = “ADOBECODEBANC”, t = “ABC”
输出:“BANC”
解释:最短子字符串 “BANC” 包含了字符串 t 的所有字符 ‘A’、‘B’、‘C’

示例 2:

输入:s = “a”, t = “a”
输出:“a”

示例 3:

输入:s = “a”, t = “aa”
输出:“”
解释:t 中两个字符 ‘a’ 均应包含在 s 的子串中,因此没有符合条件的子字符串,返回空字符串。

提示:

  • 1<=s.length,t.length<=1051 <= s.length, t.length <= 10^51<=s.length,t.length<=105
  • st由英文字母组成

分析:

本题用 滑动窗口 求解。

用哈希表 ht记录 t中字符的出现次数。

再用另一个哈希表 hs记录 s滑动窗口区间的字符出现次数。

用两个指针 ij分别维护滑动窗口的左边界 和 右边界。

如果 hs[s[j]] <= ht[s[j]],说明此时的 s[j]依旧是有效字符,区间有效字符数 cnt += 1

如果 hs[s[i]] > ht[s[i]],说明此时的区间内部字符已经超过了 t,所以收缩左区间,hs[s[i]]--i++

如果 cnt == t.size(),说明此时的区间 [l,r]包含了 t的所有字符,所以此时的 s.substr(i,j-i+1)可作为答案之一。

时间复杂度: O(n)O(n)O(n)

代码:

class Solution {
public:string minWindow(string s, string t) {int m = s.size() , n = t.size();if(m < n) return "";unordered_map<char,int> ht,hs;for(auto &c:t) ht[c]++;int len = 1e9,idx = -1;int cnt = 0;for(int i = 0,j = 0;j < m;j++){hs[s[j]]++;if(hs[s[j]] <= ht[s[j]]) cnt++;while(hs[s[i]] > ht[s[i]]){hs[s[i]]--;i++;}if(cnt == n){if(j - i + 1 < len){idx = i;len = j - i + 1;}}}return idx == -1 ? "" : s.substr(idx,len);}
};

相关文章:

剑指 Offer II 017. 含有所有字符的最短字符串

题目链接 剑指 Offer II 017. 含有所有字符的最短字符串 hard 题目描述 给定两个字符串 s和 t。返回 s中包含 t的所有字符的最短子字符串。如果 s中不存在符合条件的子字符串&#xff0c;则返回空字符串 ""。 如果 s中存在多个符合条件的子字符串&#xff0c;返回任…...

Modbus协议初探(C#实现)

由于作者水平有限&#xff0c;如有写得不对得地方请指正 趁着今天休息&#xff0c;就折腾一下Modbus协议&#xff0c;之前零零散散的看过几篇博客&#xff0c;听说搞上位机开发的要会这个协议&#xff0c;虽然我不是搞上位机开发的&#xff0c;但个人对这个比较感兴趣。按照我个…...

【华为OD机试2023】静态扫描 C++ Java Python

【华为OD机试2023】静态扫描 C++ Java Python 前言 如果您在准备华为的面试,期间有想了解的可以私信我,我会尽可能帮您解答,也可以给您一些建议! 本文解法非最优解(即非性能最优),不能保证通过率。 Tips1:机试为ACM 模式 你的代码需要处理输入输出,input/cin接收输入、…...

函数栈帧的创建和销毁(详解)

函数栈帧的创建和销毁&#x1f996;函数栈帧是什么&#xff1f;&#x1f996;函数栈帧的创建和销毁解析&#x1f40b;栈是什么&#xff1f;&#x1f40b;认识相关寄存器和汇编指令&#x1f40b;解析函数栈帧的创建和销毁&#x1f433;预备知识&#x1f433;函数的调用堆栈&…...

【100个 Unity实用技能】 | 脚本无需挂载到游戏对象上也可执行的方法

Unity 小科普 老规矩&#xff0c;先介绍一下 Unity 的科普小知识&#xff1a; Unity是 实时3D互动内容创作和运营平台 。包括游戏开发、美术、建筑、汽车设计、影视在内的所有创作者&#xff0c;借助 Unity 将创意变成现实。Unity 平台提供一整套完善的软件解决方案&#xff…...

条件期望5

条件期望例题 随机图 从节点1开始, N为一个随机变量, 表示整个过程第一次出现"贪吃蛇"情形时, 所进行的步数.即Nk⇒Xk(1)∈{1,X(1),X2(1),...Xk−1(1)}其中1,X(1),X2(1),...Xk−1(1)各不相同N k \Rightarrow X^k(1) \in \{1,X(1), X^2(1),...X^{k-1}(1)\} \\ 其中1…...

RecyclerView ViewType二级

实现效果描述&#xff1a; 1、点击recyclerview中item&#xff0c;列表下方出现其他样式的item&#xff0c;作为子item&#xff0c;如下所示 所需要的java文件和xml文件有&#xff1a; 1、创建FoldAdapteradapter, 在FoldAdapter中&#xff0c;定义两种不同的类型&#xff…...

将对象或数组存在 dom元素的属性上,最后取不到完整数据,只取到 [{

目录 一、问题 二、问题及解决方法 三、总结 一、问题 1.我需要在dom元素里面添加了一个属性test存一个对象数组temp&#xff0c;以便我下一次找到这个dom元素时可以直接拿到属性里面的数据来渲染页面。 2.dom 属性上存 对象和数组&#xff0c;必须先JSON.stringify(arr),转…...

Flask源码篇:Flask路由规则与请求匹配过程(超详细,易懂)

目录1 启动时路由相关操作&#xff08;1&#xff09;分析app.route()&#xff08;2&#xff09;分析add_url_rule()&#xff08;3&#xff09;分析Rule类&#xff08;4&#xff09;分析Map类&#xff08;5&#xff09;分析MapAdapter类&#xff08;6&#xff09;分析 url_rule_…...

Jmeter接口测试教程之【参数化技巧总结】,总有一个是你不知道的

目录&#xff1a;导读 一、随机值 二、随机字符串 三、时间戳 四、唯一字符串UUID 说起接口测试&#xff0c;相信大家在工作中用的最多的还是Jmeter。 大家看这个目录就知道jmeter的应用有多广泛了&#xff1a;https://www.bilibili.com/video/BV1e44y1X78S/? JMeter是一个…...

缓存与数据库的双写一致性

背景 在高并发的业务场景下&#xff0c;系统的性能瓶颈往往是出现在数据库上&#xff0c;用户并发访问过大&#xff0c;压力都打到数据库上。所以一般都会用redis做缓存层&#xff0c;起到一个缓冲作用&#xff0c;让请求先访问到缓存层&#xff0c;而不是直接去访问数据库&am…...

力扣-213打家劫舍II(dp)

力扣-213打家劫舍II 1、题目 213. 打家劫舍 II 你是一个专业的小偷&#xff0c;计划偷窃沿街的房屋&#xff0c;每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 &#xff0c;这意味着第一个房屋和最后一个房屋是紧挨着的。同时&#xff0c;相邻的房屋装有相互连通…...

关于【网格结构】岛屿类问题的通用解法DFS(深度遍历)遍历框架+回溯+剪枝总结

最近在刷力扣时遇见的问题&#xff0c;自己总结加上看了力扣大佬的知识总结写下本篇文章&#xff0c;我们所熟悉的 DFS&#xff08;深度优先搜索&#xff09;问题通常是在树或者图结构上进行的。而我们今天要讨论的 DFS 问题&#xff0c;是在一种「网格」结构中进行的。岛屿问题…...

【LeetCode】982. 按位与为零的三元组

982. 按位与为零的三元组 题目描述 给你一个整数数组 nums &#xff0c;返回其中 按位与三元组 的数目。 按位与三元组 是由下标 (i, j, k) 组成的三元组&#xff0c;并满足下述全部条件&#xff1a; 0 < i < nums.length0 < j < nums.length0 < k < num…...

Linux内核源码进程原理分析

Linux内核源码进程原理分析一、Linux 内核架构图二、进程基础知识三、Linux 进程四要素四、task_struct 数据结构主要成员五、创建新进程分析六、剖析进程状态迁移七、写时复制技术一、Linux 内核架构图 二、进程基础知识 Linux 内核把进程称为任务(task)&#xff0c;进程的虚…...

电子技术——CMOS反相器

电子技术——CMOS反相器 在本节&#xff0c;我们深入学习CMOS反相器。 电路原理 下图是我们要研究的CMOS反相器的原理图&#xff1a; 下图展示了当输入 vIVDDv_I V_{DD}vI​VDD​ 时的 iD−vDSi_D-v_{DS}iD​−vDS​ 曲线&#xff1a; 我们把 QNQ_NQN​ 当做是驱动源&#x…...

gazebo仿真轨迹规划+跟踪(不在move_base框架下)

以Tianbot为例子&#xff0c;开源代码如下&#xff1a; https://github.com/tianbot/tianbot_mini GitHub - tianbot/abc_swarm: Ant Bee Cooperative Swarm, indicating air-ground cooperation. This repository is for Tianbot Mini and RoboMaster TT swarm kit. 1.在…...

C. Good Subarrays(前缀和)

C. Good Subarrays一、问题二、分析三、代码一、问题 二、分析 这道题目的意思就是给我们一个数组&#xff0c;然后我们从数组中选取一个连续的区间&#xff0c;这个区间满足条件&#xff1a;区间内的元素和等于区间的长度。 对于区间和问题我们先想到的是前缀和的算法。 那…...

关于Facebook Messenger CRM,这里有你想要知道的一切

关于Facebook Messenger CRM&#xff0c;这里有你想要知道的一切&#xff01;想把Facebook Messenger与你的CRM整合起来吗&#xff1f;这篇博文是为你准备的! 我们将介绍有关获得Facebook Messenger CRM整合的一切信息。然后&#xff0c;我们将解释为什么你需要像SaleSmartly&a…...

ChIP-seq 分析:数据与Peak 基因注释(10)

动动发财的小手&#xff0c;点个赞吧&#xff01; 1. 数据 今天&#xff0c;我们将继续回顾我们在上一次中研究的 Myc ChIPseq。这包括用于 MEL 和 Ch12 细胞系的 Myc ChIPseq。 可在此处[1]找到 MEL 细胞系中 Myc ChIPseq 的信息和文件可在此处[2]找到 Ch12 细胞系中 Myc ChIP…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)

1.获取 authorizationCode&#xff1a; 2.利用 authorizationCode 获取 accessToken&#xff1a;文档中心 3.获取手机&#xff1a;文档中心 4.获取昵称头像&#xff1a;文档中心 首先创建 request 若要获取手机号&#xff0c;scope必填 phone&#xff0c;permissions 必填 …...

Unsafe Fileupload篇补充-木马的详细教程与木马分享(中国蚁剑方式)

在之前的皮卡丘靶场第九期Unsafe Fileupload篇中我们学习了木马的原理并且学了一个简单的木马文件 本期内容是为了更好的为大家解释木马&#xff08;服务器方面的&#xff09;的原理&#xff0c;连接&#xff0c;以及各种木马及连接工具的分享 文件木马&#xff1a;https://w…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

【生成模型】视频生成论文调研

工作清单 上游应用方向&#xff1a;控制、速度、时长、高动态、多主体驱动 类型工作基础模型WAN / WAN-VACE / HunyuanVideo控制条件轨迹控制ATI~镜头控制ReCamMaster~多主体驱动Phantom~音频驱动Let Them Talk: Audio-Driven Multi-Person Conversational Video Generation速…...

回溯算法学习

一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

处理vxe-table 表尾数据是单独一个接口,表格tableData数据更新后,需要点击两下,表尾才是正确的

修改bug思路&#xff1a; 分别把 tabledata 和 表尾相关数据 console.log() 发现 更新数据先后顺序不对 settimeout延迟查询表格接口 ——测试可行 升级↑&#xff1a;async await 等接口返回后再开始下一个接口查询 ________________________________________________________…...

逻辑回归暴力训练预测金融欺诈

简述 「使用逻辑回归暴力预测金融欺诈&#xff0c;并不断增加特征维度持续测试」的做法&#xff0c;体现了一种逐步建模与迭代验证的实验思路&#xff0c;在金融欺诈检测中非常有价值&#xff0c;本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...