▲

3

▼

🚀 Оптимальное применение сдвига символов строки с использованием префиксных сумм

leetcoder, изменено 13-01-2025

Задача на сегодня 2381. Shifting Letters II - решается несложно, но используемая идея мне лично кажется интересной и симпатичной.

Описание задачи 🔎

Дана строка s и список операций shifts, где каждая операция задаёт начало и конец диапазона, а также направление (вперёд или назад).
Ваша задача — применить все сдвиги к строке и вернуть окончательный результат.

Идея 🔄

Для оптимизации решения и избежания повторных расчётов сдвигов, мы используем алгоритм, основанный на префиксных суммах. Это позволяет эффективно сохранять кумулятивный эффект от всех сдвигов в отдельном массиве и применять их конечному результату за один проход.

Детали решения 📝

1. Создадим массив net_shifts, где будут храниться чистые значения сдвигов для каждой позиции в строке.
2. Пройдемся по всем операциям и обновим массив net_shifts, добавляя значения в начале диапазона и вычитая их сразу после его окончания.
3. Произведем один последовательный проход по строке, вычисляя кумулятивные сдвиги и применяя их для каждого символа.

Асимптотика ⏳

• Время: O(n + m), где n — длина строки, m — количество операций.
• Память: O(n) для массива net_shifts.

Читать дальше →

▲

3

▼

🌀 Поиск уникальных палиндромов длины 3 с использованием битового массива

leetcoder, 04-01-2025

Наша очередная задача - 1930. Unique Length-3 Palindromic Subsequences.

📝 Описание задачи

Дана строка s. Необходимо определить количество уникальных палиндромов длины 3, которые являются подпоследовательностями строки.

Подпоследовательность — это строка, полученная из исходной строки удалением некоторых (возможно, нуля) символов без изменения их порядка. Например, для строки "abcde" строка "ace" является подпоследовательностью.

Палиндром — это строка, которая читается одинаково в прямом и обратном направлениях.

💡 Идея

Основная идея заключается в том, что палиндром длины 3 определяется первыми и последними символами, которые совпадают, а также любым допустимым символом посередине.
Мы можем эффективно отслеживать такие пары (первый и последний символы) с помощью битового массива (bitset), что позволяет минимизировать использование памяти.

🔍 Детали подхода

1. Массивы частот:
   • prefix_frequency: хранит частоты символов слева от рассматриваемого.
   • suffix_frequency: хранит частоты символов справа от рассматриваемого.

Читать дальше →

▲

3

▼

💡 Элегантный подсчёт допустимых разбиений массива путём трекинга баланса

leetcoder, 03-01-2025

Следуюшая задача для нашего разбора: 2270. Number of Ways to Split Array.

Описание задачи 📝

Дан массив целых чисел nums длины n. Требуется найти количество индексов i, где выполняются следующие условия:

• Сумма первых i+1 элементов массива больше или равна сумме оставшихся элементов.
• Индекс i удовлетворяет 0≤i<n−1, то есть правая часть должна содержать хотя бы один элемент.

Идея 💡

Вместо того чтобы каждый раз вычислять суммы левой и правой частей массива, мы используем баланс для их трекинга.
Изначально баланс равен −total_sum, где total_sum — сумма всех элементов массива. На каждом шаге баланс обновляется с помощью текущего элемента, а проверка условий выполняется через простое сравнение баланса с нулём.

Подробности подхода 🛠️

1. Вычислить сумму всех элементов массива и сохранить её в total_sum.
2. Проитерироваться по массиву до предпоследнего элемента:
   • Обновить баланс, добавляя 2×текущий элемент.
   • Если баланс становится больше или равен нулю, увеличивать счётчик допустимых разбиений.
3. Вернуть итоговый счётчик, который отражает количество валидных разбиений.

Читать дальше →

▲

3

▼

🚀 Эффективное разрешение запросов о числе подходящих слов в диапазоне с помощью префиксных сумм

leetcoder, 02-01-2025

Следующая наша задача - 2559. Count Vowel Strings in Ranges.

📝 Описание задачи

Нам дан массив строк words и массив запросов queries, где каждый запрос задаётся парой [li, ri]. Необходимо для каждого запроса определить количество строк из диапазона [li, ri], которые начинаются и заканчиваются на гласные буквы ('a', 'e', 'i', 'o', 'u').
Вернуть массив ответов, где каждый элемент соответствует результату очередного запроса.

💡 Идея

Чтобы эффективно отвечать на диапазонные запросы, мы можем заранее подсчитать кумулятивные суммы валидных строк (начинающихся и заканчивающихся на гласные) в массиве префиксных сумм. Это позволяет сократить обработку каждого запроса до константного времени.

🔍 Подробности подхода

1. Создание префиксных сумм:
   • Сначала создаём итератор prefix_sum_iter, вычисляющий кумулятивное количество "валидных" строк
     (неплохой повод воспользоваться для этого методом std::iter::scan).
   • Добавляем 0 в начало итогового массива (см. std::iter::once и std::iter::chain), чтобы упростить расчёты для запросов (исключая лишнюю проверку условий для обработки начала диапазона).

Читать дальше →

▲

3

▼

🚀 Оптимизация разбиения бинарной строки за один проход

leetcoder, изменено 13-01-2025

Первая задача в этом году - 1422. Maximum Score After Splitting a String несложная, и интересно решить её за один проход по массиву.

📋 Описание задачи

Дана бинарная строка, состоящая из символов 0 и 1.
Требуется найти максимальный результат разбиения строки на две непустые подстроки.
Результат определяется как:

• Результат = (Количество нулей в левой подстроке) + (Количество единиц в правой подстроке).

💡 Идея

Для эффективного решения задачи:

• Рассчитаем динамический баланс для каждого допустимого разбиения строки. Баланс показывает, насколько выгодно разделить строку в конкретной точке.
• Пройдем по строке, обновляя текущий баланс и максимальный результат. Пропустим последнюю итерацию, чтобы обе подстроки оставались непустыми.

🔍 Подробности подхода

1. Формула результата: Для разбиения в точке i:
   • Result = zero_count + (total_ones - ones_count)
     , где:
     • zero_count – число нулей слева

Читать дальше →

▲

3

▼

🚄 Минимизируем затраты на поездки с помощью ДП и техники скользящего окна 🚀

leetcoder, 31-12-2024

Последняя в уходящем году задача 983. Minimum Cost For Tickets требует от нас несложного сочетания техник динамического программирования и скользящего окна.

📜 Условие задачи

У вас есть запланированные дни поездок в течение года, указанные в массиве days. Билеты можно приобрести по следующим ценам:

• Однодневный билет за costs[0] долларов.
• Семидневный билет (покрывает любые последовательно идущие 7 дней) за costs[1] долларов.
• Тридцатидневный билет (покрывает любые последовательно идущие 30 дней) за costs[2] долларов.

Необходимо определить минимальные затраты, чтобы покрыть все дни из списка days.

💡 Идея

Для минимизации затрат можно использовать динамическое программирование.
Основная идея — поочередно вычислять минимальную стоимость для каждой даты из массива days, учитывая разные виды билетов, а также использовать индексы скользящих окон для эффективного вычисления диапазонов покрытия билетов.

🛠️ Детали подхода

1. Создаем массив dp, где dp[i] хранит минимальную стоимость поездок для первых i дней.

Читать дальше →

▲

3

▼

🎯 Динамическое программирование для подсчёта "хороших строк"

leetcoder, 31-12-2024

Сегодня нас опять радует задачка на методы динамического программирования - 2466. Count Ways To Build Good Strings.

😊 Описание задачи

Нам нужно подсчитать количество "хороших строк", длина которых находится в диапазоне [low, high].
Хорошая строка создаётся из пустой строки путём выполнения следующих операций:

• Добавление символа '0' ровно zero раз.
• Добавление символа '1' ровно one раз.

Результат может быть очень большим, поэтому необходимо вернуть его по модулю 10⁹+7.

💡 Идея

Для решения задачи мы используем динамическое программирование.
Каждое состояние dp[length] хранит количество способов построить строку длины length.
Постепенно вычисляя значения для всех длин от 1 до high, мы получаем итоговый результат.

🔍 Подробности подхода

1. Инициализация:
   • Создаём массив dp длиной high+1, где dp[length] будет содержать количество способов построить строку длины length.
   • Базовый случай: dp[0] = 1, так как существует ровно один способ создать пустую строку.

Читать дальше →

▲

3

▼

🧩 Оптимизированный ДП для подсчёта числа способов собрать строку из кусочков

leetcoder, 29-12-2024

Задача - 1639. Number of Ways to Form a Target String Given a Dictionary

🔍 Описание задачи

Дано: список строк words одинаковой длины и строка target.
Цель: определить, сколькими способами можно собрать строку target, следуя правилам:

• В очередной шаг можно использовать символ, совпадающий с необходимым очередным символом target, из любой допустимой позиции таблицы words.
• После выбора символа из определённой позиции все символы всех слов левее или равные этой позиции становятся недоступными.
• Вернуть количество способов по модулю 1_000_000_007

💡 Идея

Мы можем использовать подход динамического программирования. Для быстрого обновления состояний ДП предварительно подсчитаем частоты символов для каждой позиции в words.

Формула ДП:

Пусть dp[i][j] — количество способов собрать первые i символов строки target, используя первые j-й позиции в строках words. Тогда:

dp[i][j] = dp[i][j−1] + dp[i−1][j−1]⋅freqj(target[i]]), где:

Читать дальше →

▲

3

▼

Эффективное разбиение на подмассивы через скользящее окно и динамическое программирование 🚀

leetcoder, 29-12-2024

Новая задача - 689. Maximum Sum of 3 Non-Overlapping Subarrays.

Описание задачи 📜

Дано: массив чисел nums и целое число k.
Задача: найти три непересекающихся подмассива длины k с максимальной суммой и вернуть индексы их начала.
Если существует несколько решений, вернуть лексикографически минимальное.

Идея 💡

Для нахождения оптимального решения нам нужно:

• Вычислить суммы всех подмассивов длины k с помощью техники скользящего окна.
• Найти лучшие индексы подмассивов для правой, средней и левой частей массива, используя динамическое программирование.

Это позволяет эффективно комбинировать результаты и найти оптимальное выделение трёх подмассива.

Детали подхода 🛠️

1. Скользящее окно для вычисления сумм:
   • Вычисляем суммы всех подмассивов длины k, чтобы избежать повторных расчетов.
2. Поиск лучших правых подмассивов:
   • Сканируем массив справа налево, чтобы сохранить индексы подмассивов с максимальной суммой для каждого положения.

Читать дальше →

▲

3

▼

🚀 Поиск оптимальной пары с использованием итераторов

leetcoder, 27-12-2024

Следующая наша задача - 1014. Best Sightseeing Pair.

Описание задачи 📝

Дано: массив values, где

• values[i] — это ценность туристической достопримечательности,
• j-i — расстояние между двумя достопримечательностями i и j.

Требуется: найти пару достопримечательностей (i < j) с максимальной совместной ценностью по формуле:

• score = values[i] + values[j] + i − j

Идея 💡

Основная задача заключается в оптимизации вычислений. Если переписать формулу как:
score = (values[i] + i) + (values[j] − j),
то видно, что для эффективного решения нужно поддерживать максимум для values[j]−j во время итерации.
Это позволяет избежать вложенных циклов и сократить сложность до O(n).

Детали подхода 🛠️

1. Используем обратный обход массива с помощью .enumerate().rev().
2. На каждой итерации:
   • Вычисляем текущую наилучшую ценность: score = values[i] + i + max_right,

Читать дальше →

▲

3

▼

🎯 Эффективный ДП для подсчёта числа возможных целевых комбинаций

leetcoder, 26-12-2024

Сегодня нам предстоит решить задачу 494. Target Sum.

Описание задачи 📜

Нам дана последовательность чисел nums и целевая сумма target.
Необходимо определить количество способов поставить знаки + или - перед числами так, чтобы выражение из всех чисел дало в результате target.

Пример

Для nums = [1, 1, 1, 1, 1] и target = 3, всего 5 правильных комбинаций:

• -1+1+1+1+1
• +1-1+1+1+1
• +1+1-1+1+1
• +1+1+1-1+1
• +1+1+1+1-1

Идея 💡

Эту задачу можно свести к известной задаче о рюкзаке:

• Разделим числа на две группы:
  • Sum_Positive — сумма чисел со знаком +,
  • Sum_Negative — сумма чисел со знаком -.
• Из уравнений:
  • Sum_Positive − Sum_Negative = Target

Читать дальше →

▲

3

▼

🌳🔄 Сортировка уровней дерева через BFS и минимизацию перестановок

leetcoder, 23-12-2024

Очередная наша задача - 2471. Minimum Number of Operations to Sort a Binary Tree by Level

🚀 Описание задачи

Дано бинарное дерево. На каждом уровне дерева нужно отсортировать значения узлов в строго возрастающем порядке, минимизируя количество операций. За одну операцию можно поменять значения двух узлов одного уровня местами.

🧠 Идея

Для решения задачи:
1. Выполним обход дерева по уровням и соберем значения узлов для каждого уровня.
2. Для каждого уровня определим минимальное количество перестановок, необходимых для сортировки значений, используя алгоритм обнаружения циклов.

📋 Подробности подхода

1. Сбор уровней:
   • Используем std::iter::successors для выполнения обхода дерева по уровням.
   • На каждом шаге собираем значения текущего уровня и формируем следующий уровень из дочерних узлов.
2. Минимальные перестановки:
   • Для каждого уровня создаем массив индексов, отсортированный по значениям.
   • Используя алгоритм обнаружения циклов, подсчитываем минимальное количество операций для приведения массива к упорядоченному состоянию.

Читать дальше →

▲

3

▼

🏙️ Эффективное разрешение отложенных запросов с использованием двоичной кучи

leetcoder, изменено 23-12-2024

Задача: 2940. Find Building Where Alice and Bob Can Meet

Описание задачи 📝

У нас есть массив heights, где heights[i] представляет высоту здания i.
Также даны запросы в виде массива queries, где каждый запрос [ai,bi>] требует определить самое левое здание, на которое могут попасть Алиса и Боб, начав с ai​ и bi​ соответственно, при соблюдении следующих условий:

• Алиса и Боб могут двигаться только в здания с индексами больше их текущего.
• Они могут перейти только на здания с высотой больше их текущей.

Если подходящее здание невозможно найти, результат для данного запроса равен −1.

Идея 💡

Мне сходу не известна эффективная структура данных для онлайн-разрешения запросов.
Но можно поступить хитрее, а именно:

• Немедленно обработать "простые" запросы, где результат очевиден.
• Для сложных запросов использовать технику отложенной обработки:
  • Сначала отсортировать их по индексу правого здания.
  • Затем разрешать запросы, итерируясь по зданиям, и, храня кандидатов на разрешение в двоичной куче.

Читать дальше →

▲

3

▼

🌲 Поиск в глубину для оптимального разбиения вершин дерева на специальные компоненты

leetcoder, изменено 23-12-2024

Задача: 2872. Maximum Number of K-Divisible Components

Описание задачи 📋

Дано неориентированное дерево с n узлами, пронумерованными от 0 до n−1. Также даны:
- массив рёбер edges, где каждое ребро связывает два узла,
- массив значений values, где значение values[i] связано с узлом i,
- число k.
- гарантируется, что сумма всех значений values кратна k

Необходимо найти максимальное количество компонентов, на которые можно разделить дерево, удаляя рёбра, чтобы сумма значений в каждом компоненте делилась на k.

Идея 💡

Будем разбивать дерево на компоненты рекурсивно (DFS), начиная с произвольного узла.
Несложно показать, что родительская вершина должна быть в одной компененте со всеми дочерними, для которых сумма значений в соответствующем поддереве не делится на k.

Детали подхода 🚀

1. Построение графа:
   • Представляем дерево в виде списка смежности для удобного обхода.
2. Обход дерева:

Читать дальше →

▲

3

▼

🌳 Обращение значений на нечетных уровнях двоичного дерева || Подход на идее BFS 0-1 🚀

leetcoder, изменено 22-12-2024

На нашей новой задаче 2415. Reverse Odd Levels of Binary Tree есть повод продемонстировать продвинутые методы Rust работы с итераторами (std::iter::successors & std::iter::zip), а также "непристойную" работу c реф-каунт ячейками :(

📜 Описание задачи

Дано идеальное бинарное дерево. Требуется изменить порядок значений узлов на всех нечетных уровнях дерева.
Идеальное дерево — это дерево, где у каждого узла два потомка, а все листья находятся на одном уровне.

💡 Идея

Мы адаптируем BFS для обхода дерева по уровням. На каждом уровне проверяется, нужно ли инвертировать порядок значений (для нечетных уровней). С помощью вспомогательной функции формируются следующие уровни дерева.

📋 Подробности подхода

1. Вспомогательная функция next_level:
   • Формирует следующий уровень дерева, собирая всех левых и правых потомков текущих узлов.
2. Завершение обработки:
   • Проверка, что текущий уровень является листовым, выполняется через условие nodes[0].borrow().left.is_none().
   • При достижении уровня листьев обработка завершается.
3. Обход уровней с помощью std::iter::successors:
   • Используется функциональный подход для последовательного формирования уровней дерева. Итератор автоматически останавливается при достижении листового уровня.

Читать дальше →

▲

4

▼

Shortest write-up ever!

leetcoder, 19-12-2024

Для задачи 769. Max Chunks To Make Sorted у меня есть очень короткое решение, а значит и разбор не стоит делать длинным ;)

Задача: Максимальное количество отсортированных блоков 🧩

Дана перестановка arr длины n. Нужно разделить массив на максимальное количество блоков, таких, что, отсортировав каждый блок по отдельности и объединив их, получится полностью отсортированный массив.

Идея

Вводим функцию баланса, зависящую от частичных сумм по индексам и значениям. Каждый новый блок формируем при нулевых балансах.

Подход

Напишем код самым коротким и непонятным читателю образом, как только умеем.

Сложность:

• O(n) по времени
• O(1) по памяти

Исходный код

impl Solution {
    pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
        arr.into_iter().enumerate().fold(
            (0, 0), |acc, (val, idx)| (
                acc.0 + val as i64 - idx as i64, 
                acc.1 - (acc.0.abs()-1).min(0) as i32)
        ).1
    }
}

▲

3

▼

🛍️ Определение скидок на товары с помощью монотонного стека

leetcoder, 18-12-2024

Сегодняшняя задача 1475. Final Prices With a Special Discount in a Shop решается с помощью стандартного стека, но интересно и нестандартно выглядит мотивация его использования.

Описание задачи 🛒

У вас есть массив цен prices, где prices[i] — это цена i-го товара. Если вы покупаете товар i, вы можете получить скидку, равную цене первого товара с индексом j>i, для которого выполняется условие prices[j] ≤ prices[i]. Если такого товара нет, скидка не применяется. Требуется вернуть массив, где каждая позиция показывает финальную цену с учётом скидки.

Идея 🤔

• Мы идём по массиву цен и обрабатываем товары по порядку.
• Для каждого товара находим, для каких товаров он определяет скидку, проверяя необработанные товары с индексами слева, чья цена больше или равна текущей.
• Чтобы эффективно отслеживать эти необработанные товары, используем монотонный стек. Этот стек хранит индексы товаров, цены которых упорядочены по возрастанию. Это позволяет быстро находить и применять скидки.

Подход 🚀

1. Создаём стек discount_candidates, чтобы хранить индексы товаров, ожидающих применения скидки.
2. Итерируем по массиву prices:
   • Пока верхний элемент стека соответствует условию скидки (цена товара в стеке ≥ текущей цене), применяем скидку и удаляем элемент из стека.

Читать дальше →

▲

3

▼

Жадная сборка строки с ограничениями 😊

leetcoder, 17-12-2024

Сегодня нам предстоит несложная задача - 2182. Construct String With Repeat Limit. Но технически она получилась муторной - требует от программиста очень аккуратного подхода к себе :)

Задача 📜

Дана строка s, состоящая из произвольных символов, и число repeat_limit. Необходимо построить лексикографически максимальную строку, используя символы из s, но с ограничением:

• один и тот же символ не может встречаться более repeat_limit раз подряд.

Подход 🚀

1. Подсчёт частоты символов:
   • Используем массив размера 256, чтобы подсчитать количество вхождений каждого байта (символа).
2. Жадный выбор символов:
   • Обходим пространство символов (0–255), начиная с самого большого.
   • Добавляем текущий символ в результат до repeat_limit раз или пока его количество не исчерпается.
   • Если нужно "разорвать" последовательность, вставляем следующий по величине символ, уменьшая его количество.
3. Эффективный поиск следующего символа:
   • Вспомогательная функция find_last_valid_index ищет ближайший допустимый символ с ненулевой частотой, используя знание о текущем символе как ускоряющую подсказку.

Читать дальше →

▲

3

▼

Очередь с приоритетами для оптимальной подгонки среднего уровня студентов 🎯

leetcoder, 15-12-2024

Сегодня нам предстоит решить задачу 1792. Maximum Average Pass Ratio.

Описание задачи 📚

У нас есть школа, где классы проводят итоговые экзамены. Каждый класс описывается массивом [pass_i,total_i], где:

• pass_i​ — количество учеников,

Читать дальше →

▲

3

▼

💡 Эффективный подсчет с использованием битовых операций

leetcoder, 13-12-2024

Очередная наша задача - 2593. Find Score of an Array After Marking All Elements. Ну и так как наша цель не просто решать, а показывать имплементацию разных техник, то воспользуемся-ка мы идеей битового множества (его в стандартную библиотеку Rust еще "не подвезли", так что и операции имплементируем сами).

Задача 🧩

Дан массив положительных целых чисел nums. Ваша цель — получить максимальное значение score, выполняя следующие действия:

1. Выберите наименьший немаркированный элемент массива (при равенстве — элемент с меньшим индексом).
2. Добавьте значение этого элемента к score.
3. Пометьте выбранный элемент и его двух соседей (если они существуют).
4. Повторяйте, пока все элементы не будут помечены.

Необходимо вернуть итоговое значение score.

Идея 💡

В данной задаче нужно эффективно следовать указанным правилам. Чтобы сделать это:

• (а) Мы отсортируем индексы массива nums по значениям, чтобы обрабатывать элементы в правильном порядке, начиная с наименьших.
• (б) Используем битовое множество (Vec<u128>) для компактного представления состояния "помечен" для элементов массива.

Подход 🚀

Читать дальше →

▲

3

▼

🔥 Модифицированный алгоритм Кадане для подмассивов с длиной, кратной k

leetcoder, 13-12-2024

Очередная наша задача - 3381. Maximum Subarray Sum With Length Divisible by K

Описание задачи

Дано целое число k и массив чисел nums. Необходимо найти максимальную сумму подмассива, длина которого кратна k.

🚀 Идея

Данная задача расширяет классический алгоритм нахождения максимальной суммы подмассива (алгоритм Кадане) для случаев, когда длина подмассива должна быть кратной k. Чтобы учесть это условие, мы перебираем все смещения в полуинтервале [0,k) и анализируем подмассивы с шагом k.

🔍 Подход

1. Префиксные суммы:
   • Вычисляем массив префиксных сумм, чтобы быстро находить сумму любого подмассива.
2. Перебор смещений:
   • Итерируем по всем возможным начальным смещениям [0,k), чтобы обрабатывать подмассивы длиной, кратной k.
3. Модификация алгоритма Кадане:
   • Для каждого смещения применяем алгоритм нахождения максимальной суммы подмассива.
   • Если текущая сумма становится отрицательной, начинаем новый расчет с текущей позиции (сброс индекса начала подмассива).

Читать дальше →

▲

3

▼

Скользящее окно для максимизации "красоты массива" 🌟

leetcoder, 11-12-2024

Сегодня рассмотрим достаточно простое решение задачи 2779. Maximum Beauty of an Array After Applying Operation.

Условие 📋

Дан массив nums и целое неотрицательное число k. Разрешается заменить каждый элемент массива (не более одного раза) любым числом из диапазона [nums[i]−k,nums[i]+k]. Требуется найти максимальную длину подпоследовательности массива, состоящей из одинаковых элементов (это называется "красота массива").

Идея 💡

Фактически задача сводится к нахождению наибольшего подмножества массива, все элементы которого укладываются в интервал длины 2×k. Чтобы эффективно найти такой диапазон, можно использовать метод скользящего окна по предварительно отсортированному массиву.

Подход 🛠️

1. Сортировка массива: Упорядочиваем массив, чтобы элементы, которые могут принадлежать одному диапазону, оказались рядом.
2. Скользящее окно: Используем два указателя (l и r) для определения максимального диапазона, удовлетворяющего условию nums[r]−nums[l]≤2×k.
3. Подсчёт длины диапазона: На каждом шаге обновляем результат как максимум текущей длины окна r−l.

Асимптотика 📊

• Временная сложность: O(nlog⁡n) из-за сортировки + O(n) для скользящего окна, итого O(nlog⁡n).
• Пространственная сложность: O(1), если используется сортировка "на месте".

Исходный код решения

impl Solution {
    pub fn maximum_beauty(nums: Vec<i32>, k: i32) -> i32 {
        // Create a mutable copy of nums and sort it
        let mut sorted_nums = nums.clone();
        sorted_nums.sort_unstable();

        let mut max_beauty = 0;
        let mut right = 0;

        // Iterate over each number in the sorted array
        for left in 0..sorted_nums.len() {
            // Expand the right pointer as long as the difference is within the allowed range
            while right < sorted_nums.len() && sorted_nums[right] <= sorted_nums[left] + 2 * k {
                right += 1;
            }
            // Update the maximum beauty based on the current window size
            max_beauty = max_beauty.max((right - left) as i32);
        }

        max_beauty
    }
}

▲

3

▼

🏆 Оптимальный анализ подстрок, состоящих из одного символа

leetcoder, 10-12-2024

На этот раз наша задача выглядит заковыристо - 2982. Find Longest Special Substring That Occurs Thrice II.

📝 Описание задачи

Необходимо найти длину самой длинной "особенной" подстроки, которая встречается в строке хотя бы три раза. Если такой подстроки нет, вернуть -1.

"Особенная" подстрока — это подстрока, содержащая один и тот же символ.

😊 Идея

Отбросим сразу идею перебора всех возможных подстрок (что крайне неэффективно).
Вместо этого мы сосредоточимся на последовательных участках каждого символа.
Для каждого символа достаточно рассмотреть только длины его подряд идущих сегментов, и это позволит нам эффективно вычислить искомый результат.

🚀 Подход

1. Перебираем все строчные английские буквы ('a' до 'z').
2. Для каждой буквы:
   • Находим все её подряд идущие сегменты (например, для 'aaaabbaab' сегменты: [4,2], [2,1] для 'a' и 'b').
   • Сортируем длины сегментов по убыванию.
   • Вычисляем максимальную возможную длину "особенной" подстроки, встречающейся как минимум три раза, используя метод get_triple_length.

Читать дальше →

▲

4

▼

🔢 Префиксные суммы для быстрой проверки на чередование чётности в подмассиве

leetcoder, 09-12-2024

Задача на сегодня 3152. Special Array II.

📝 Условие:

• Нам дан массив nums и запросы queries.
• Для каждого запроса [from, to] нужно проверить, является ли подмассив nums[from..=to] "особым".
• Подмассив считается "особым", если каждая пара соседних элементов в нём имеет разную чётность (один чётный, другой нечётный).

🧠 Идея:

• Решение основано на идее "вычисли один раз — используй много раз".
• Сначала выполняем линейные предвычисления префиксных количеств пар соседних элементов разной чётности.
• Затём каждый запрос обрабатывается мгновенно за O(1), что делает решение особенно эффективным для больших массивов и множества запросов 😊

💡 Подход:

1. Префиксная сумма:
   • Создаём массив prefix_count, где prefix_count[i] хранит количество пар соседних элементов с разной чётностью от начала массива до индекса i.
   • Заполняем его за O(n) в одном проходе.
2. Обработка запросов:
   • Для каждого запроса [from, to] считаем количество таких пар в диапазоне через разность: prefix_count[to] - prefix_count[from].

Читать дальше →

▲

4

▼

🏆 Максимальная ценность не более чем двух независимых событий

leetcoder, 08-12-2024

Сегодня решаем задачу 2054. Two Best Non-Overlapping Events. Будем закреплять двоичный поиск ;)

😇 Описание задачи

Дан список событий с известными для них start_time, end_time и value. Нужно выбрать максимум два непересекающихся события с максимальной общей ценностью. События пересекаются, если одно начинается до окончания другого.

💡 Идея

Сортируем события по end_time (в убывающем порядке). Для каждого события используем двоичный поиск, чтобы найти все заканчивающиеся до его начала. Остаётся найти среди них событие с максимальной ценностью, для этого будем хранить накопленные максимальные ценности в отдельном массиве max_vals.

🛠️ Подход

1. Сортировка событий: По end_time в порядке убывания.
2. Предобработка максимальных ценностей: Создаём массив max_vals с накопленной максимальной ценностью событий (справа-налево).
3. Итерация и поиск:
   • Для каждого события находим первое, заканчивающееся раньше его, через двоичный поиск.
   • Суммируем ценности текущего события и накопленной максимальной ценности по найденному индексу, обновляя общий максимум.

Читать дальше →