当前位置: 首页> 游戏> 单机 > 拍摄制作宣传片企业_购物网页版_电池优化大师下载_网站排名怎么优化

拍摄制作宣传片企业_购物网页版_电池优化大师下载_网站排名怎么优化

时间:2025/7/9 15:12:12来源:https://blog.csdn.net/qq_73586673/article/details/145671359 浏览次数:0次
拍摄制作宣传片企业_购物网页版_电池优化大师下载_网站排名怎么优化

题目:

给定两个字符串 s 和 p,找到 s 中所有 p 的 

异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。

示例 1:

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

 示例 2:

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

分析:

借鉴了力扣49题的思路,拼接p中字符和字符出现次数来作为判断异位词的条件。从头开始遍历,计算s字符串中当前下标以及当前下标+p.length()-1之间字符的出现次数,进行拼接,与p的拼接结果进行比较,相同则保存当前下标。

这种方法虽然能通过但是太慢,每次都要拼接,都要进行一个26次的循环。

改进:

49题进行拼接是因为要在一堆字符串中找出其中的异位词组,所以要用拼接的结果作为unordered_map的键值,去和异位词做映射,保存拼接结果与键值相同的异位词。这题并不不需要,题目已经给出要找的字符串,所以直接比较字符出现次数就行。

采用滑动窗口,由于已经给出要查找的字符串,那么滑动窗口的大小就确定,是p的长度。在s和p中,都先从头开始,计算窗口大小字符串中字符的出现次数,保存在数组(scount,pcount)中(字符与下标映射)。然后s开始滑动:将窗口的首元素滑出,同时改变数组中该字符对应下标的元素的值(-1),然后将新字符加入滑动窗口,同理,改变scount数组中该字符对应下标的元素的值(+1)。滑动完一次,比较一次sount数组与pcount数组,相同则将窗口首元素在字符串中对应的下标保存。

代码:

class Solution {public:vector<int> findAnagrams(string s, string p) {vector<int>res;vector<int>scount(26);vector<int>pcount(26);for(int i=0;i<p.length();++i){scount[s[i]-'a']++;pcount[p[i]-'a']++;}if(scount==pcount){res.push_back(0);}for(int i=0;i<(s.length()-p.length());++i){//移除滑动窗口队头,增加新元素--scount[s[i]-'a'];++scount[s[i+p.length()]-'a'];if(scount==pcount){res.push_back(i+1);}}return res;}};

关键字:拍摄制作宣传片企业_购物网页版_电池优化大师下载_网站排名怎么优化

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: