Ссылка на задачу — 2780. Minimum Index of a Valid Split.
📘 Описание задачи
- Дан массив целых чисел
nums, в котором гарантированно существует один доминирующий элемент
(то есть такой элемент, который встречается чаще, чем половина длины массива).
- Необходимо найти наименьший индекс
i, такой что массив можно разделить на две части:
nums[0],..,nums[i] и nums[i+1],..,nums[n-1],- и обе части будут иметь одинаковый доминирующий элемент.
- Если такого разделения не существует — вернуть
-1.
💡 Идея
Для эффективного поиска доминирующего элемента хорошо подходит алгоритм большинства голосов Бойера — Мура.
Зная доминирующий элемент, можно пройти по массиву и в каждой возможной точке разделения отслеживать:
- Сколько раз этот элемент встречался слева;
- Сколько осталось справа;
- Затем проверяется, является ли он доминирующим в обеих частях.
🔍 Детали подхода
- Применяем алгоритм голосования большинства для нахождения доминанты.
- Подсчитываем точное количество его вхождений, чтобы использовать для отслеживания остатка справа.
Читать дальше →
Ссылка на задачу — 3169. Count Days Without Meetings.
📌 Описание задачи
- Данo
days — количество дней, в течение которых сотрудник доступен для работы.
- Также дан массив
meetings, где meetings[i] = [starti, endi] обозначает дни проведения встречи.
Нужно посчитать количество дней, когда сотрудник свободен от встреч и может работать.
💡 Идея
Мы сортируем встречи по дню начала, чтобы затем обходить их в порядке возрастания.
Это позволяет использовать метод заметания линии как эффективный способ вычислить количество свободных дней между встречами.
🚀 Детали подхода
1️⃣ Сортируем встречи по начальной дате.
2️⃣ Проходим по списку встреч, отслеживая next_free (следующий свободный день).
3️⃣ Подсчитываем разрывы между next_free и началом следующей встречи.
4️⃣ Обновляем next_free после каждой встречи, сдвигая его на день после её окончания.
5️⃣ Добавляем свободные дни после последней встречи.
⏳ Асимптотика
-
Время:
O(n·logn)
O(n·logn) на сортировку.O(n) на обход.
-
Память:
O(1)
- Используем только несколько переменных.
💻 Исходный код
impl Solution {
pub fn count_days(days: i32, mut meetings: Vec<Vec<i32>>) -> i32 {
meetings.sort_unstable_by_key(|meet| meet[0]);
let (next_free, free_count) = meetings.into_iter()
.fold((1, 0), |(next_free, free_count), meet| {
let [start, end] = meet[..2] else { unreachable!("bad meet format") };
let gap = (start - next_free).max(0);
let next_free = next_free.max(end + 1);
(next_free, free_count + gap)
});
free_count + (days - next_free + 1).max(0)
}
}
Tags: #rust #algorithms #counting
Ссылка на задачу — 2379. Minimum Recolors to Get K Consecutive Black Blocks.
📌 Описание задачи
Дана строка blocks, состоящая из символов 'W' (белый) и 'B' (чёрный).
Необходимо определить минимальное число перекрашиваний белых блоков в чёрные, чтобы получить хотя бы одну последовательность из k подряд идущих чёрных блоков.
💡 Идея
Используем технику скользящего окна:
- будем двигать окно размера
k по строке и считать количество белых блоков внутри окна;
- минимальное количество белых блоков среди всех окон и будет ответом.
📖 Детали подхода
- Посчитаем число белых блоков в первом окне размера
k.
- Сдвигаем окно вправо на один символ за раз:
- если символ, который «входит» в окно, белый (
'W'), увеличиваем счётчик;
- если символ, который «выходит» из окна, белый, уменьшаем счётчик.
- После каждого сдвига окна обновляем минимальное найденное значение.
- Итоговый ответ — это минимальное число белых блоков за всё время обхода.
⏳ Асимптотика
- Время:
O(n) — каждый символ просматривается не более двух раз.
- Память:
O(1) — используется константная дополнительная память.
🛠️ Исходный код
impl Solution {
pub fn minimum_recolors(blocks: String, k: i32) -> i32 {
let blocks = blocks.as_bytes();
let k = k as usize;
// Count white blocks ('W') in the first window of size k
let initial_recolors = blocks[..k].iter().filter(|&&b| b == b'W').count() as i32;
// Slide window over the blocks using iterator methods
blocks
.windows(k+1)
.fold((initial_recolors, initial_recolors), |(current, min), window| {
// Update recolors based on outgoing and incoming blocks
let next = current
+ (window.last() == Some(&b'W')) as i32
- (window.first() == Some(&b'W')) as i32;
(next, min.min(next))
}).1
}
}
Tags: #rust #algorithms #counting