927. Three Equal Parts

Given an array `A` of `0`s and `1`s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any `[i, j]` with `i+1 < j`, such that:

• `A[0], A[1], ..., A[i]` is the first part;
• `A[i+1], A[i+2], ..., A[j-1]` is the second part, and
• `A[j], A[j+1], ..., A[A.length - 1]` is the third part.
• All three parts have equal binary value.

If it is not possible, return `[-1, -1]`.

Note that the entire part is used when considering what binary value it represents.  For example, `[1,1,0]` represents `6` in decimal, not `3`.  Also, leading zeros are allowed, so `[0,1,1]` and `[1,1]` represent the same value.

Example 1:

``````Input: [1,0,1,0,1]
Output: [0,3]
``````

Example 2:

``````Input: [1,1,0,1,1]
Output: [-1,-1]
``````

Note:

1. `3 <= A.length <= 30000`
2. `A[i] == 0` or `A[i] == 1`

``````class Solution {
public:
vector<int> threeEqualParts(vector<int>& A) {
int cntOne = 0, n = A.size();
for (int num : A) {
if (num == 1) ++cntOne;
}
if (cntOne == 0) return {0, n - 1};
if (cntOne % 3 != 0) return {-1, -1};
int idxThird = 0, cnt = 0;
for (int i = n - 1; i >= 0; --i) {
if (A[i] == 0) continue;
++cnt;
if (cnt == cntOne / 3) {
idxThird = i;
break;
}
}
int idx1 = helper(A, 0, idxThird);
if (idx1 < 0) return {-1, -1};
int idx2 = helper(A, idx1 + 1, idxThird);
if (idx2 < 0) return {-1, -1};
return {idx1, idx2 + 1};
}
int helper(vector<int>& A, int left, int right) {
while (A[left] == 0) ++left;
while (right < A.size()) {
if (A[left] != A[right]) return -1;
++left; ++right;
}
return left - 1;
}
};
``````

``````class Solution {
public:
vector<int> threeEqualParts(vector<int>& A) {
int cntOne = 0, n = A.size();
for (int num : A) {
if (num == 1) ++cntOne;
}
if (cntOne == 0) return {0, n - 1};
if (cntOne % 3 != 0) return {-1, -1};
int k = cntOne / 3, start = 0, mid = 0, end = 0, cnt = 0;
for (int i = 0; i < n; ++i) {
if (A[i] == 0) continue;
if (cnt == 0) start = i;
++cnt;
if (cnt == k + 1) mid = i;
if (cnt == 2 * k + 1) {end = i; break;}
}
while (end < n && A[start] == A[mid] && A[mid] == A[end]) {
++start; ++mid; ++end;
}
if (end == n) return {start - 1, mid};
return {-1, -1};
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/927

https://leetcode.com/problems/three-equal-parts/