C ++中的三个相等部分

Z时代
2024-01-10
分类：综合

假设我们有一个0和1的数组A，我们必须将数组分成3个非空部分，以使所有这些部分代表相同的二进制值。如果可能，请返回i + 1 <j的任何[i，j]，这样-

A [0]，A [1]，...，A [i]是第一部分；
A [i + 1]，A [i + 2]，...，A [j-1]是第二部分，并且
A [j]，A [j + 1]，...，A [A.length-1]是第三部分。

所有这三个部分具有相等的二进制值。如果不可能，则返回[-1，-1]。

因此，如果输入类似于[0,1,0,1,1]，则输出将为[0,4]

为了解决这个问题，我们将遵循以下步骤-

定义一个函数getIdx()，它将采用一个数组a，left，right，
while（left <right和a [left]与0相同），执行-

（向左增加1）

而右<(int)a.size()，则执行-

如果a [left]不等于a [right]，则返回-1
（向左增加1），（向右增加1）

向左返回-1
从主要方法中执行以下操作-
定义大小为2的数组ret，以-1填充
num：= 0，n：= A的大小
对于初始化i：= 0，当i <n时，更新（将i增加1），执行-

num：= num + 1（（A [i]等于1），否则为0

如果num mod 3不等于0，则-

返回ret

如果num与0相同，则-

返回{0，2}

要求：= num / 3
idx：= n-1
对于初始化temp：= 0，当idx> = 0且temp <req时，更新（将idx减少1），执行

temp：= temp + 1，当（A [idx]等于1）时，否则为0

（将idx增加1）
firstEnd：= getIdx(A,0,idx)
如果firstEnd <0，则-

返回ret

secondEnd：= getIdx（A，firstEnd + 1，idx）
如果secondEnd <0，则-

返回ret

返回{firstEnd，secondEnd + 1}

让我们看下面的实现以更好地理解-

示例

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