目录
1、水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组
fruits表示，其中fruits[i]是第i棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组
fruits，返回你可以收集的水果的 最大 数目。示例 1：
输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。示例 2：
输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。示例 3：
输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。
解题代码：
class Solution {
public:
int totalFruit(vector<int>& f) {
int len=f.size();
//定义一个哈希表
unordered_map<int,int> hash;
int ret=0;
for(int left=0,right=0;right<len;right++)
{
//进窗口
hash[f[right]]++;
//出窗口
while(left<len&&hash.size()>2)
{
hash[f[left]]--;
if(hash[f[left]]==0) hash.erase(f[left]);
left++;
}
//更新结果
ret=max(ret,right-left+1);
}
return ret;
}
};代码小优化：
class Solution {
public:
int totalFruit(vector<int>& f) {
int len=f.size();
int hash[100001]={0};
int ret=0;
for(int left=0,right=0,kinds=0;right<len;right++)
{
if(hash[f[right]]==0) kinds++;
hash[f[right]]++;//进窗口
while(left<len&&kinds>2)//出窗口
{
hash[f[left]]--;
if(hash[f[left]]==0) kinds--;
left++;
}
ret=max(ret,right-left+1);//更新结果
}
return ret;
}
};2、找到字符串中所有字母异位词
给定两个字符串
s和p，找到s中所有p的异位词
的子串，返回这些子串的起始索引。不考虑答案输出的顺序。示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。示例 2:
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
解题代码：
class Solution {
public:
bool check(int* hash1,int* hash2)
{
for(int i=0;i<26;i++)
{
if(hash1[i]!=hash2[i])
return false;
}
return true;
}
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int hash1[26]={0};
int hash2[26]={0};
for(auto e:p) hash1[e-'a']++;
int len1 =p.size();
int len2 =s.size();
for(int left=0,right=0;right<len2;right++)
{
hash2[s[right]-'a']++;//进窗口
if(right-left+1>len1)//判断是否出窗口
{
hash2[s[left]-'a']--;
left++;
}
if(check(hash1,hash2)) ret.push_back(left);//更新结果
}
return ret;
}
};
优化判断后的代码：
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int hash1[26]={0},hash2[26]={0};
for(auto e:p) hash1[e-'a']++;
int len1 =p.size(),len2 =s.size();
int count=0;//记录有效字符的个数
for(int left=0,right=0;right<len2;right++)
{
hash2[s[right]-'a']++;//进窗口
if(hash2[s[right]-'a']<=hash1[s[right]-'a']) count++;
if(right-left+1>len1)//判断是否出窗口
{
if(hash2[s[left]-'a']<=hash1[s[left]-'a']) count--;
hash2[s[left++]-'a']--;
}
if(count==len1) ret.push_back(left);//更新结果
}
return ret;
}
};3、串联所有单词的子串
给定一个字符串
s和一个字符串数组words。words中所有字符串 长度相同。
s中的 串联子串 是指一个包含words中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果
words = ["ab","cd","ef"]， 那么"abcdef"，"abefcd"，"cdabef"，"cdefab"，"efabcd"， 和"efcdab"都是串联子串。"acdbef"不是串联子串，因为他不是任何words排列的连接。返回所有串联子串在
s中的开始索引。你可以以 任意顺序 返回答案。示例 1：
输入：s = "barfoothefoobarman", words = ["foo","bar"] 输出：[0,9]解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。 子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。 子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。 输出顺序无关紧要。返回 [9,0] 也是可以的。示例 2：
输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]输出：[]解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。 s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。 所以我们返回一个空数组。示例 3：
输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"] 输出：[6,9,12] 解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。 子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。 子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。 子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
解题代码：
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
vector<int> ret;//记录结果
int len=words[0].size();
unordered_map<string,int> hash1;
//将words的字符串放入hash1
for(auto& e:words) hash1[e]++;
for(int i=0;i<len;i++)//进行len次滑动窗口
{
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++;//维护count
if(right-left+1>words.size()*len)
{
string out=s.substr(left,len);
if(hash1.count(out)&&hash2[out]<=hash1[out]) count--;//维护count
hash2[out]--;//出窗口
left+=len;
}
if(count==words.size()) ret.push_back(left);//更新结果
}
}
return ret;
}
};4、最小覆盖子串
给你一个字符串
s、一个字符串t。返回s中涵盖t所有字符的最小子串。如果s中不存在涵盖t所有字符的子串，则返回空字符串""。注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。- 如果
s中存在这样的子串，我们保证它是唯一的答案。示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
解题代码：
class Solution {
public:
string minWindow(string s, string t) {
int len=INT_MAX,begin=-1;//记录子串长度和结果起始位置
int hash1[128]={0};
int hash2[128]={0};
for(auto ch:t) hash1[ch]++;
for(int left=0,right=0,count=0;right<s.size();right++)
{
char in=s[right];
hash2[in]++;//进窗口
if(hash2[in]<=hash1[in]) count++;//维护 count
while(count>=t.size())
{
if(len>right-left+1)
{
len=right-left+1;//更新len
begin=left;//更新结果
}
char out=s[left++];
if(hash1[out]&&hash2[out]<=hash1[out]) count--;// count
if(hash1[out]) hash2[out]--;//出窗口
}
}
return begin==-1?"":s.substr(begin,len);
}
};