做网站爬闪,钢板出租铺路钢板出租,东莞网站制作推广公司,网站架构师招聘题意大致是#xff0c;给定两个字符串#xff0c;s 和 p 其中 要在s 中找到由p的元素组成的子字符串#xff0c;记录子字符串首地址 class Solution {
public:vectorint findAnagrams(string s, string p) {int m s.size(), n p.size();if(m n)return {};vec… 题意大致是给定两个字符串s 和 p 其中 要在s 中找到由p的元素组成的子字符串记录子字符串首地址 class Solution {
public:vectorint findAnagrams(string s, string p) {int m s.size(), n p.size();if(m n)return {};vectorint hashTable(26);for(auto ch : p){hashTable[ch - a];}vectorint ret;/*手动移动滑动窗口右边界如果是新元素循环循环移动左边界直到找到右边的那个元素如果串口长度于p的长度一致达成条件*/for(int l 0, r 0; r m; r){hashTable[s[r] - a]--;while(hashTable[s[r] - a] 0){hashTable[s[l] - a];l;}if(r - l 1 n){ret.push_back(l);}}return ret;}
};其实很容易想到滑动窗口
这道题解的思路是先把p的所有元素记录下来然后开始遍历滑动串口的右边界直接hashTable[s[r]]–; 如果其值 0 说明遍历的滑动窗口s的子串)有p 的元素不管 继续移动右窗口直到滑出边界 如果 0 说明 新元素此时右边界不能动动左边界左边界怎么动呢就是左边界不断加元素不断右移最后把新元素添加进去了。 在窗口滑动的过程中如果满足 r - l 1 n 说明找到了一个满足 p 的子字符串。
//还有一个
// 思想是一样的但是看着会比较啰嗦class Solution {
public:vectorint findAnagrams(string s, string p) {unordered_mapchar, int mp;vectorint result;int s_len s.size(), p_len p.size();for(auto c : p){mp[c];}int left 0, right 0, count p_len;// 初始化滑动窗口while(right p_len){if(mp.count(s[right]) 0 mp[s[right]] 0){count--;}mp[s[right]]--;right;}if(count 0){result.push_back(left);}//移动滑动窗口while(right s_len){if(mp.count(s[left]) 0 mp[s[left]] 0){count;}mp[s[left]];left;if(mp.count(s[right]) 0 mp[s[right]] 0){count--;}mp[s[right]]--;right;if(count 0){result.push_back(left);}}return result;}
};
