滑动窗口_水果成篮_C++
1.题目解析
leetcode链接:https://leetcode.cn/problems/fruit-into-baskets/description/
你正在探访一家农场,农场从左到右种植了一排果树。这些树用一个整数数组 fruits
表示,其中 fruits[i]
是第 i
棵树上的水果种类 。
你想要尽可能多地收集水果。然而,农场的主人设定了一些严格的规矩,你必须按照要求采摘水果:
- 你只有两个篮子,并且每个篮子只能装单一类型的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘,你必须从每棵树(包括开始采摘的树)上恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次,你将会向右移动到下一棵树,并继续采摘。
- 一旦你走到某棵树前,但水果不符合篮子的水果类型,那么就必须停止采摘。
给你一个整数数组fruits
,返回你可以收集的水果的最大数目。
示例 1:
输入:fruits = [1,2,1]
输出:3
解释:可以采摘全部 3 棵树。
示例 2:
输入:fruits = [0,1,2,2]
输出:3
解释:可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘,则只能采摘 [0,1] 这两棵树。
问题本质:
- 在一个数组中,找出一段最长连续区域,这个区域中最多只能含两种类型的水果。
2.算法原理
1. 暴力解法:
- 暴力枚举+哈希表。
- 由
left
和right
维护一段区间,right
不断向右移,先遇到1,将1放入哈希表。再移动到2,将2放入哈希表,移动到3时,发现哈希表中的已经有两种水果了,记录当前的区间长度。 - 之后右移
left
,让right = left
返回,继续开始下一次遍历。
2. 滑动窗口:
- 对暴力解法进行优化,
right
没有必要返回。
- 当
right
走到3时,哈希表中已经有两种水果了。需要右移left
,让哈希表中,1水果的数量--
,如果该水果的数量减到0了,就需要让该水果从哈希表中去除。在右移left
的过程中,有两种情况:- 右移没有导致哈希表中水果种类数的减少,继续右移;
- 右移导致哈希表中水果的种类数减少了,令
right = left
,从该位置继续遍历。
3.编写代码
1. unordered_map版:
class Solution {
public:
int totalFruit(vector<int>& f)
{
unordered_map<int, int> hash; // 统计窗口内出现了多少种水果
int ret = 0;
for(int left = 0, right = 0; right < f.size(); 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;
}
};
2. 用数组模拟哈希表(比容器更快):
kinds
表示当前哈希表中水果的种类数。
class Solution {
public:
int totalFruit(vector<int>& f)
{
int hash[100001] = {0}; // 统计窗口内出现了多少种水果
int ret = 0;
for(int left = 0, right = 0, kinds = 0; right < f.size(); right++)
{
if(hash[f[right]] == 0) kinds++; // 维护水果的种类
hash[f[right]]++; // 进窗口
while(kinds > 2) // 判断
{
// 出窗口
hash[f[left]]--;
if(hash[f[left]] == 0) kinds--;
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
原文地址:https://blog.csdn.net/weixin_73870552/article/details/134170849
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!