C++のバスケットにフルーツ

木の列があるとすると、i番目のツリーはタイプtree[i]のフルーツを生成します。任意のツリーから開始して、これらの手順を繰り返し実行できます-

• この木から1つの果物をバスケットに追加します。チャンスがない場合は、やめてください。
• 現在のツリーの右側にある次のツリーに移動します。右側に木がない場合は、停止します。

バスケットは2つあり、各バスケットには任意の量の果物を入れることができますが、各バスケットにはそれぞれ1種類の果物のみを入れる必要があります。この手順で収集できる果物の総量を見つける必要がありますか？したがって、ツリーが[0、1、2、2]のような場合、出力は3になります。[1,2,2]を収集できます。最初のツリーから開始すると、[0、 1]

これを解決するには、次の手順に従います-

• n：=ツリーサイズ、j：=0、ans：=0
• 1つのマップを作成するm
• 0からn–1の範囲のiの場合
  • 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
• 回答を返す

理解を深めるために、次の実装を見てみましょう-

例

#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