面试经典150题——最小覆盖子串(困难)

"The greatest glory in living lies not in never falling, but in rising every time we fall." - Nelson Mandela​

an aerial view of a body of water surrounded by land

1. 题目描述

2.  题目分析与解析

2.1 思路一——暴力求解

还是和之前讲的一样,看见题目没思路,先试试普通情况下人的解法,也就是暴力求解。如果让一个人来解决该题目,那就是尝试从S字符串的每个位置作为起始位置,然后向后遍历,看是否能那囊括所有 t 中的字符,能囊括就记录位置与长度,不能囊括就记录为空,最后返回最短的子串。

代码思路:

  1. 初始化,对于 t 中字符,使用一个hashMap存储,键为字母,值为出现的次数

  2. 外层for循环遍历 s 中所有字符,作为起始字符

  3. 内层for循环遍历以每个起始字符出发向后尝试囊括 t 中字符

    1. 走到 s 尾部仍然不行,那就返回空串 (因为第一个字符作为起始位置都不能涵盖 t 所有字符,那也就是遍历了整个 s 都无法涵盖t,肯定无解)

    2. 能够囊括便停止,记录起始位置和终止位置

  4. 返回最短的解

但是很显然,这种算法时间复杂度很高,通过嵌套循环遍历字符串s,试图找到包含t中所有字符的最小窗口。对于s中的每一个字符(外层循环),它会迭代剩余的字符(内层循环)来找到这样的窗口。这导致了最坏情况下的时间复杂度为O(n^2),其中n是字符串s的长度。这是因为对于s中的每个字符,我们在最坏的情况下可能需要扫描它右侧的每个其他字符。同时还需要遍历 t 字符串,因此导致时间复杂度为O(n^2 \cdot m)。

现在我们考虑如何优化代码。

2.2 思路二——滑动窗口

这个题目起始和上一篇文章《串联所有单词的子串》题目非常的相似,如果大家对于滑动窗口没有解决该题目没有什么头绪可以先回头看看上个题目。

因为和上一篇内容十分相似,我就直接给出解决办法。

  • 我们需要指定一个左右指针,开始时左右指针都指向 s 的首字符,然后右指针不断向右移动,直到囊括了 t (也就是找到了第一个解)。

  • 这时我们移动左指针,将左指针不断加一,并判断在这种情况下是否还能囊括 t ,如果出现了不能囊括的情况,我们继续移动右指针,直到再次囊括 t 。

  • 然后继续移动左指针不断加一,并判断在这种情况下是否还能囊括 t ,以此循环,直到右指针走到结尾。

这样做之所以是正确的是因为每一次左指针的移动实际上就是以左指针指向的字符作为开始位置的判断(类似于暴力求解将,以左指针作为起始字符,向后寻找解)。

而之所以这样做很高效就是因为我在每一个位置都能利用窗口中的信息,从而减少了对窗口部分的判断,大大缩减了时间开销。

代码思路:

  1. 初始化哈希表

    1. 窗口计数表(windowCounts):同时,创建另一个哈希表来追踪当前滑动窗口中每个字符出现的次数。

    2. 频率表(freqMap):首先创建一个哈希表来存储字符串t中每个字符出现的次数。这是因为我们需要知道窗口中必须包含哪些字符,以及这些字符各需要出现多少次,才能认为窗口满足条件。

  2. 使用两个指针表示窗口的边界

    1. 左指针(left)和右指针(right):这两个指针分别表示当前考察的窗口的左右边界。初始时,两者都指向字符串s的开始位置。

  3. 扩大窗口

    1. 如果窗口中某个字符的数量达到了t中该字符所需的数量,则认为该字符已被“完全覆盖”。

    2. 移动右指针right来扩大窗口,每次右移一位,并更新windowCounts中对应字符的计数。

  4. 收缩窗口

    1. 在收缩的过程中,如果移除的字符是t中的必需字符,且其数量减少到小于t中所需的数量,则更新formed,表示窗口不再满足条件。

    2. 当窗口已包含所有t中的字符(即formed(用来跟踪当前窗口中完全匹配t中所有字符所需的唯一字符数)等于freqMap的大小时),尝试通过移动左指针left来收缩窗口,以找到可能的最小窗口。

  5. 更新最小窗口

    1. 在每次窗口变动(扩大或收缩)后,如果当前窗口满足所有t中字符的要求(即formed等于freqMap的大小),就比较并更新保存最小窗口的变量(如窗口大小、起始位置等)。

  6. 结果输出

    1. 最终,根据保存的最小窗口信息输出最小窗口子串。如果没有找到满足条件的窗口,则返回空字符串。

这种方法的优势在于它通过动态地调整窗口的大小来寻找最小满足条件的窗口,同时利用哈希表来有效地追踪和更新窗口内字符的情况,从而避免了不必要的字符串操作,提高了算法的效率。

3. 代码实现

3.1 暴力求解

3.2 滑动窗口

4. 相关复杂度分析

4.1 暴力求解

  • 时间复杂度

  1. 初始化tCharMap:首先遍历字符串t中的所有字符,这一步的时间复杂度为O(m),其中m是字符串t的长度。向HashMap中插入元素的平均时间复杂度为O(1),因此这一步的时间复杂度为O(m)。

  2. 寻找最小窗口:通过嵌套循环遍历字符串s,试图找到包含t中所有字符的最小窗口。对于s中的每一个字符(外层循环),它会迭代剩余的字符(内层循环)来找到这样的窗口。这导致了最坏情况下的时间复杂度为O(n^2),其中n是字符串s的长度。这是因为对于s中的每个字符,我们在最坏的情况下可能需要扫描它右侧的每个其他字符。

  3. 内层循环中的操作:内层循环中进行了检查tCharMapCopy中是否存在字符、更新映射和复制HashMap(tCharMapCopy = new HashMap<>(tCharMap))等操作。HashMap的复制操作是O(m),因为它必须复制原始映射中的所有条目。这个操作对于外层循环的每次迭代都会进行。对于s中的每个字符,检查和更新HashMap的平均时间复杂度是O(1)。

  4. 综合考虑这些操作,主导因素是嵌套循环结构,使得整体时间复杂度为O(n^2 × m)

  • 空间复杂度

  1. tCharMap的空间复杂度:这个HashMap存储了字符串t中每个字符及其出现的次数。因此,它的空间复杂度取决于t中不同字符的数量。在最坏的情况下,如果t中每个字符都不同,这个映射的空间复杂度是O(m),其中m是字符串t的长度。

  2. tCharMapCopy的空间复杂度:在外层循环的每次迭代中,我们都创建了HashMap tCharMap的一个副本。尽管这些副本是依次创建的,而不是同时存在的,但每个副本的空间复杂度也是O(m),因为它包含了t中所有不同字符的一个完整映射。

  3. 结果字符串ret的空间复杂度:这取决于找到的最小窗口的大小。在最坏的情况下,如果整个s是最小窗口,那么这个字符串的空间复杂度为O(n),其中n是字符串s的长度。因此,总的空间复杂度是由这三部分组成的,即O(m) + O(m) + O(n) = O(m + n)。这表明空间复杂度与输入字符串s和t的长度线性相关,主要是因为需要存储字符及其出现次数的映射以及可能的最小窗口子串。总结来说,此代码的空间复杂度主要受到两个因素的影响:一是存储t字符及其频率的映射,二是在查找过程中创建的映射副本以及存储结果子串。

  4. 因此,空间复杂度为O(m + n)

4.2 滑动窗口

  • 时间复杂度

  1. 哈希表操作:哈希表的插入、删除和查找操作的平均时间复杂度为O(1)。因此,尽管在遍历字符串和调整窗口的过程中进行了多次这些操作,它们的时间复杂度在整个算法的上下文中是线性的。综合以上各点,整个算法的总时间复杂度为O(n + m),这反映了需要分别遍历字符串s和t各一次,而对哈希表的操作平均来说是常数时间的。

  2. 窗口内数据更新:虽然左指针left的移动看起来在内部循环中进行,但每个字符在整个算法中由左指针和右指针各访问一次,因此这部分操作的总时间复杂度仍然是O(n)。

  3. 遍历字符串s:算法通过移动右指针right来遍历字符串s一次,对于字符串s中的每个字符,可能需要进行一次哈希表的更新操作。这部分的时间复杂度为O(n),其中n是字符串s的长度。

  4. 初始化频率表:遍历字符串t以构建字符频率表的时间复杂度为O(m),其中m是字符串t的长度。

  • 空间复杂度

  1. 答案记录:用于存储最小窗口的起始位置和长度的变量是固定大小的,可以忽略不计。因此,整个算法的总空间复杂度主要由哈希表决定,为O(m)。总结来说,优化后的滑动窗口算法的时间复杂度是O(n + m),空间复杂度是O(m),这反映了算法与输入字符串s的长度和字符串t中不同字符的数量线性相关。

  2. 频率表和窗口计数表:这两个哈希表存储了字符串t中所有唯一字符的计数,以及当前窗口中字符的计数。空间复杂度取决于字符串t中不同字符的数量。在最坏的情况下,如果t中每个字符都不同,这部分的空间复杂度为O(m),其中m是字符串t中唯一字符的数量。

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

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

相关文章

计算机毕业设计分享-SpringBoot宿舍管理平台app13023(赠送源码数据库)JAVA、PHP,node.js,C++、python,大屏数据可视化等

SpringBoot宿舍管理平台app 摘 要 近年来&#xff0c;校园内出现了越来越多的信息管理系统&#xff0c;逐渐覆盖了校园内的各种教学和管理业务。在各种制度的帮助下&#xff0c;校园的管理水平和效率都有了很大的提高。在学生管理方面&#xff0c;已经涌现了众多的信息管理系统…

每日OJ题_递归①_力扣面试题 08.06. 汉诺塔问题

目录 递归算法原理 力扣面试题 08.06. 汉诺塔问题 解析代码 递归算法原理 递归算法个人经验&#xff1a;给定一个任务&#xff0c;相信递归函数一定能解决这个任务&#xff0c;根据任务所需的东西&#xff0c;给出函数参数&#xff0c;然后实现函数内容&#xff0c;最后找出…

Editing While Playing 使用 Easyx 开发的 RPG 地图编辑器 tilemap eaitor

AWSD移动画布 鼠标右键长按拖拽 鼠标左键长按绘制 可以边拖拽边移动画布边绘制。 F1 导出 DLC F2 导入DLC author: 民用级脑的研发记录 1309602336qq.com 开发环境&#xff1a; 内置 easyx 的 devc 5.11 或者 VS 2022 TDM GCC 4.9.2 64-bit c11及以上都可运行 windows 环境运行…

机器学习3----决策树

这是前期准备 import numpy as np import pandas as pd import matplotlib.pyplot as plt #ID3算法 #每个特征的信息熵 # target : 账号是否真实&#xff0c;共2种情况 # yes 7个 p0.7 # no 3个 p0.3 info_D-(0.7*np.log2(0.7)0.3*np.log2(0.3)) info_D #日志密度…

华为23年9月笔试原题,巨详细题解,附有LeetCode测试链接

文章目录 前言思路主要思路关于f函数的剖析Code就到这&#xff0c;铁子们下期见&#xff01;&#xff01;&#xff01;&#xff01; 前言 铁子们好啊&#xff01;今天阿辉又给大家来更新新一道好题&#xff0c;下面链接是23年9月27的华为笔试原题&#xff0c;LeetCode上面的ha…

- 语言经验 - 《c++的高性能内存管理库tcmalloc和jemalloc》

本文属于专栏《构建工业级QPS百万级服务》​​​​​ 1、前置知识 c的内存管理&#xff0c;主要说的是堆内存管理。现代计算机系统中&#xff0c;用户进程的堆内存&#xff0c;由内核映射。 堆内存的来源 主要是通过mmap()函数&#xff0c;在进程的虚拟地址空…

【Linux技术宝典】深入理解Linux基本指令:命令行新手指南

&#x1f4f7; 江池俊&#xff1a; 个人主页 &#x1f525;个人专栏&#xff1a; ✅数据结构冒险记 ✅Linux技术宝典 &#x1f305; 有航道的人&#xff0c;再渺小也不会迷途。 文章目录 一、Linux下基本指令1. ls 指令2. pwd指令3. clear指令4. cd指令什么是家目录&#xf…

【AI视野·今日Robot 机器人论文速览 第七十八期】Wed, 17 Jan 2024

AI视野今日CS.Robotics 机器人学论文速览 Wed, 17 Jan 2024 Totally 49 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Robotics Papers Safe Mission-Level Path Planning for Exploration of Lunar Shadowed Regions by a Solar-Powered Rover Authors Olivier L…

【Pandas 统计函数和自定义函数的使用】

文章目录 前言一、统计函数1. 描述性统计2. 直方图 二、自定义函数1. 自定义函数示例 总结 前言 Pandas 是基于 NumPy 的数据分析工具&#xff0c;它提供了各种数据结构&#xff0c;如 Series 和 DataFrame&#xff0c;以及各种功能强大的函数&#xff0c;用于数据的统计、清洗…

随机过程及应用学习笔记(四) 马尔可夫过程

马尔可夫过程是理论上和实际应用中都十分重要的一类随机过程。 目录 前言 一、马尔可夫过程的概念 二、离散参数马氏链 1 定义 2 齐次马尔可夫链 3 齐次马尔可夫链的性质 三、齐次马尔可夫链状态的分类 四、有限马尔可夫链 五、状态的周期性 六、极限定理 七、生灭过…

Android adb使用超级大全

Android adb使用超级大全 ADB&#xff0c;即Android Debug Bridge&#xff0c;是一款强大的工具&#xff0c;对于Android开发/测试人员来说是不可或缺的&#xff0c;同时也是Android设备玩家的好玩具。本文将详细介绍ADB的使用方法。 ADB的基本用法如下&#xff1a; 命令语法…

chatglm3-6b使用

源码地址 GitHub - THUDM/ChatGLM3: ChatGLM3 series: Open Bilingual Chat LLMs | 开源双语对话语言模型 创建环境 conda create -n chatglm36 python3.11.7 修改源码中依赖&#xff0c;使得使用cuda&#xff0c;否则太慢了 pip3 install torch2.1.2 torchvision0.16.2 to…

SpringBoot3 + Vue3 由浅入深的交互 基础交互教学

说明&#xff1a;这篇文章是适用于已经学过SpringBoot3和Vue3理论知识&#xff0c;但不会具体如何实操的过程的朋友&#xff0c;那么我将手把手从教大家从后端与前端交互的过程教学。 目录 一、创建一个SpringBoot3项目的和Vue3项目并进行配置 1.1后端配置: 1.1.1applicatio…

C语言第二十四弹---指针(八)

✨个人主页&#xff1a; 熬夜学编程的小林 &#x1f497;系列专栏&#xff1a; 【C语言详解】 【数据结构详解】 指针 1、数组和指针笔试题解析 1.1、字符数组 1.1.1、代码1&#xff1a; 1.1.2、代码2&#xff1a; 1.1.3、代码3&#xff1a; 1.1.4、代码4&#xff1a; 1…

StringJoiner

JDK8开始有&#xff0c;用来操作字符串&#xff0c;不仅可以提高字符串的操作效率&#xff0c;而且在某些场景使用它操作字符串&#xff0c;代码会更加简洁。 import java.util.StringJoiner;public class Test {public static void main(String[] args) {//StringJoiner的应用…

ChatGPT高效提问—prompt实践(漏洞风险分析-重构建议-识别内存泄漏)

ChatGPT高效提问—prompt实践&#xff08;漏洞风险分析-重构建议-识别内存泄漏&#xff09; 1.1 漏洞和风险分析 ChatGPT还可以帮助开发人员预测代码的潜在风险&#xff0c;识别其中的安全漏洞&#xff0c;而不必先运行它&#xff0c;这可以让开发人员及早发现错误&#xff0…

探索设计模式的魅力:创建型设计模式的比较与决策

设计模式专栏&#xff1a;http://t.csdnimg.cn/U54zu 目录 一、设计模式概览 1.1 创建型模式 二、比较创建型设计模式 1.1 适用场景典型用例 1.2 关键要素与差异对比 1.3 结构图 三、模式选择指南 3.1 场景分析 3.2 决策流程图 四、结语 4.1 优势 4.2 考量因素 一、…

【漏洞扫描】网络空间安全工具—Goby 快速入门使用指南

下载地址 Goby&#xff08;含1322个POC&#xff09; v2.8.9 社区版 介绍 Goby是一款基于网络空间测绘技术的新一代网络安全工具&#xff0c;它通过给目标网络建立完整的资产知识库&#xff0c;进行网络安全事件应急与漏洞应急。 Goby可提供最全面的资产识别&#xff0c;目前…

串行通信的艺术:深入解析UART与奇偶校验

发送数据位是电流传输吗&#xff1f; 在UART&#xff08;Universal Asynchronous Receiver/Transmitter&#xff09;通信中&#xff0c;发送数据位不直接以电流的形式传输。而是通过改变电压水平或者光信号&#xff08;在光纤通信中&#xff09;来表示不同的数据位&#xff08…

C#利用接口实现选择不同的语种

目录 一、涉及到的知识点 1.接口定义 2.接口具有的特征 3.接口通过类继承来实现 4.有效使用接口进行组件编程 5.Encoding.GetBytes(String)方法 &#xff08;1&#xff09;检查给定字符串中是否包含中文字符 &#xff08;2&#xff09;编码和还原前后 6.Encoding.GetS…
最新文章