目录
方法4:四个变量分别充当篮子和篮子中水果的个数(最快!!!)
1.题目
https://leetcode.cn/problems/fruit-into-baskets/
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组
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] 这五棵树。提示：
1 <= fruits.length <= 10^50 <= fruits[i] < fruits.length
2.分析
需要使用set来统计[left,right]之间水果的种类数
方法1:暴力枚举
class Solution {
public:
int totalFruit(vector<int>& fruits)
{
int left=0,right=0,ret=0;
for (;left<fruits.size();left++)
{
set<int> mp;
for (right=left;right<fruits.size();right++)
{
mp.insert(fruits[right]);
if (mp.size()>2)
break;
}
ret=max(ret,right-left);
}
return ret;
}
};提交结果:超时
方法2:暴力解法的优化:滑动窗口
right不用每次都从left开始枚举,以这个为例:[1,2,1,2,3,2,3,3]
当mp.size()>2时,
left只需要向前移动,直到mp.size()2时停止移动,能减少大量无用的循环,提高运行速度
使用存储双关键字类型的map<int,int>,第一个关键字存储类型,第二个关键字存储每类的水果的个数
可以先mp[fruits[right]]++(进窗口),看看mp.size()有没有超过2,如果超过,使mp[fruits[left++]]--(出窗口),如果发现减到0了,就erase(注:erase直接删除掉节点的所有信息, 不是让mp[x]置为0)
最后更新结果:ret=max(ret,right-left+1);
代码
class Solution {
public:
int totalFruit(vector<int>& fruits)
{
map<int,int> mp;
int left=0,right=0,ret=0;
for (;right<fruits.size();right++)
{
mp[fruits[right]]++;
while (mp.size()==3)
{
mp[fruits[left++]]--;
if (mp[fruits[left-1]]==0)
mp.erase(fruits[left-1]);
}
ret=max(ret,right-left+1);
}
return ret;
}
};
提交结果:
当然也可以使用unordered_map解决:
但无论是map还是unordered_map对mp多次插入和删除比较耗时,时间复杂度较高,可以使用方法3:数组充当哈希表
方法3:优化方法2:使用数组充当哈希表
要多用一个变量kind来存储水果种类的数量,因为1 <= fruits.length <= 10^5 使用哈希数组hash[100001]来存储,哈希数组的特点正好符合对双关键字的要求,对于种类为x的水果,其个数为hash[x]
kind++的条件:hash[fruit[right]]从0变成1
kind--的条件:hash[fruit[right]]从1变成0
class Solution {
public:
int totalFruit(vector<int>& fruits)
{
int hash[100001]={0};
int left=0,right=0,ret=0,kind=0;
for (;right<fruits.size();right++)
{
hash[fruits[right]]++;
if (hash[fruits[right]]==1)
kind++;
while (kind==3)
{
hash[fruits[left++]]--;
if (hash[fruits[left-1]]==0)
kind--;
}
ret=max(ret,right-left+1);
}
return ret;
}
};提交结果:
方法4:四个变量分别充当篮子和篮子中水果的个数(最快!!!)
bkt1存储篮子1的水果种类数,篮子1的水果个数为bkt1_num(bkt为basket的简写)
bkt2存储篮子2的水果种类数,篮子1的水果个数为bkt2_num
代码
class Solution {
public:
int totalFruit(vector<int>& fruits)
{
int bkt1 = -1, bkt2 = -1, bkt1_num = 0, bkt2_num = 0;
int left = 0, right = 0, ret = 0;
for (; right < fruits.size(); right++)
{
if (bkt1 == -1)
{
bkt1 = fruits[right];
bkt1_num++;
}
else if (bkt2 == -1&&fruits[right]!=bkt1)
{
bkt2 = fruits[right];
bkt2_num++;
}
else
{
if (fruits[right] == bkt1)
bkt1_num++;
else if (fruits[right] == bkt2)
bkt2_num++;
else//如果出现第三种水果
{
while (1)
{
if (fruits[left] == bkt1)
bkt1_num--;
else
bkt2_num--;
left++;
if (bkt1_num == 0)
{
bkt1 = fruits[right];
bkt1_num++;
break;
}
if (bkt2_num == 0)
{
bkt2 = fruits[right];
bkt2_num++;
break;
}
}
}
}
ret = max(ret, right - left + 1);
}
return ret;
}
};容易忽略的点
else if (bkt2 == -1&&fruits[right]!=bkt1)的fruits[right]!=bkt1不可以省,否则将无法通过[0,0,1,1]测试用例
提交结果:
