C ++中的三个相等部分
假设我们有一个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
如果nummod3不等于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));
}输入项
{0,1,0,1,1}输出结果
[1, 4, ]