题目描述
给定一个只含 0 和 1 的数组 A，将这个数组分成 3 个非空的部分，使得每一部分代表相同的二进制的值。
如果可分，返回任意的[i, j]，i+1 < 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]。
注意，当考虑二进制的值时，整个部分都需要用到。例如，[1,1,0] 代表十进制的 6，非 3。另外，允许前导零，所以 [0,1,1] 和 [1,1] 表示相同的值。
样例
输入: [1,0,1,0,1]
输出: [0,3]
输入: [1,1,0,1,1]
输出: [-1,-1]
算法
(模拟) O(n)
- 所有三部分拥有相同的
1的个数，所以先统计1的个数。如果个数不被三整除，则则不可能。 - 如果
1的个数为 0，则直接返回[0, 2]。 - 否则，找到每一部分开头的
1和 末尾的1所在的位置。例如[0, 0, 1, 1, 0, 1, 1, 1, 1, 0]，三部分的位置分别为(2, 3), (5, 6), (7, 8)； - 判断每个区间长度是否一致；不一致则不可能。
- 检查每个区间内部的
01子串是否一致；不一致则不可能。 - 记录最后一部分中，最后的
1和数组末尾的距离，即为last_zero，这个值决定了每一部分最后需要多少个0。 - 最后判断前两个部分中，末尾是否足够有
last_zero个0。
时间复杂度
- 线性遍历若干次数组，故时间复杂度为 O(n)。
C++ 代码
class Solution {
public:
vector<int> threeEqualParts(vector<int>& A) {
int n = A.size(), ones = 0;
for (int i = 0; i < n; i++)
if (A[i] == 1)
ones++;
if (ones % 3 != 0)
return {-1, -1};
if (ones == 0)
return {0, 2};
ones /= 3;
int s[3], t[3];
int cnt = 0;
for (int i = 0; i < n; i++) {
if (A[i] == 1) {
cnt++;
if (ones == 1)
s[cnt / ones - 1] = i;
if (cnt % ones == 1)
s[cnt / ones] = i;
if (cnt % ones == 0)
t[cnt / ones - 1] = i;
}
}
int len = t[0] - s[0] + 1;
if (t[1] - s[1] + 1!= len || t[2] - s[2] + 1!= len)
return {-1, -1};
for (int i = 0; i < len; i++) {
int x = A[i + s[0]];
if (x != A[i + s[1]] || x != A[i + s[2]])
return {-1, -1};
}
int last_zeros = n - t[2] - 1;
if (s[2] - t[1] - 1 < last_zeros || s[1] - t[0] - 1 < last_zeros)
return {-1, -1};
return {t[0] + last_zeros, t[1] + last_zeros + 1};
}
};
alternative implementation
template <typename T, std::size_t N> array<T, N> equal_split(const T& x, array<T, N> result = {}) { for (int i = 0; i < N; ++i) std::copy(begin(x) + i * size(x) / N, begin(x) + (i + 1) * size(x) / N, std::back_inserter(result[i])); return result; } template <typename T, typename F> vector<int> index_tracker(const T &x, F&& f, vector<int> result = {}) { for (int i = 0; i < size(x); ++i) if (std::forward<F>(f)(x[i])) result.emplace_back(i); return result; } class Solution { public: vector<int> threeEqualParts(vector<int>& A) { const int n = size(A); const vector<int> impossible = {-1, -1}; const auto ones_id = index_tracker(A, [&](auto x){ return x == 1; }); if (size(ones_id) == 0) return {0, 2}; else if (size(ones_id) % 3 != 0) return impossible; else { const auto [fst, snd, thd] = equal_split<vector<int>, 3>(ones_id); const int last_zeros = n - (thd.back() + 1); const int fst_interval_zeros = snd.front() - (fst.back() + 1); const int snd_interval_zeros = thd.front() - (snd.back() + 1); auto solution = [&]() -> vector<int> { if (std::min(fst_interval_zeros, snd_interval_zeros) < last_zeros or not std::equal(begin(A) + fst.front(), begin(A) + fst.back(), begin(A) + snd.front(), begin(A) + snd.back()) or not std::equal(begin(A) + snd.front(), begin(A) + snd.back(), begin(A) + thd.front(), begin(A) + thd.back())) return impossible; else return {fst.back() + last_zeros, snd.back() + last_zeros + 1}; }; return solution(); } } };神，请收悉我的膝盖。