Fruit Into Baskets trong C ++

Giả sử chúng ta có một hàng cây, cây thứ i cho quả với cây loại [i]. chúng ta có thể bắt đầu ở bất kỳ cây nào mà chúng ta chọn, sau đó thực hiện lặp đi lặp lại các bước này -

Thêm một phần trái cây từ cây này vào giỏ của chúng tôi. Nếu không còn cơ hội, hãy dừng lại.
Di chuyển đến cây tiếp theo ở bên phải của cây hiện tại. Nếu không có cây ở bên phải thì dừng lại.

Chúng tôi có hai giỏ, và mỗi giỏ có thể đựng bất kỳ số lượng trái cây nào, nhưng chúng tôi muốn mỗi giỏ chỉ nên đựng một loại trái cây mỗi loại. Ta phải tìm tổng số quả mà ta thu được bằng thủ tục này? Vì vậy, nếu các cây giống như [0, 1, 2, 2], thì đầu ra sẽ là 3. Chúng ta có thể thu thập [1,2,2], nếu chúng ta bắt đầu từ cây đầu tiên, thì chúng ta sẽ chỉ thu thập [0, 1]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

n:=kích thước cây, j:=0, ans:=0
tạo một bản đồ m
cho tôi trong phạm vi từ 0 đến n - 1
- tăng m [tree [i]] lên 1
- trong khi kích thước của m là> 2 và j <=i, thì
  - giảm m [tree [j]] đi 1
  - nếu m [tree [j]] =0, thì hãy xóa tree [j] khỏi m
  - tăng j lên 1
- ans:=max của i - j + 1 và ans
trả lại ans

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

[3,3,3,1,2,1,1,2,3,3,4]

Fruit Into Baskets trong C ++

Ví dụ

Đầu vào

Đầu ra