Ba phần bằng nhau trong C ++

Giả sử chúng ta có một mảng A gồm các số 0 và 1, chúng ta phải chia mảng thành 3 phần không rỗng sao cho tất cả các phần này biểu diễn cùng một giá trị nhị phân. Nếu có thể, hãy trả về bất kỳ [i, j] nào với i + 1

• A [0], A [1], ..., A [i] là phần đầu tiên;

• A [i + 1], A [i + 2], ..., A [j-1] là phần thứ hai và

• A [j], A [j + 1], ..., A [A.length - 1] là phần thứ ba.

Cả ba phần đều có giá trị nhị phân bằng nhau. Nếu không được, hãy trả về [-1, -1].

Vì vậy, nếu đầu vào là [0,1,0,1,1], thì đầu ra sẽ là [0,4]

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

• Xác định một hàm getIdx (), điều này sẽ lấy một mảng a, left, right,

• while (left

  • (tăng bên trái 1)

• while right <(int) a.size (), do -

  • nếu [trái] không bằng [phải] thì trả về -1

  • (tăng bên trái 1), (tăng bên phải 1)

• quay lại bên trái - 1

• Từ phương thức chính, hãy làm như sau -

• Xác định ret mảng có kích thước 2, điền vào giá trị này bằng -1

• num:=0, n:=kích thước của A

• để khởi tạo i:=0, khi i

  • num:=num + 1 khi (A [i] giống với 1), nếu không thì 0

• nếu num mod 3 không bằng 0, thì -

  • trả lại ret

• nếu num giống 0 thì -

  • trả về {0, 2}

• yêu cầu:=num / 3

• idx:=n - 1

• để khởi tạo temp:=0, khi idx> =0 và temp

  • temp:=temp + 1 khi (A [idx] giống với 1), nếu không thì 0

• (tăng idx lên 1)

• firstEnd:=getIdx (A, 0, idx)

• if firstEnd <0, then -

  • trả lại ret

• secondEnd:=getIdx (A, firstEnd + 1, idx)

• if secondEnd <0, then -

  • trả lại ret

• trả về {firstEnd, secondEnd + 1}

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;
void print_vector(vector<auto> v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << v[i] << ", ";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   vector<int> threeEqualParts(vector<int>& A){
      vector<int> ret(2, -1);
      int num = 0;
      int n = A.size();
      for (int i = 0; i < n; i++) {
         num += (A[i] == 1);
      }
      if (num % 3 != 0)
         return ret;
      if (num == 0) {
         return { 0, 2 };
      }
      int req = num / 3;
      int idx = n - 1;
      for (int temp = 0; idx >= 0 && temp < req; idx--) {
         temp += A[idx] == 1;
      }
      idx++;
      int firstEnd = getIdx(A, 0, idx);
      if (firstEnd < 0)
         return ret;
      int secondEnd = getIdx(A, firstEnd + 1, idx);
      if (secondEnd < 0)
         return ret;
      return { firstEnd, secondEnd + 1 };
   }
   int getIdx(vector<int>& a, int left, int right){
      while (left < right && a[left] == 0)
      left++;
      while (right < (int)a.size()) {
         if (a[left] != a[right])
            return -1;
         left++;
         right++;
      }
      return left - 1;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,1,0,1,1};
   print_vector(ob.threeEqualParts(v));
}

Đầu vào

{0,1,0,1,1}

Đầu ra

[1, 4, ]