Ссылка на задачу — 763. Partition Labels.
📄 Описание задачи
- Дана строка
s, состоящая только из строчных латинских букв.
- Нужно разбить строку на как можно большее количество подстрок, таких что каждая буква встречается не более чем в одной подстроке.
- После разбиения объединение всех подстрок в порядке следования должно дать исходную строку.
- Например, для строки
"ababcc" корректное разбиение: ["abab", "cc"].
А такие варианты, как ["aba", "bcc"] или ["ab", "ab", "cc"] — недопустимы, потому что буквы повторяются в нескольких частях.
- Нужно вернуть список размеров всех полученных подстрок.
💡 Идея
Каждая буква должна присутствовать в одной части.
Значит, можно рассматривать все буквы как интервалы [первая позиция, последняя позиция].
Теперь задача сводится к жадному объединению перекрывающихся интервалов: как только текущий интервал завершился, мы фиксируем подстроку.
🔍 Детали подхода
- Проходим по строке один раз, чтобы:
- определить первую и последнюю позицию каждой буквы;
- зафиксировать порядок появления символов.
- Затем проходим по символам алфавита в порядке первого появления:
Читать дальше →
Ссылка на задачу — 3356. Zero Array Transformation II.
📝 Описание задачи
Дан массив nums длины N и список запросов queries, каждый из которых задаётся как [li, ri, vali]. Запрос означает, что значения в диапазоне [li, ri] можно уменьшить на любое число от 0 до vali независимо друг от друга.
Нужно найти минимальное число первых запросов k, после которых nums может превратится в массив, состоящий только из нулей. Если это невозможно — вернуть -1.
💡 Идея
Вместо того, чтобы изменять nums напрямую, будем хранить массив последовательных изменений к декременту (updates). Он позволяет эффективно применять диапазонные операции без лишних вычислений.
Чтобы минимизировать количество обработанных запросов, будем использовать жадную стратегию обработки запросов:
- Обрабатываем
nums последовательно
- Для каждой позиции
i, если nums[i] ещё не стал 0, пытаемся применить минимально возможное число новых запросов из списка.
⚙️ Детали подхода
- Используем массив
updates (N+1 элементов), где updates[i] хранит последовательные изменения к декременту значений.
Читать дальше →