Leetcode 927 Three Equal Parts

发表于 |

给定只包含’0’,’1’的数组A，将数组A划分成3个部分，每个部分代表一个二进制数，你需要找到一组i,j（i+1 < j）使得划分的3部分所代表的二进制数的值相等。
其中：
A[0],A[1],…,A[i]是第一部分
A[i+1],…,A[j-1] 是第二部分
A[j],A[j+1],…,A[A.length-1]是第三部分

如果找不到划分方法，返回[-1,-1]

注意：
例如划分出[1,1,0]这个数组，他代表的值是6而不是3。
允许前导0的存在，例如[0,1,1]和[1,1]都可以代表3。

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

题意分析：
将数组划分成三个部分，使三个部分所代表的二进制值相同。
注意到A的长度达到3w，所以考虑复杂度的时候一定需要考虑清楚。

思路分析：
在这里我讲一下我看到这道题的时候思路过程是怎样的。

我首先想的是从第一部分和第三部分下手，因为这两个部分靠近边界，很容易可以计算出所代表的数值。我想使用left[i]表示A[:i]对应的数，right[i]表示A[i:]对应的数，然后依次找到i,j使得left[i] == right[j]，最后再判断中间的数是不是也相等。

乍一想，好像还真行诶，因为是O(n) time, O(n) space嘛。当然稍微再分析一下就会发现这是有问题的。第一个问题在于A的长度实在太大，能表示的二进制数的大小是巨大无比的，我根本没法存下来；第二个问题在于，由于A中必定存在着大量的’0’，使得很多left[i]的值与right[j]的值相同，但中间的数的大小是会发生改变的，这样会有大量计算，我估计会超时！

那么这两个问题要怎么解决呢？
我们不妨就将划分成的三部分分别定义为a,b,c吧，如何判断a==b==c呢？上面说了转成十进制数来判断是行不通的，所以我们直接比较数组本身是不是相同，但是这又衍生出一个问题————因为有前缀0的存在，所以每次比较都要先消除前缀0，这个比较的开销感觉挺大的，所以我采取的方式是记录的时候就只记录出现了第一个1之后的部分，例如[0,0,0,1,1]就只记录[1,1]，这样开销就减小很多了。下文中所提到的a,b,c数组默认都是以1开头的。

根据我们记录数组的方式(以1开头)，那么我们顺势可以确定b,c长度。为何这样说呢？
我们知道，二进制数中(1开头)如果长度就不相等的话最后表达的值也不可能相等。所以例如我们确定了数组a的长度为l，
那么b数组和c数组的长度也一定是l。如果长度都不满足，那么根本无需比较！

我们来看一个例子 A = [1,0,1,0,1,0]
我们首先选取a = [1]代表第一部分，那么第一部分的长度就为1；所以第二部分的长度也只能是1，则b = [1]（实际为[0,1]，我们只记录[1]），那么c的长度则是剩余的数组长度 [1,0]，长度为2，故不符合！

OK，在代码中我们使用right数组来记录下一个‘1’出现的位置，使用left数组记录左边第一个‘1’出现的位置。

当我们选取第i个位置作为第一部分的结尾，则有：
第一部分的开头在left[i], 结尾在i， 长度为l = (i-left[i]+1)
第二部分的开头在right[i]，结尾在end = right[i] + l， 满足长度相同
第三部分的开头在end+1,结尾在end+1 + l, 满足长度相同

如果第三部分的结尾不等于len(A)，则跳过不处理！！！

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
# 120ms
class Solution(object):
    def threeEqualParts(self, A):
        # 考虑到没有1的情况
        if A.count(1) == 0:
            return [0,len(A)-1]
        # 只要有1个1，那么逻辑就成立。
        n = len(A)
        # right,left数组含义如上所述
        right = [-1] * n
        index = n
        for i in range(n-1,-1,-1):
            right[i] = index
            if A[i] == 1: index = i

        left = [-1] * n
        index = A.index(1)
        for i in range(n):
            if i >= index: left[i] = index

        for i in range(n-2):
            f_start = left[i]
            # 左边还没有1的话则表示第一部分的值为0
            # 三部分的值都为0的情况在程序开头已经处理了
            if f_start == -1: continue
            l = i - f_start + 1
            # 第二部分如果就超过了数组长度就没有第三部分了
            s_start = right[i]
            s_end = s_start + l - 1
            if s_end >= n: break

            t_start = right[s_end]
            if t_start >= n: break
            if n - t_start != l: continue
            # 满足上述所有条件后，再进行比较
            if A[f_start:i+1] == A[s_start:s_end+1] == A[t_start:n]:
                return [i, s_end + 1]
        return [-1, -1]