leetcode 百天解题 - day 80 - 927. 三等分

题目名称

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

示例

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

题解

答案

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var threeEqualParts = function(arr) {
  let i = -1, j = -1
  let oneNum = arr.filter(i => i === 1).length
  if(!oneNum) return [0, arr.length - 1]
  if(oneNum % 3 !== 0) return [i, j]
  let first = -1, second = -1, third = -1, num = 0
  for(let i = 0; i < arr.length; i++) {
    if(arr[i] === 1) {
      num++
      if(first === -1) {
        first = i
      } else if(second === -1 && num === oneNum / 3 + 1) {
        second = i
      } else if(third === -1 && num === oneNum / 3 * 2 +1) {
        third = i
      }
    }
  }
  let thirdStr = arr.slice(third).join("")
  let secondStr = arr.slice(second, third).join("")
  let firstStr = arr.slice(first, second).join("")
  if(firstStr.includes(thirdStr) && secondStr.includes(thirdStr)) {
    i = first + thirdStr.length - 1
    j = second + thirdStr.length
  }
  return [i, j]
};