网站建设任职要求,做网站税率,网站建设柒金手指花总12,宏泰机械网站建设题目链接
力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 题目解析
该题目的意思简而言之就是说#xff0c;从s字符串中寻找与p字符串含有相同字符(次数和种类均相同)的子串#xff0c;并且将他们的首字符下标集合进数组中进行返回。
滑动窗口解…题目链接
力扣LeetCode官网 - 全球极客挚爱的技术成长平台 题目解析
该题目的意思简而言之就是说从s字符串中寻找与p字符串含有相同字符(次数和种类均相同)的子串并且将他们的首字符下标集合进数组中进行返回。
滑动窗口解法(未优化版本)
分析完该题目可以发现该题是一个大小不变的滑动窗口题目。窗口大小一直为p字符串的大小并且我们出窗口和进窗口的大小是相同的就相当于我们拿着一个窗口在s字符串上去滑动直到我们找到合适的子串。
如以下动图所示 代码如下(含详细注释)
// 该题是一个大小固定的滑动窗口题目
class Solution
{
public:// 设计一个函数来检查两个哈希表是否相等bool check_hash(int hash1[],int hash2[]){for(int i0;i26;i)if(hash1[i]!hash2[i]) return false;return true;}vectorint findAnagrams(string s, string p) {int p_hash[26]{0};int s_hash[26]{0};int nss.size();int npp.size();// 将p字符串中的字符插入到p_hash中for(autoe:p) p_hash[e-a];vectorint ret;for(int left0,right0;rightns;right){// 直接将right对应位置字符进行入哈希表char ins[right];s_hash[in-a];// 如果right-left1np说明已经超过我们滑动窗口的大小了if(right-left1np){// 直接从左边进行出窗口char outs[left];s_hash[out-a]--;}// 检查是否符合条件(两个哈希表是否相等)if(check_hash(s_hash,p_hash))// 相等就把该字符串最左边字符的下标入ret数组中ret.push_back(left);}return ret;}
};
滑动窗口(优化版本)
该题只存放了小写字母因此我们检查两个哈希表其实时间复杂度是非常低的倘若存入的不止是小写字母那么我们检查的这一步操作时间复杂度就会非常高并且检查的这一步操作每一次滑动的时候我们都要进行检测因此我们可以使用一个count来记录s_hash哈希表中有效字符(存在的字符是p_hash中的字符)的数量进窗口的时候我们将count出窗口的时候我们将count--。
代码如下(含详细注释)
// 优化版本
// 该题是一个大小固定的滑动窗口题目
class Solution
{
public:vectorint findAnagrams(string s, string p) {int p_hash[26]{0};int s_hash[26]{0};int nss.size();int npp.size();// 将p字符串中的字符插入到p_hash中for(autoe:p) p_hash[e-a];vectorint ret;for(int left0,right0,count0;rightns;right){char ins[right];// 当前字符插入s_hash之后// 如果s_hash中该字符对应的次数p_hash[in-a]// 说明若不是该字符次数在s_hash中的次数与p_hash中的次数一样// 那就是插入之后还比p_hash中的次数少// 无论哪种情况均能说明该字符存在于p_hash中 符合我们要找的字符// 因此count 也就是统计的是s_hash中的有效字符数量if(s_hash[in-a]p_hash[in-a]) count;// 如果right-left1np说明已经超过我们滑动窗口的大小了if(right-left1np){char outs[left];// 这一步同理上一步 // 当我们将该字符移除之前该字符次数在s_hash中小于p_hash// 说明该字符是有效字符// 就算该字符不是我们要的有效字符 仍然可以出窗口 只不过count不进行--操作罢了if(s_hash[out-a]--p_hash[out-a]) count--;}// 如果此时countnp说明当前情况完全满足我们的要求 加入该结果即可if(countnp)ret.push_back(left);}return ret;}
};
