927. Three Equal Parts

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, 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

这道题给了我们一个只有0和1的数组,让将其分为三段,使得每一段组成的二进制的数相同,注意数组左边的数字是高位,且开头可能会存在多余的0。最开始博主使用的方法是最直接的暴力方法,遍历所有的分成三段的可能,然后将每一段的二进制都计算出来比较是否相等,结果毫不意外的超时了,丝毫没有尊重这道题的 Hard 标签。仔细分析以下题目,既然要分成三段,且二进制数字相等,那么这三个二进制数中1的个数一定是相等的,因为转十进制的时候,只有1才会累加,而由于开头0的存在,所以0的个数不一定相同。那么1的个数就是突破口了,先遍历整个数组,统计出1的个数。假如数组中没有1的话,那就简单了,随便分三段都行了,因为都是0,所以返回 {0, n-1} 就行。再来想一下,假如1的个数不是3的个数,就绝无可能分为相等值的三段,直接返回 {-1,-1} 即可。假如个数是3的倍数,也不表示一定能成功分为3段,但如果能分的话,每段的1的个数一定是 cntOne/3,现在从末尾开始,找出正好有 cntOnt/3 个的位置 idxThird,此时虽然范围 [idxThird, n-1] 不一定是第三段,因为前面可能有0,但如果能成功分的话,其1的个数及位置一定是正确的。此时要做的是,从开头0开始,略去连续0,然后和 [idxThird, n-1] 区间对比,一旦有不一样的位置,说明无法正确分,返回 {-1,-1}。若能找到相同的一段话,说明此时第一段和第三段存在了,再来检测第二段,此时中间段的1的个数已经确定为 cntOne/3 了,只需要再确定其位置是否一样就可以了,其实主要比的是1的位置,因为开头连续0可以略去,就算每个区间末尾还有0,这些0是可以移动到下一个区间的开头的,从而可以保证对应的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;
    }
};

再来看一种比较类似的方法,开始的操作还是一样的,统计1的个数 cntOne,然后计算出每段的1的个数 k=cntOne/3,再用三个变量 start, mid, end 来标记每段的第一个1的位置,因为想要跳过开头的连续0。再用另一个变量 cnt 来重新在遍历的过程中统计1的个数,在 cnt 为0的时候,一直更新 start,这样可以跳过开头连续0,当 cnt=k+1 时,更新 mid 为i,因为这是第二段中第一个1的位置,当 cnt=2*k+1 时,更新 end 为i,因为这是第三段中第一个1的位置,然后此时验证三个区间,即 A[start],A[mid],和 A[end] 必须相等,然后三个指针同时向后移动一位,若有任何不相等,就 break 掉,最后看若 end 等于n,说明三段区间中1的位置都相等,是符合题意的,返回 {start-1, mid},否则返回 {-1,-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/

https://leetcode.com/problems/three-equal-parts/discuss/183922/C%2B%2B-O(n)-time-O(1)-space-12-ms-with-explanation-and-comments

https://leetcode.com/problems/three-equal-parts/discuss/223886/Java-O(n)-simple-solution-(don't-know-why-official-solution-is-that-long)

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation