多语言外贸网站,做彩票网站代理赚钱吗,wordpress+写php页面,深圳龙华区龙华街道高坳新村AC截图 题目 思路
我一开始是打算将窗口内的s子字符串和p字符串都重新排序#xff0c;然后判断是否相等#xff0c;再之后进行窗口滑动。不过缺点是会超时。
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint vec;if(s.siz…AC截图 题目 思路
我一开始是打算将窗口内的s子字符串和p字符串都重新排序然后判断是否相等再之后进行窗口滑动。不过缺点是会超时。
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint vec;if(s.size()p.size()){return vec;}int lenp.size();sort(p.begin(),p.end());for(int i0;is.size()-len;i){string ss s.substr(i,len);sort(ss.begin(),ss.end());if(pss){vec.push_back(i);}}return vec;}
};
后面改用滑动窗口
因为字符串 p 的异位词的长度一定与字符串 p 的长度相同所以我们可以在字符串 s 中构造一个长度为与字符串 p 的长度相同的滑动窗口并在滑动中维护窗口中每种字母的数量当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时则说明当前窗口为字符串 p 的异位词。 关键部分在此 //开始让窗口进行滑动for(int i0;isLen-pLen;i){ //i是滑动前的首位--scount[s.charAt(i) -a]; //将滑动前首位的词频删去scount[s.charAt(ipLen) -a]; //增加滑动后最后一位的词频以此达到滑动的效果//判断滑动后处是否有异位词if(scountpcount){vec.push_back(i1);} } 代码
class Solution {
public:vectorint findAnagrams(string s, string p) {vectorint vec;if(s.size()p.size()){return vec;}int plenp.size();int slens.size();vectorint scount(26);vectorint pcount(26);for(int i0;iplen;i){pcount[p[i]-a];scount[s[i]-a];}if(scountpcount){vec.push_back(0);}for(int i0;islen-plen;i){scount[s[i]-a]--;scount[s[iplen]-a];if(scountpcount){vec.push_back(i1);}}return vec;}
};
