0927：三等分（1994 分）

力扣第 107 场周赛第 3 题

题目

给定一个由 0 和 1 组成的数组 arr ，将数组分成 3 个非空的部分 ，使得所有这些部分表示相同的二进制值。

如果可以做到，请返回任何 [i, j]，其中 i+1 < j，这样一来：

• arr[0], arr[1], ..., arr[i] 为第一部分；
• arr[i + 1], arr[i + 2], ..., arr[j - 1] 为第二部分；
• arr[j], arr[j + 1], ..., arr[arr.length - 1] 为第三部分。
• 这三个部分所表示的二进制值相等。

如果无法做到，就返回 [-1, -1]。

注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，[1,1,0] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的，所以 [0,1,1] 和 [1,1] 表示相同的值。

示例 1：

输入：arr = [1,0,1,0,1]
输出：[0,3]

示例 2：

输入：arr = [1,1,0,1,1]
输出：[-1,-1]

示例 3:

输入：arr = [1,1,0,0,1]
输出：[0,2]

提示：

• 3 <= arr.length <= 3 * 104
• arr[i] 是 0 或 1

分析

• 相同的二进制数必然 1 的数量是相同的
• 因此先提取 1 的下标数组 A
  • 如果 m=len(A) 不是 3 的倍数，无法分割
  • 否则将 A 三等分，三段起始的 1 分别是 i=A[0],j=A[m//3],k=A[m//3*2]
    • 注意前缀 0 不影响值，所以直接定位起始的 1
  • 注意最后一段必然是 arr[k:]，所以要使三段相同，长度必然都是 L=n-k
  • 确定了三段的起始和长度，直接判断是否相同即可
    • 注意三段不能重叠，要特别判断
  • 假如相同，返回对应的分割点 [i+L-1,j+L] 即可
    • 注意分割点要考虑前缀 0 了，不能直接返回起始的 1 的下标

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        n = len(arr)
        A = [i for i,a in enumerate(arr) if a==1]
        m = len(A)
        if m%3:
            return [-1,-1]
        if m==0:
            return [0,2]
        i,j,k = A[0],A[m//3],A[m//3*2]
        L = n-k
        if i+L<=j<=k-L and arr[i:i+L]==arr[j:j+L]==arr[k:]:
            return [i+L-1,j+L]
        return [-1,-1]

8 ms