难度: Hard
原题连接
内容描述
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:
3 <= A.length <= 30000
A[i] == 0 or A[i] == 1
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(1)******
什么都不说了，我是个智障，不允许任何反驳，上来就无脑写了一个暴力，我就是头铁，我，就是铁头娃！！！
class Solution(object):
def threeEqualParts(self, A):
"""
:type A: List[int]
:rtype: List[int]
"""
if len(A) < 3:
return [-1, -1]
for i in range(len(A)-2):
for j in range(i+2, len(A)):
tmpi, tmpj, tmpk = i, j-1, len(A)-1
while tmpi >= 0 and tmpj >= i+1 and tmpk >= j:
if A[tmpi] == A[tmpj] == A[tmpk]:
tmpi -= 1
tmpj -= 1
tmpk -= 1
else:
break
if not (tmpi == -1 or tmpj == i or tmpk == j-1):
continue
while tmpi >= 0:
if A[tmpi] == 0:
tmpi -= 1
else:
break
if tmpi != -1:
continue
while tmpj >= i+1:
if A[tmpj] == 0:
tmpj -= 1
else:
break
if tmpj != i:
continue
while tmpk >= j:
if A[tmpk] == 0:
tmpk -= 1
else:
break
if tmpk != j-1:
continue
return [i, j]
return [-1,-1]
思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******
三个部分相等，那么三个部分1的数量肯定要相等，立马变成O(1)
但是这里要注意三个比较重要的点
- 如果A的长度小于3，直接返回[-1,-1]
- 如果A中全是0，直接返回[0,2]
- 如果A的末尾有很多连续的0的时候，我们要注意在part1和part2后面也要加上那么多个0, 例如：输入为[1,0,0,0,1,0,0,0,1,0,0]
应该分为的三个部分分别是
part1 = [1,0,0], part2 = [0,1,0,0], part3 = [0,1,0,0], 而不是part1 = [1], part2 = [0,0,0,1], part3 = [0,0,0,1,0,0]。因为A末尾有2个连续的0，所以每个part后面都要有2个连续的0
class Solution:
def threeEqualParts(self, A: 'List[int]') -> 'List[int]':
if len(A) < 3:
return [-1, -1]
count_one = 0
for i in A:
if i == 1:
count_one += 1
if count_one == 0:
return [0, 2]
if count_one % 3 != 0:
return [-1, -1]
idx, count_end_zero = len(A) - 1, 0
while A[idx] == 0:
count_end_zero += 1
idx -= 1
part1_end, part2_end, count = 0, 0, 0
for idx, num in enumerate(A):
if num == 1:
count += 1
if count == count_one / 3:
part1_end = idx
elif count == 2 * count_one / 3:
part2_end = idx
break
i, j = part1_end+count_end_zero, part2_end+count_end_zero+1
tmpi, tmpj, tmpk = i, j-1, len(A)-1
while tmpi >= 0 and tmpj >= i+1 and tmpk >= j:
if A[tmpi] == A[tmpj] == A[tmpk]:
tmpi -= 1
tmpj -= 1
tmpk -= 1
else:
break
if not (tmpi == -1 or tmpj == i or tmpk == j-1):
return [-1,-1]
while tmpi >= 0:
if A[tmpi] == 0:
tmpi -= 1
else:
break
if tmpi != -1:
return [-1,-1]
while tmpj >= i+1:
if A[tmpj] == 0:
tmpj -= 1
else:
break
if tmpj != i:
return [-1,-1]
while tmpk >= j:
if A[tmpk] == 0:
tmpk -= 1
else:
break
if tmpk != j-1:
return [-1,-1]
return [i, j]