Ссылка на задачу — 3191. Minimum Operations to Make Binary Array Elements Equal to One I.
📌 Описание задачи
- Дан массив
nums, состоящий из 0 и 1.
- Можно переворачивать любые три подряд идущих элемента (
0 становится 1, а 1 — 0).
- Нужно найти минимальное количество операций, чтобы сделать все элементы
1. Если это невозможно, вернуть -1.
Пример:
- Вход:
nums = [0,1,1,1,0,0]
- Выход:
3
- Объяснение: Можно выполнить следующие операции:
1️⃣ Выбираем элементы с индексами [0,1,2]. Новый массив: [1,0,0,1,0,0]
2️⃣ Выбираем элементы с индексами [1,2,3]. Новый массив: [1,1,1,0,0,0]
3️⃣ Выбираем элементы с индексами [3,4,5]. Новый массив: [1,1,1,1,1,1] ✅
💡 Идея
- Будем искать необходимые перевороты слева-направо (это валидно, ибо 3-перевороты коммутируют друг с другом).
- Вместо непосредственного изменения
nums будем использовать битовый сдвиговый регистр flip_state (на 2 бита) для отслеживания переворотов вперед на 2 значения.
Читать дальше →