leetcode 927. 三等分

927. 三等分

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

示例 1：

輸入：[1,0,1,0,1]

輸出：[0,3]

示例 2：

輸出：[1,1,0,1,1]

輸出：[-1,-1]

提示：

3 <= A.length <= 30000

A[i] == 0 或 A[i] == 1

逾時的心累=-=

簡單說下過程：

• 首先判斷清單中1的個數，如果不是三的倍數，傳回假
• 對1的個數除以3，得到的數值将是每一組所含有的1的個數cnt
• 計算A的長度，友善之後的傳回索引
• 從左向右計算cnt個1在那一個位置,從右往左也計算cnt個1在哪個位置，分别命名為 j , i
• 對s1,s2,s3進行初步的判斷，如果有相等，可以直接指派out
• 接下來就是右移s1的右指針，左移s2的左指針。
• 最後輸出out

class Solution:
    def threeEqualParts(self, A: List[int]) -> List[int]:
        num = sum(A)
        if num % 3 != 0: return[-1,-1]
        if num == 0: return [0,len(A)-1]
        n = len(A)
        A = [str(i) for i in A]

		#從左向右計算cnt個1在哪個索引
        cnt = num // 3
        i = n
        while cnt and i > 0:
            if A[i-1] == '1':
                cnt -= 1
            i -= 1
            
		#從右往左計算cnt個1在哪個索引
        cnt = num // 3
        j = 0
        while cnt and j < n:
            if A[j] == '1':
                cnt -= 1
            j += 1
		#初始化輸出，三個清單的數值，去除左0
        out = [-1,-1]
        s1 = ''.join(A[:j]).lstrip('0')
        s2 = ''.join(A[j:i]).lstrip('0')
        s3 = ''.join(A[i:]).lstrip('0')
        #對三個清單值進行初步的判斷，減少之後的運算
        if s1 == s2 == s3: return [j-1, i]
        if s1 == s3: out[0] = j-1
        if s2 == s3: out[1] = i
        #s1的指針右移，如果不是1，則加入s1，s1 == s3，或者右指針為1結束。如果找到s1 ==s3，直接傳回
        while A[j] != '1' and s1 < s3:
            s1 += ('0')
            if s1 == s3:
                out[0] = j
                break
            j += 1 
		#s2的右指針左移，如果不是1，則s2減去末尾的值，同理
        while A[i-1] != '1' and s2 > s3:
            s2 = s2[:-1]
            if s2 == s3:
                out[1] = i-1
                break
            i -= 1
		#如果out中還有坐标為-1,說明某兩個不相等
        if -1 in out:
            return [-1,-1]
        else:
            return out