LeetCode 927: three equal parts

发表于 | | 阅读次数:
字数统计: 640 | 阅读时长 ≈ 2

题目链接

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

题意

给一个仅包含0和1的数组A(3<= A.length <= 30000)，将数组分为三块，要求分为三块后的各自块二进制数保证相等，并给出如何分为三块的两个分割点，数组构成数字时可以接受前导0。

举例： [1, 1, 0] 代表 6

题目类型

智力

题目分析

挺有意思的题目。

  • 首先不难想到如果要能分为三块那三个块中的1的个数必须相同，否则不可能分出三个相等的块来（同时特判一下数组全是0的情况）；
  • 然后再将含有1的部分等分为三块以后，如何划分数组剩下的0是问题所在。因为三个块的值都相同，所以我们可以从数组最右边的连续0的个数判断三个块形成的相同的数字的后缀0的个数，这样就能够圈定出每个块的范围了。
  • 最后还要判断一下三个块去除前导0后能不能保证相等，如果能保证相等就是所求答案；如果不能保证也一定不会有解了

举个例子，寻找 [1, 0, 0, 1, 0, 1, 0] 的分块方案

首先找到三个1的位置，由最后一个块最后只有1个0将数组分为[1, 0]、[0, 1, 0]、[1, 0]

验证后发现相等，问题得解

时间复杂度

$O(N)$

源代码

代码写的非常凌乱

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
    vector<int> threeEqualParts(vector<int>& A) {
        int n = A.size();
        int i, sum3 = 0;
        for (i = 0; i < n; i++) {
            if (A[i] == 1)
                sum3++;
        }
        vector<int>false_ans(2, -1);
        if(sum3 % 3 != 0)
            return false_ans;
        vector<int>ans;
        int back0;
        for (i = n - 1; i >= 0; i--)
            if (A[i] == 1)
                break;
        back0 = n - 1 - i;
        if (back0 == n) {
            ans.push_back(0);
            ans.push_back(2);
            return ans;
        }
        vector<int>back1;
        int tmp = 0, j, k;
        for (i = 0; i < n; i++) {
            tmp += A[i];
            if (tmp == sum3 / 3) {
                tmp = 0;
                back1.push_back(i);
            }
        }
        for (i = 0; i < 2; i++) {
            for (j = back1[i] + 1; j <= back1[i] + back0; j++)
                if (j >= n || A[j] == 1)
                    return false_ans;
            ans.push_back(back1[i] + back0);
        }
        ans[1]++;
        for (i = 0; i < n; i++)
            if (A[i] == 1)
                break;
        for (j = ans[0] + 1; j < n; j++)
            if (A[j] == 1)
                break;
        for (k = ans[1]; k < n; k++)
            if (A[k] == 1)
                break;
        if (!(ans[0] - i == ans[1] - 1 - j && ans[0] - i == n - 1 - k))
            return false_ans;
        tmp = ans[0] - i;
        for (int t = 0; t < tmp; t++)
            if (!(A[t + i] == A[t + j] && A[t + i] == A[t + k]))
                return false_ans;
        return ans;
    }
};
0%