文章目录
- 一、水果成篮
- 1、题目讲解
- 2、讲解算法思路
- 3、代码实现
- 二、找到字符串中所有字母异位词
- 1、题目讲解
- 2、讲解算法思路
- 3、代码实现
- 三、串联所有单词的子串
- 1、题目讲解
- 2、讲解算法思路
- 3、代码实现
- 四、最小覆盖子串
- 1、题目讲解
- 2、讲解算法思路
- 3、代码实现
一、水果成篮
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);}};