0927. Three Equal Parts

927. Three Equal Parts #

题目 #

Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

  • A[0], A[1], ..., A[i] is the first part;
  • A[i+1], A[i+2], ..., A[j-1] is the second part, and
  • A[j], A[j+1], ..., A[A.length - 1] is the third part.
  • All three parts have equal binary value.

If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

Example 1:

Input: [1,0,1,0,1]
Output: [0,3]

Example 2:

Input: [1,1,0,1,1]
Output: [-1,-1]

Note:

  1. 3 <= A.length <= 30000
  2. A[i] == 0 or A[i] == 1

题目大意 #

给定一个由 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. 3 <= A.length <= 30000
  2. A[i] == 0 或 A[i] == 1

解题思路 #

  • 给出一个数组,数组里面只包含 0 和 1,要求找到 2 个分割点,使得分成的 3 个子数组的二进制是完全一样的。
  • 这一题的解题思路不难,按照题意模拟即可。先统计 1 的个数 total,然后除以 3 就是每段 1 出现的个数。有一些特殊情况需要额外判断一下,例如没有 1 的情况,那么只能首尾分割。1 个个数不是 3 的倍数,也无法分割成满足题意。然后找到第一个 1 的下标,然后根据 total/3 找到 mid,第一个分割点。再往后移动,找到第二个分割点。找到这 3 个点以后,同步的移动这 3 个点,移动中判断这 3 个下标对应的数值是否相等,如果都相等,并且最后一个点能移动到末尾,就算找到了满足题意的解了。

代码 #


package leetcode

func threeEqualParts(A []int) []int {
	n, ones, i, count := len(A), 0, 0, 0
	for _, a := range A {
		ones += a
	}
	if ones == 0 {
		return []int{0, n - 1}
	}
	if ones%3 != 0 {
		return []int{-1, -1}
	}
	k := ones / 3
	for i < n {
		if A[i] == 1 {
			break
		}
		i++
	}
	start, j := i, i
	for j < n {
		count += A[j]
		if count == k+1 {
			break
		}
		j++
	}
	mid := j
	j, count = 0, 0
	for j < n {
		count += A[j]
		if count == 2*k+1 {
			break
		}
		j++
	}
	end := j
	for end < n && A[start] == A[mid] && A[mid] == A[end] {
		start++
		mid++
		end++
	}
	if end == n {
		return []int{start - 1, mid}
	}
	return []int{-1, -1}
}


⬅️上一页

下一页➡️

Calendar Sep 6, 2020
Edit Edit this page
本站总访问量:  次 您是本站第  位访问者