用 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

相关文章