用 C++ 将水果放入篮子
c++server side programmingprogramming
假设我们有一排树，第 i 棵树结出的水果类型为 tree[i]。我们可以从任意一棵树开始，然后重复执行这些步骤 −
- 将这棵树上的一个水果放入篮子。如果没有机会，则停止。
- 移至当前篮子右侧的下一棵树。如果右侧没有树，则停止。
我们有两个篮子，每个篮子可以装任意数量的水果，但我们希望每个篮子只能装一种水果。我们必须找出通过此过程可以收集的水果总量?因此，如果树的大小为 [0, 1, 2, 2]，则输出将为 3。我们可以收集 [1,2,2]，如果我们从第一棵树开始，那么我们只会收集 [0, 1]
为了解决这个问题，我们将遵循以下步骤 −
- n := 树大小，j := 0，ans := 0
- 创建一个映射 m
- 对于 i，范围为 0 到 n – 1
- 将 m[tree[i]] 增加 1
- 当 m 的大小 > 2 且 j <= i，则
- 将 m[tree[j]] 减少 1
- 如果 m[tree[j]] = 0，则从 m 中删除 tree[j]
- 将 j 增加 1
- ans := i – j + 1 和 ans 的最大值
- return ans
让我们看看下面的实现以便更好地理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int totalFruit(vector<int>& tree) {
int n = tree.size();
int j = 0;
map <int, int> m;
int ans = 0;
for(int i = 0; i < n; i++){
m[tree[i]] += 1;
while(m.size() > 2 && j <= i){
m[tree[j]]--;
if(m[tree[j]] == 0)m.erase(tree[j]);
j++;
}
ans = max(i - j + 1, ans);
}
return ans;
}
};
main(){
vector<int> v = {3,3,3,1,2,1,1,2,3,3,4};
Solution ob;
cout <<(ob.totalFruit(v));
}
输入
[3,3,3,1,2,1,1,2,3,3,4]
输出
5
