главная новое лучшее написать
3

Сегодня мы разберём задачу 916. Word Subsets.

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

Вам даны два массива строк words1 и words2.

Задача: найти все строки из words1, которые являются универсальными относительно всех строк из words2.

Условие универсальности:
Строка a из words1 универсальна, если для каждой строки b из words2 строка b является подмножеством строки a (Подмножество строки: строка b является подмножеством строки a, если каждая буква в b встречается в a как минимум столько же раз).

Пример:

💡 Идея

Для эффективного решения задачи:
- Определим максимальное количество вхождений каждой буквы по всем строкам из words2.
- Для каждой строки из words1 проверим, удовлетворяет ли она этим требованиям.

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

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

ответить
3

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

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

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

Идея 🔄

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

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

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

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

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

ответить
3

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

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

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

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

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

💡 Идея

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

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

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

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

ответить
3

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

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

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

Идея 💡

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

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

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

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

ответить
3

Следующая наша задача - 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

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

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

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

💡 Идея

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

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

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

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

ответить
4

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

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

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

Идея

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

Подход

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

Сложность:

Исходный код

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
    }
}

5 ответов
3

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

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

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

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

💡 Идея

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

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

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

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

ответить
4

Страшилку "серой слизи" изобрел футуролог Эрик Дрекслер еще в прошлом веке. Суть идеи в том, что самовоспроизводящиеся наноботы, если упустить их из лаборатории, могут начать бесконечно копировать себя, и в результате Земля превратится в бесформенную "серую слизь", состоящую из гигантской массы нанороботов.

В 2024 году даже самые параноидальные исследователи экзистенциальных рисков относятся к "серой слизи" не слишком всерьёз. Мы не умеем делать самовоспроизводящихся наноботов и вряд ли научимся до того, как изобретём сильный искусственный интеллект который все равно нас уничтожит, с наноботами или без них.

Да?

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

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

Почему так происходит, ведь вроде бы законы химии инвариантны относительно зеркальной симметрии? Дело в том, в этом смысле почему-то несимметричны все живые существа. Аминокислоты, из которых состоят белки, в природе существуют почти исключительно в "левой" форме, а сахара, например, глюкоза, только в "правой". Хотя при замене хиральности у всех молекул, участвующих в реакции, ничего не поменялось бы, если заменить хиральность только у части из них, она может пойти совсем иначе, поэтому то, что жизнь несимметрична, важно.

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

3 ответа
3

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

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

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

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

💡 Идея

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

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

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

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

ответить
3

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

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

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

💡 Идея

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

Формула ДП:

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

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

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

ответить
3

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

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

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

Идея 💡

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

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

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

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

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

ответить
3

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

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

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

Требуется: найти пару достопримечательностей (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

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

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

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

Пример

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

Идея 💡

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

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

ответить
3

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

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

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

🧠 Идея

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

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

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

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

ответить
3

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

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

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

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

Идея 💡

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

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

ответить
3

Задача: 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

На нашей новой задаче 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:
    • Используется функциональный подход для последовательного формирования уровней дерева. Итератор автоматически останавливается при достижении листового уровня.

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

ответить
3

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

Задача 📜

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

Подход 🚀

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

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

2 ответа
3

Сегодняшняя задача 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

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

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

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

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

2 ответа
3

На этот раз наша задача выглядит заковыристо - 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 ответа
3

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

Задача 🧩

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

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

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

Идея 💡

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

Подход 🚀

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

ответить
3

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

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

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

🚀 Идея

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

🔍 Подход

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

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

ответить
3

Сегодня рассмотрим достаточно простое решение задачи 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.

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

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

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
    }
}

ответить

Страница 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17