Сложность: hard
Вам дан массив arr, состоящий только из нулей и единиц. Разделите массив на три непустые части так, чтобы все эти части представляли одно и то же двоичное значение. Если это возможно, верните любой [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] представляют одно и то же значение.
Пример:
Input: arr = [1,0,1,0,1]
Output: [0,3]
👨💻 Алгоритм:
1⃣Подсчитать количество единиц в массиве.
2⃣Если количество единиц не делится на три, вернуть [-1, -1].
Найти индексы начала каждой части, игнорируя ведущие нули.
Использовать эти индексы для проверки, могут ли три части быть одинаковыми.
3⃣Если три части одинаковы, вернуть соответствующие индексы, иначе вернуть [-1, -1].
😎 Решение:
def threeEqualParts(arr):
ones = sum(arr)
if ones % 3 != 0:
return [-1, -1]
if ones == 0:
return [0, len(arr) - 1]
part_ones = ones // 3
first = second = third = cnt = 0
for i, val in enumerate(arr):
if val == 1:
if cnt == 0:
first = i
elif cnt == part_ones:
second = i
elif cnt == 2 * part_ones:
third = i
cnt += 1
while third < len(arr) and arr[first] == arr[second] == arr[third]:
first += 1
second += 1
third += 1
if third == len(arr):
return [first - 1, second]
return [-1, -1]
Ставь 👍 и забирай 📚 Базу знаний