【leetcode】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:

3 <= A.length <= 30000

A[i] == 0 or A[i] == 1

解题思路：可以肯定的一点是A中1的个数(记为count_1)一定是3的倍数，如果不是那么是无法分成相同的三等份的；如果可以等分，那么每一份的1的个数count_1/3，假设每一份的有效字符串是S(有效字符串可以理解成不包括前面的0)，A就可以表示成 0...0S0...0S0...0S 的形式。接下来倒序遍历A，遍历过程中记录1的数量，每当数量到达count_1/3的时候将这一段记为其中一等份，那么A就可以分成 [S0...0,S0...0,S]的形式，记为parts数组，第一个S前的0是无效的，所以不需要处理。接下来就只要判断parts数组中最后一个元素是否是前两个元素的前缀，如果是的话，就表示可以被等分了。最后是求等分的下标位置，只要把[S0...0,S0...0,S] 中S后面的0都给下一个元素变成[S,0...0S,0...0S]就可以轻而易举的得到结果了。

代码如下：

class Solution(object):
    def threeEqualParts(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        A = [str(i) for i in A]
        count_1 = A.count('1')
        if count_1 == 0 :
            return [0,2]
        elif count_1 == 0 or count_1 % 3 != 0:
            return [-1,-1]

        parts = ['','','']
        times = 0
        inx = 2
        subs = ''
        for i,v in enumerate(A[::-1]):
            if v == '1':
                times += 1
            subs = v + subs
            if times == (count_1 / 3):
                parts[inx] = subs
                inx -= 1
                times = 0
                subs = ''
        #print parts
        if parts[0].startswith(parts[2]) and parts[1].startswith(parts[2]):
            second_len = len(parts[2]) + (len(parts[1]) - len(parts[2]))
            first_len = len(parts[2]) + len(parts[1]) +  + (len(parts[0]) - len(parts[2]))
            return [len(A) - first_len-1,len(A) - second_len]
            #pass
        #print parts
        return [-1,-1]