力扣-927.三等分

题目描述

实现

今天一看题目，坏了家人们，怎么是纯数学题啊（悲），这下不会了。
那既然是数学题，那就要仔细分析题目了。
首先，题目是将数组分为3个非空的部分，所有这些部分表示相同的二进制值，数组只存在0和1两个表示二进制的数字。
分析下示例，可以看到我们应该把重点放在1这个数字上，并且分情况讨论：

1. 如果可以做到，那么数组其中的1的个数应该能被3整除，并且得到的3个部分中，1的个数应一致。
2. 特殊情况，没有一个1，即数组全是0的情况，我们只要随意给出一个合理答案即可，如[0,2]。
   那么我们知道数组中可能存在解后，要怎么得到这个解呢？其实就是逐一比较。虽然数组中存在前导0，但是我们完全可以避开它，因为我们把重点放在了1上。无论有几个前导0，我们只要从每个数字的第一个1开始比较就不会受前导0影响。
   知道了从每个部分的第一个1开始比较后，我们的重点就转变为了怎么找到每个部分第一个1在数组中的位置。前面提到，如果存在解，那么每个部分的1的个数是一致的。我们可以遍历数组，并使用一个计数器来帮助确定每个部分的1的位置。举个例子：

假设给出数组[1,1,0,0,1,1,0,1,1]，我们可以得知其中1的个数为6，那么每个部分包含的1的个数应该为：6/3 == 2。
遍历数组，cnt开始设为0，如果遇到了1，那么进行判断，cnt为0，那么当前位置就是第一部分第一个1的位置，如果cnt为2，那么就是第二个部分第一个1的位置，如果cnt为4，那么就是第三部分第一个1的位置，最后cnt++。
现在我们得到了每个部分第一个1的位置，接下来要做的就是进行比较了。同样是遍历数组，一直比到数组越界都一致的话，我们就得到了解。否则无解。

class Solution:
    def threeEqualParts(self, arr: List[int]) -> List[int]:
        nums = arr.count(1)  # 统计1出现的次数
        if nums == 0:  # 数组中全0，返回一个合理答案即可
            return [0, 2]
        elif nums % 3 != 0:  # 1的个数无法被3整除，返回无解
            return [-1, -1]
        cnt = index1 = index2 = index3 = 0  # 辅助变量
        ones_cnt = nums // 3  # 每个部分1的个数
        for index, item in enumerate(arr):
            if item:  # 如果item是1
                if cnt == 0:
                    index1 = index  # 第一部分第一个1的位置
                elif cnt == ones_cnt:
                    index2 = index  # 第二部分第一个1的位置
                elif cnt == 2 * ones_cnt:
                    index3 = index  # 第三部分第一个1的位置
                cnt += 1  # 找到的1的个数增加
        while index3 + 1 < len(arr):
            if arr[index1 + 1] != arr[index2 + 1]  or arr[index1 + 1] != arr[index3 + 1]:  # 匹配失败，返回无解
                return [-1, -1]
            index1 += 1
            index2 += 1
            index3 += 1
        return [index1, index2 + 1]

希望本文章能够帮到您~