用 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