https://leetcode.com/problems/three-equal-parts/
Approach 1: Equal Ones
https://www.jianshu.com/p/c8dbaaf87644
Given an array
A of 0s and 1s, 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, andA[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:
3 <= A.length <= 30000A[i] == 0orA[i] == 1
Each part has to have the same number of ones in their representation. The algorithm given below is the natural continuation of this idea.
Algorithm
Say
S is the number of ones in A. Since every part has the same number of ones, they all should have T = S / 3 ones.
If
S isn't divisible by 3, the task is impossible.
We can find the position of the 1st, T-th, T+1-th, 2T-th, 2T+1-th, and 3T-th one. The positions of these ones form 3 intervals:
[i1, j1], [i2, j2], [i3, j3]. (If there are only 3 ones, then the intervals are each length 1.)
Between them, there may be some number of zeros. The zeros after
j3 must be included in each part: say there are z of them (z = S.length - j3).
So the first part,
[i1, j1], is now [i1, j1+z]. Similarly, the second part, [i2, j2], is now [i2, j2+z].
If all this is actually possible, then the final answer is
[j1+z, j2+z+1].- Time Complexity: , where is the length of
S. - Space Complexity: .
public int[] threeEqualParts(int[] A) {
int[] IMP = new int[] { -1, -1 };
int N = A.length;
int S = 0;
for (int x : A)
S += x;
if (S % 3 != 0)
return IMP;
int T = S / 3;
if (T == 0)
return new int[] { 0, N - 1 };
int i1 = -1, j1 = -1, i2 = -1, j2 = -1, i3 = -1, j3 = -1;
int su = 0;
for (int i = 0; i < N; ++i) {
if (A[i] == 1) {
su += 1;
if (su == 1)
i1 = i;
if (su == T)
j1 = i;
if (su == T + 1)
i2 = i;
if (su == 2 * T)
j2 = i;
if (su == 2 * T + 1)
i3 = i;
if (su == 3 * T)
j3 = i;
}
}
// The array is in the form W [i1, j1] X [i2, j2] Y [i3, j3] Z
// where [i1, j1] is a block of 1s, etc.
int[] part1 = Arrays.copyOfRange(A, i1, j1 + 1);
int[] part2 = Arrays.copyOfRange(A, i2, j2 + 1);
int[] part3 = Arrays.copyOfRange(A, i3, j3 + 1);
if (!Arrays.equals(part1, part2))
return IMP;
if (!Arrays.equals(part1, part3))
return IMP;
// x, y, z: the number of zeros after part 1, 2, 3
int x = i2 - j1 - 1;
int y = i3 - j2 - 1;
int z = A.length - j3 - 1;
if (x < z || y < z)
return IMP;
return new int[] { j1 + z, j2 + z + 1 };
}
https://leetcode.com/problems/three-equal-parts/discuss/183902/Java-O(n)-Solution// The solution can be optimized to O(1) space, by not using StringBuilder, but only record the index of the first one digit of the right part.
public int[] threeEqualParts(int[] A) {
if (A == null || A.length < 3) return new int[] {-1, -1};
int n = A.length;
int cntOneBit = 0;
for (int b : A) {
if (b == 1) cntOneBit++;
}
if (cntOneBit % 3 != 0) return new int[] {-1, -1};
int cnt = cntOneBit / 3;
if (cnt == 0) return new int[] {0, n - 1};
//construct the string using the right most part;
int j = n - 1, cntR = 0;
StringBuilder suffix = new StringBuilder();
for (;j >= 0 && cntR < cnt; j--) {
suffix.append(A[j]);
if (A[j] == 1) cntR++;
}
String target = suffix.reverse().toString();
//matching the left part with target string, omit all leading zero
int i = 0;
while (A[i] == 0) i++;
int k = 0;
while (k < target.length()) {
if (A[i + k] == target.charAt(k) - '0') k++;
else return new int[] {-1, -1};
}
int left = i + k -1;
//matching the middle part with target string, omit all leading zero
i = i + k;
while (A[i] == 0) i++;
k = 0;
while (k < target.length()) {
if (A[i + k] == target.charAt(k) - '0') k++;
else return new int[] {-1, -1};
}
return new int[] {left, i + k};
}
这道题思考过程是这样，看了数据规模得出 解的时间复杂度应该是ON，那么暴力解法肯定不行。
O N + 分成3段，就想到2个指针。那么2个指针就很容易想到双向指针。
那么我就把第一个指针放在头部，后一个指针放在尾部，开始找能不能指针只会往中间走而不回退的方法。
我发现，如果一开始头尾指针构成的二进制数，如果是一样的。那么只要中间的部分和他们也是一样的就找到答案了。
如果不一样，分为2个情况
如果前面的 比 后面的 小
可以通过右移左指针而起到增大前面的本事。因为3个区间要相等。我们最开始已经贪心的把前后都压缩到最小，所以要补救势必是通过增大的方式。
如果后面比前面小。我们肯定要通过左移右指针去把中间的元素拿到右面，来增大右面。道理同上
如果配平了左右2面，此时一定是前缀和后缀长度最小的配平。根据贪心的思想。
我们就看这个最小的配平下，中间是不是也能配平。配平就找到解了。
如果中间的比右面的大，我们可以通过左移右指针，来试图让中间的区间减少。当然右移左指针也是可以的。为什么要选择左移右指针呢？
通过观察，右移左指针必然会使得前半部分增大。而左移右指针，可能因为是0，加了前缀0等于没加。而依然保持左半和右半配平。
如果中间的区间的值比右面的小，肯定无解了。因为我们已经为了配平左右而用了最小的长度。一旦要去从左右拿出元素，肯定就无法配平左右了。
分析到这里，思路就有了。
落实到代码，我决定用DQ，因为方便2头进出。
同时为了在做DQ compare的时候，加速。
我决定忽略所有前缀0，这增加了编码难度，但是加快了时间。
所有忽略前缀0的DQ，在比较的时候，
如果长度不同，可以直接比出大小。
如果长度相同，就依次遍历每一个值，如果全相同就同，如果一旦不同，直接比较这2个不同的值。
为了达到上述效果，我在发现每个DQ的前缀是0的情况下，就不插进去了。只有1做前缀的时候再插进去，同时需要补之前没插的0.
O N + 分成3段，就想到2个指针。那么2个指针就很容易想到双向指针。
那么我就把第一个指针放在头部，后一个指针放在尾部，开始找能不能指针只会往中间走而不回退的方法。
我发现，如果一开始头尾指针构成的二进制数，如果是一样的。那么只要中间的部分和他们也是一样的就找到答案了。
如果不一样，分为2个情况
如果前面的 比 后面的 小
可以通过右移左指针而起到增大前面的本事。因为3个区间要相等。我们最开始已经贪心的把前后都压缩到最小，所以要补救势必是通过增大的方式。
如果后面比前面小。我们肯定要通过左移右指针去把中间的元素拿到右面，来增大右面。道理同上
如果配平了左右2面，此时一定是前缀和后缀长度最小的配平。根据贪心的思想。
我们就看这个最小的配平下，中间是不是也能配平。配平就找到解了。
如果中间的比右面的大，我们可以通过左移右指针，来试图让中间的区间减少。当然右移左指针也是可以的。为什么要选择左移右指针呢？
通过观察，右移左指针必然会使得前半部分增大。而左移右指针，可能因为是0，加了前缀0等于没加。而依然保持左半和右半配平。
如果中间的区间的值比右面的小，肯定无解了。因为我们已经为了配平左右而用了最小的长度。一旦要去从左右拿出元素，肯定就无法配平左右了。
分析到这里，思路就有了。
落实到代码，我决定用DQ，因为方便2头进出。
同时为了在做DQ compare的时候，加速。
我决定忽略所有前缀0，这增加了编码难度，但是加快了时间。
所有忽略前缀0的DQ，在比较的时候，
如果长度不同，可以直接比出大小。
如果长度相同，就依次遍历每一个值，如果全相同就同，如果一旦不同，直接比较这2个不同的值。
为了达到上述效果，我在发现每个DQ的前缀是0的情况下，就不插进去了。只有1做前缀的时候再插进去，同时需要补之前没插的0.
