Ссылка на задачу — 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 значения.
🔍 Детали подхода
- Обход массива, используя
flip_state для проверки, должен ли текущий элемент быть перевернут.
- Если переворот необходим, инкрементируем
flip_count и переворачиваем биты flip_state, виртуально изменяя два следующих элемента.
- Сдвигаем
flip_state вправо на каждой итерации, чтобы учитывать только последние два переворота.
- В конце, если
flip_state == 0, значит все элементы 1 (возвращаем flip_count), иначе ответ -1 (преобразование невозможно).
📊 Асимптотика
- Время:
O(n) → Один проход по nums, каждое число обрабатывается ровно один раз.
- Память:
O(1) → Используется только несколько целочисленных переменных, без дополнительного хранения данных.
💻 Исходный код
impl Solution {
pub fn min_operations(nums: Vec<i32>) -> i32 {
let (flip_count, flip_state) = nums.into_iter()
.fold((0, 0), |(count, state), num| {
if num ^ (state & 1) == 0 {
(count + 1, (state >> 1) ^ 3) // Flip current and next two elements
} else {
(count, state >> 1) // Shift out the oldest flip
}
});
if flip_state == 0 { flip_count } else { -1 } // If there's an unprocessed flip, it's impossible
}
}
Tags: #rust #algorithms #bithacks