力扣-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]

希望本文章能够帮到您~