一、水果成篮
1、题目讲解
2、讲解算法思路
3、代码实现
class Solution { public: int totalFruit(vector<int>& f) { int n=f.size(); unordered_map<int,int> hash; int ret=0; for(int left=0,right=0;right<n;right++) { hash[f[right]]++; while(hash.size()>2) { hash[f[left]]--; if(hash[f[left]]==0) { hash.erase(f[left]); } left++; } ret=max(ret,right-left+1); } return ret; } };
二、找到字符串中所有字母异位词
1、题目讲解
2、讲解算法思路
3、代码实现
class Solution { public: vector<int> findAnagrams(string s, string p) { vector<int> ret; int hash1[256]={0},len=p.size(); for(char ch:p) hash1[ch]++; int hash2[256]={0}; for(int left=0,right=0,count=0;right<s.size();right++) { char in=s[right]; hash2[in]++; if(hash2[in]<=hash1[in]) count++; if(right-left+1>len) { char out=s[left]; if(hash2[out]<=hash1[out]) count--; hash2[out]--; left++; } if(count==len) { ret.push_back(left); } } return ret; } };
三、串联所有单词的子串
1、题目讲解
2、讲解算法思路
3、代码实现
class Solution { public: vector<int> findSubstring(string s, vector<string>& words) { vector<int> ret; unordered_map<string,int> hash1; for(auto ch:words) { hash1[ch]++; } 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>len*m) { 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; } };
四、最小覆盖子串
1、题目讲解
2、讲解算法思路
3、代码实现
代码一
class Solution { public: string minWindow(string s, string t) { int hash1[256]={0}; int kinds=0; for(auto ch:t) { if(hash1[ch]==0) kinds++; hash1[ch]++; } int hash2[256]={0}; int minlen=INT_MAX,begin=-1; for(int left=0,right=0,count=0;right<s.size();right++) { char in=s[right]; hash2[in]++; if(hash2[in]==hash1[in]) count++; while(count==kinds) { if(right-left+1<minlen) { minlen=right-left+1; begin=left; } char out=s[left++]; if(hash2[out]--==hash1[out]) count--; } } if(begin==-1) return ""; else return s.substr(begin,minlen); } };
代码二 不使用kinds来计算种类
class Solution { public: string minWindow(string s, string t) { int hash1[256]={0},n=t.size(); for(char ch:t) { hash1[ch]++; } int begin=-1,len=INT_MAX; int hash2[256]={0}; for(int left=0,right=0,count=0;right<s.size();right++) { char in=s[right]; hash2[in]++; if(hash2[in]<=hash1[in]) count++; while(count==n) { if(right-left+1<len) { begin=left; len=right-left+1; } char out=s[left]; if(hash2[out]<=hash1[out]) count--; hash2[out]--; left++; } } if(begin==-1) return ""; else return s.substr(begin,len); } };
