【十二】【算法分析与设计】滑动窗口(3)

30. 串联所有单词的子串

给定一个字符串 s 和一个字符串数组 words words 中所有字符串 长度相同

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

  • 例如,如果 words = ["ab","cd","ef"], 那么 "abcdef""abefcd""cdabef""cdefab""efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1:

 

输入:s = "barfoothefoobarman", words = ["foo","bar"] 输出:[0,9]解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2:

 

输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"] 输出:[]解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。 所以我们返回一个空数组。

示例 3:

输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出:[6,9,12] 解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

提示:

  • 1 <= s.length <= 10(4)

  • 1 <= words.length <= 5000

  • 1 <= words[i].length <= 30

  • words[i]s 由小写英文字母组成

我们需要再s找一个子数组,这个子数组包含words的所有的元素。返回这个子数组的首索引。

注意到words里面的单词长度都是一样的。所以我们满足要求的所有子数组,都是按照单词的长度划分的。

我们将字符串看做一个整体,问题转化为在s子数组中找words的异位词。

利用map容器模拟hash表。hash1记录words中不同字符串对应的个数,hash2记录区间[left,right]中不同字符串对应的个数。

在s中划分字符串,有len=words[0].size()种划分情况。

adfea3c18eeb40e78b5301569e9dfc15.png

对于每一种划分情况,我们只需要寻找符合要求的子数组即可。每一次遍历长度为len的字符串。

[left,right]区间,hash2记录区间[left,right]中不同字符串对应的个数,count记录区间内有效的字符个数,[left,right]长度不超过len*m。

因为[left,right]长度等于len*m的时候,就是对于left组合的一个解,对于后面的组合都不需要再考虑了,因为首索引都没有改变。

不断维护这个意义,我们每一次只需要判断count是否等于m,就知道[left,right] 是否符合条件。

当我们添加进right元素后,维护hash2和count。如果right-left+1>len*m,表示对于left的所有组合都考虑完毕了。left++。维护hash2和count。

此时[left,right]长度符合条件,hash2和count都维护成功,这就是一个可能的解,判断count==m,如果相等就是一个解。

 
class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ret;
        unordered_map<string, int> hash1;
        for (auto& s : words)
            hash1[s]++;

        int len = words[0].size(), m = words.size();
        for (int i = 0; i < len; i++) {
            unordered_map<string, int> hash2;
            for (int left = i, right = i, count = 0; right + len <= s.size();
                 right += len) {
                string in = s.substr(right, len);
                hash2[in]++;
                if (hash1.count(in) && hash2[in] <= hash1[in])
                    count++;

                if (right - left + 1 > m * len) {
                    string out = s.substr(left, len);
                    if (hash1.count(out) && hash2[out] <= hash1[out])
                        count--;
                    hash2[out]--;
                    left += len;
                }

                if (count == m)
                    ret.push_back(left);
            }
        }

        return ret;
    }
};

unordered_map<string, int> hash1; 定义了一个哈希表 hash1,用于存储 words 中每个单词的出现次数。

for (auto& s : words) hash1[s]++; 遍历单词列表 words,更新哈希表 hash1,计算每个单词的出现次数。

int len = words[0].size(), m = words.size(); 获取单词的长度 len(假设所有单词长度相同)和单词列表 words 的大小 m。

for (int i = 0; i < len; i++) { 由于单词有固定长度,所以使用多个滑动窗口,每个窗口的起始位置从 0 到 len-1。

unordered_map<string, int> hash2; 对于每个滑动窗口,定义一个哈希表 hash2,用于存储当前考察的窗口中每个单词的出现次数。

for (int left = i, right = i, count = 0; right + len <= s.size(); right += len) { 使用一个滑动窗口,窗口的左右边界分别由 left 和 right 表示,count 用来计数当前窗口内满足条件的单词数量,也就是有效字符的个数。窗口右边界 right 从 i 开始,每次移动一个单词的长度。

string in = s.substr(right, len); 获取当前右边界指向的单词 in。

hash2[in]++; 更新哈希表 hash2,计算当前窗口中每个单词的出现次数。

if (hash1.count(in) && hash2[in] <= hash1[in]) count++; 如果 in 存在于 hash1 中,并且 hash2[in] 的值不超过 hash1[in] 的值,则增加 count。

if (right - left + 1 > m * len) { 如果当前窗口的大小超过了所有单词串联后的长度,需要缩小窗口。

string out = s.substr(left, len); 获取当前左边界指向的单词 out。

if (hash1.count(out) && hash2[out] <= hash1[out]) count--; 如果 out 存在于 hash1 中,并且 hash2[out] 的值不超过 hash1[out] 的值,则减少 count。

hash2[out]--; left += len; 减少 out 在哈希表 hash2 中的计数,并将左边界向右移动一个单词的长度。

if (count == m) ret.push_back(left); 如果当前窗口内包含 words 中所有单词,则将当前左边界的索引添加到结果向量 ret 中。

时间复杂度和空间复杂度分析 时间复杂度:O(n * m * len),其中 n 是字符串 s 的长度,m 是单词列表 words 的大小,len 是单词的长度。每个窗口最多移动 n/len 次,每次移动需要 O(m * len) 的时间来处理窗口内的单词。

空间复杂度:O(m),主要是哈希表 hash1 和 hash2 的空间开销,它们存储了 words 中每个单词的出现次数。

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""

注意:

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

  • 如果 s 中存在这样的子串,我们保证它是唯一的答案。

示例 1:

输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC" 解释:最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2:

输入:s = "a", t = "a" 输出:"a" 解释:整个字符串 s 是最小覆盖子串。

示例 3:

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

提示:

  • (m == s.length)

  • (n == t.length)

  • 1 <= m, n <= 10(5)

  • st 由英文字母组成

进阶:你能设计一个在 o(m+n) 时间内解决此问题的算法吗?

滑动窗口(同向双指针)优化暴力枚举:

我们需要在[left,right]中判断是否包含t字符串,可以用hash1记录t字符串中不同字符的个数,用hash2记录[left,right]记录字符串中不同字符的个数,再用一个count记录[left,right]中有效的字符个数,我们仅需要判断count是否等于t.size(),就可以直接判断[left,right]中是否包含t字符串。

count记录有效字符的具体做法,我们考虑把right字符添加进区间中,添加right之前count记录是的[left,right-1]的有效字符个数,添加进right后,维护hash2,hash2[in]++。hash2维护之后,如果hash2[in]<=hash2[in],说明新加入进来的字符是有效字符,表示right字符有意义。

我们不断判断所有的子串区间,也就是所有的left和right的组合。找到符合条件的最小区间的长度。

[left,right]当添加进right后,count==m,此时对于left,与right+1,right+2...后面的组合都可以不用考虑了,因为子串的长度一定大于left与right的组合。也就是说对于left的所有组合我们都考虑完毕了。此时left++。

left++后,对于[left,right-1]这个区间的所有组合都不符合条件,所以跳过这个组合,直接从right开始匹配。

然后count==m,对于这个left的所有组合也考虑完毕。以此类推,直到count!=m为止。

left++的时候,需要注意维护hash2和count的意义。

 
class Solution {
public:
    string minWindow(string s, string t) {
        int n = s.size(), m = t.size();
        if (n < m)
            return "";

        int hash1[128] = {0}, hash2[128] = {0};
        for (auto ch : t)
            hash1[ch]++;
        int begin = -1, minlen = INT_MAX;
        for (int left = 0, right = 0, count = 0; right < n; right++) {
            char in = s[right];
            hash2[in]++;
            if (hash2[in] <= hash1[in])
                count++;

            while (count == m) {
                if (right - left + 1 < minlen) {
                    minlen = right - left + 1;
                    begin = left;
                }

                char out = s[left];
                if (hash2[out] <= hash1[out])
                    count--;
                hash2[out]--;
                left++;
            }
        }

        if (begin == -1)
            return "";
        else
            return s.substr(begin, minlen);
    }
};

int n = s.size(), m = t.size(); 获取字符串 s 和 t 的长度。

if (n < m)return ""; 如果字符串 s 的长度小于字符串 t 的长度,返回空字符串,因为无法找到满足条件的窗口。

int hash1[128] = {0}, hash2[128] = {0}; 定义两个哈希表 hash1 和 hash2,用于存储字符串 t 中每个字符的出现次数和当前考察的窗口中每个字符的出现次数。

for (auto ch : t) hash1[ch]++; 遍历字符串 t,更新哈希表 hash1,计算 t 中每个字符的出现次数。

int begin = -1, minlen = INT_MAX; 初始化变量 begin 为-1,表示最小窗口的起始索引,初始化 minlen 为INT_MAX,表示最小窗口的长度。

for (int left = 0, right = 0, count = 0; right < n; right++) { 使用一个滑动窗口,窗口的左右边界分别由 left 和 right 表示,count 用来计数当前窗口内满足条件的字符数量,也就是有效字符数。窗口右边界 right 从0开始,遍历整个字符串 s。

char in = s[right]; 获取当前右边界指向的字符 in。

hash2[in]++; 更新哈希表 hash2,计算当前窗口中每个字符的出现次数。

if (hash2[in] <= hash1[in]) count++; 如果当前字符 in 在窗口中的出现次数不超过它在 t 中的出现次数,则增加 count。

while (count == m) { 如果当前窗口内包含所有 t 中的字符,尝试缩小窗口以找到更小的窗口。

if (right - left + 1 < minlen) { 如果当前窗口大小小于已知的最小窗口大小,更新最小窗口大小和起始索引。

minlen = right - left + 1; begin = left; 更新最小窗口的长度和起始索引。

char out = s[left]; 获取当前左边界指向的字符 out。

if (hash2[out] <= hash1[out]) count--; 如果 out 在窗口中的出现次数不超过它在 t 中的出现次数,减少 count。

hash2[out]--; left++; 减少字符 out 在哈希表 hash2 中的计数,并将左边界向右移动。 if (begin == -1)return "";elsereturn s.substr(begin, minlen);} 如果没有找到合适的窗口,返回空字符串。否则,返回从 begin 开始长度为 minlen 的子字符串。

时间复杂度和空间复杂度分析

时间复杂度:O(n),其中 n 是字符串 s 的长度。尽管有循环嵌套,但每个字符在 s 中只被访问两次(一次是当它进入窗口,一次是当它离开窗口),所以时间复杂度是线性的。

空间复杂度:O(1),因为 hash1 和 hash2 的大小固定为128(ASCII 字符集的大小),不依赖于输入数据的大小,因此可以认为是常数空间。

结尾

最后,感谢您阅读我的文章,希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点,请随时在评论区留言。

 

同时,不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中,我将继续探讨这个话题的不同方面,为您呈现更多深度和见解。

 

谢谢您的支持,期待与您在下一篇文章中再次相遇!

 

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

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

相关文章

【Godot 3.5控件】用TextureProgress制作血条

说明 本文写自2022年11月13日-14日&#xff0c;内容基于Godot3.5。后续可能会进行向4.2版本的转化。 概述 之前基于ProgressBar创建过血条组件。它主要是基于修改StyleBoxFlat&#xff0c;好处是它几乎可以算是矢量的&#xff0c;体积小&#xff0c;所有东西都是样式信息&am…

Mysql学习--深入探究索引和事务的重点要点与考点

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好&#xff0c;我是xiaoxie.希望你看完之后,有不足之处请多多谅解&#xff0c;让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …

基于springboot+vue+Mysql的闲一品交易平台

开发语言&#xff1a;Java框架&#xff1a;springbootJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包&#xff1a;…

2024,产品国际化改造

2024&#xff0c;我们的核心是国际化/信创/多租户/AI融合应用。 作为招投标与即将推进的项目需求&#xff0c;优先对产品进行国际化改造。 1.我们的思考 作为基础平台个性化定制的项目落地模式&#xff0c;我们必须兼顾平台与定制直接的平衡&#xff0c;使整个系统能快速在多…

力扣541. 反转字符串 II

思路&#xff1a;题目的意思就是每2k个字符进行一次循环访问&#xff0c;如果个数小于k就全部反转&#xff0c;如果大于k则只反转k个字符; class Solution {public String reverseStr(String s, int k) {char[] charArray s.toCharArray();int length charArray.length;//每…

DDR4总结最全纯干货分享

DDR存储器发展的主要方向一言以蔽之&#xff0c;是更高速率&#xff0c;更低电压&#xff0c;更密的存储密度&#xff0c;从而实现更好的性能。 DDR4 SDRAM&#xff08;Double Data Rate Fourth SDRAM&#xff09;&#xff1a;DDR4提供比DDR3/ DDR2更低的供电电压1.2V以及更高的…

学会这些Jmeter插件,才能设计出复杂性能测试场景

为什么要使用jmeter线程组插件呢&#xff1f; jmeter自带的线程组插件模拟的压测场景非常有限&#xff0c;当需要模拟复杂压测场景的时候&#xff0c;推荐大家使用jmeter线程组插件。 如何下载jmeter线程组插件呢&#xff1f; 早期版本的jmeter可以针对我们需要的扩展功能&a…

Docker-Container

Docker ①什么是容器②为什么需要容器③容器的生命周期容器 OOM容器异常退出容器暂停 ④容器命令清单总览docker createdocker rundocker psdocker logsdocker attachdocker execdocker startdocker stopdocker restartdocker killdocker topdocker statsdocker container insp…

宏集PLC如何应用于建筑的3D打印?

案例概况 客户&#xff1a;Rebuild 合作伙伴&#xff1a;ASTOR 应用&#xff1a;用于建筑的大尺寸3D打印 应用产品&#xff1a;3D混凝土打印机 一、应用背景 自从20世纪80年代以来&#xff0c;增材制造技术&#xff08;即3D打印&#xff09;不断发展。大部分3D打印技术应…

力扣---零钱兑换---动态规划

思路&#xff1a; 这是一道典型的动态规划问题&#xff08;希望下次不用提示&#xff0c;能直接认出来&#xff09;&#xff1a;我将g[i]定义为总金币为i所需的最少硬币个数。所以递推公式可以表示为&#xff1a;g[i]min(g[i-1],g[i-2],g[i-5])1&#xff0c;也就是g[i]min(g[i-…

简介:网络数据中心和数字孪生系统融合

前言 云服务器是在云中提供可扩展的计算服务&#xff0c;避免了使用传统服务器时需要预估资源用量及前期投入的情况。云服务器支持用户自定义一切资源&#xff1a;cpu、内存、硬盘、网络、安全等等&#xff0c;并可在访问量和负载等需求发生变化时轻松地调整它们。云服务器为业…

算法公式汇总

文章目录 三角函数定义式诱导公式平方关系两角和与差的三角函数积化和差公式和差化积公式倍角公式半角公式万能公式其他公式反三角函数恒等式 三角函数定义式 三角函数 定义式 余切&#xff1a; c o t A 1 t a n A \text { 余切&#xff1a;} \ cotA \frac{1}{tanA} 余切&a…

华为OD机22道试题

华为OD机试题 2.查找小朋友的好朋友位置 在学校中&#xff0c;N 个小朋友站成一队&#xff0c;第 i 个小朋友的身高为 height[i]&#xff0c;第 i 个小朋友可以看到第一个比自己身高更高的小朋友j&#xff0c;那么 j 是 i 的好朋友 (要求&#xff1a;j>i) 。 请重新生成一个…

springboot+itextpdf+thymeleaf+ognl根据静态模版文件实现动态生成pdf文件并导出demo

第一步&#xff1a;导入maven依赖 <!-- 导出为PDF依赖包 --><dependency><groupId>com.itextpdf</groupId><artifactId>itextpdf</artifactId></dependency><dependency><groupId>com.itextpdf</groupId><art…

xAI开发的一款巨大型语言模型(HLM)--Grok 1

在xAI发布Grok的权重和架构之后&#xff0c;很明显大型语言模型&#xff08;LLM&#xff09;的时代已经过去&#xff0c;现在是巨大型语言模型&#xff08;HLM&#xff09;的时代。这个混合专家模型发布了3140亿个参数&#xff0c;并且在Apache 2.0许可下发布。这个模型没有针对…

C++关于类和对象的基础语法

前言&#xff1a; 介绍c中类和对象的基础语法和注意事项&#xff0c;这里是c入门的第一道坎&#xff0c;细节很多&#xff0c;在后面的更深的学习中还会反复提到。 目录 前言&#xff1a; 1.OO语言 2.类的定义 3.类的访问限定符与封装的引入 4.类的实例化 5.关键字this指…

Magic Copy:一键AI抠图,在浏览器中获得任何图像素材

Magic Copy&#xff1a;轻松一点&#xff0c;精准抠图&#xff0c;让创意无限放大&#xff01; - 精选真开源&#xff0c;释放新价值。 概览 Magic Copy&#xff08;AI智能抠图插件&#xff09;是一个创新型的浏览器扩展工具&#xff0c;其独特之处在于能够无缝集成于用户的网…

项目配置之道:优化Scrapy参数提升爬虫效率

前言 在当今信息时代&#xff0c;数据是无处不在且无比重要的资源。为了获取有效数据&#xff0c;网络爬虫成为了一项至关重要的技术。Scrapy作为Python中最强大的网络爬虫框架之一&#xff0c;提供了丰富的功能和灵活的操作&#xff0c;让数据采集变得高效而简单。本文将以爬…

Kafka安装配置

#安装启动之前必须配置好zookeeper 可以参考zookeeper安装配置-CSDN博客 一、下载安装包&#xff0c;并解压 #创建目录 mkdir -p /kafka/{install,data} #进入/kafka/install目录下 cd /kafka/install #下载kafka wget https://archive.apache.org/dist/kafka/3.7.0/kafka_2…

JSONP 实现跨域请求案例

后端使用 express 搭建&#xff0c;案例代码如下&#xff1a; const express require(express)const app express() const PORT 3000app.get(/data, (req, res) > {const jsonData {name: Alan,age: 666,city: GD}const callback req.query.callback // 获取前端中的回…