天池在线编程三等分（模拟）

Michael阿明

发布于 2021-02-19 14:53:59

5970

发布于 2021-02-19 14:53:59

文章被收录于专栏：Michael阿明学习之路

1. 题目

给定一个由 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] 表示相同的值。

3 <= A.size <= 30000
A[i] = 0  or  A[i] = 1
 
示例
样例 1：
输入：[1,0,1,0,1]
输出：[0,3]

样例 2：
输出：[1,1,0,1,1]
输出：[-1,-1]

https://tianchi.aliyun.com/oj/245867719779445300/277517718521058001 https://leetcode-cn.com/problems/three-equal-parts/

2. 解题

就是检查每个部分尾部的0的个数一样，确定开始结束位置，见注释

class Solution {
public:
    /**
     * @param A: an array
     * @return: divide the array into 3 non-empty parts
     */
    vector<int> threeEqualParts(vector<int> &A) {
        // write your code here
        int sum = accumulate(A.begin(), A.end(), 0);
        if(sum%3 != 0)//1的个数不能整除3
            return {-1,-1};
        int i, j, part = sum/3, one = 0, tail0 = 0, n = A.size();
        if(part == 0)//没有1
            return {0,2};
        for(i = n-1; i >= 0; --i)
        {
            if(A[i] == 1)
                one++;
            else
            {
                if(one==0)
                    tail0++;//第三部分的尾部0个数
            }
            if(one == part)
                break;
        }
        int mid0 = 0, start = i;//start 为第三部分的可能开始点
        for(i--; i>=0 && A[i] != 1; i--)
        {
            mid0++;//第二第三部分中间的0的个数
        }
        if(mid0 < tail0)//第二部分尾0的个数不能跟第三部分尾0一样多
            return {-1,-1};

        start -= mid0-tail0;//分一部分前置0给第三部分
        int count = 0;
        for(i = start-1, j = n-1; i >= 0; --i,--j)
        {   // 比较 第二第三部分是否一样
            if(A[i]==1) count++;
            if(A[i] != A[j])
                return {-1,-1};
            if(count == part)//1的个数够了，跳出
                break;
        }
        mid0 = 0;
        int start1 = i;//第二分部可能的开始位置
        for(i--; i>=0 && A[i] != 1; i--)
        {
            mid0++;//第一第二部分中间的0的个数
        }

        if(mid0 < tail0)//同上
            return {-1,-1};
        count = 0;
        start1 -= mid0-tail0;//第二部分开始的位置
        for(i = start1-1, j = n-1; i >= 0; --i,--j)
        {
            if(A[i] == 1) count++;
            if(A[i] != A[j])
                return {-1,-1};
            if(count == part)
                break;
        }
        return {start1-1, start};//第一部分结束，第三部分开始
    }
};

50ms C++