Задача - 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]]), где:
Читать дальше →
ответить
В следующей задаче - 2661. First Completely Painted Row or Column можно не симулировать в лоб, и за счёт этого сэкономить память при решении (хоть и не получится асимптотически лучше).
📋 Описание задачи
- Нам дан массив
arr и матрица mat, содержащие числа от 1 до m * n.
- Массив
arr задаёт порядок закраски ячеек матрицы mat (закрашивается ячейка, содержащая указанное число).
- В следующем примере:
arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
Необходимо найти первый такой индекс i в массиве arr, при котором:
- Либо вся строка, либо весь столбец матрицы окажется закрашенным.
💡 Идея
Задачу можно переформулировать:
- Каждая строка и каждый столбец закрашиваются, если все элементы строки/столбца обработаны в порядке массива
arr.
- Получается, что для решения задачи нужно:
- Найти максимальный индекс появления значений из
arr для каждой строки/столбца.
Читать дальше →
ответить
Задача на выходные - 2097. Valid Arrangement of Pairs
Описание задачи 📜
Нужно переставить заданные пары [starti,endi] так, чтобы получилось корректное расположение,
где для каждой пары i: endi−1=starti. Гарантируется, что такое расположение существует.
Обзор решения 🛠
Для решения задачи используется алгоритм Хирхольцера, который позволяет построить Эйлеров путь (или цикл) в ориентированном графе. Основная идея — удалять рёбра во время обхода, что упрощает структуру данных и предотвращает повторное использование рёбер.
Ключевые шаги 🚀
-
Построение графа:
- Граф представляется в виде списка смежности (
HashMap<i32, Vec<i32>>), где каждая вершина хранит список своих исходящих рёбер.
- Параллельно вычисляются разницы степеней вершин (входящих и исходящих рёбер) для определения начальной вершины пути.
-
Поиск начальной вершины:
- Начальная вершина — это вершина с положительным балансом исходящих рёбер. Если таких нет, берётся любая вершина из входных данных.
-
Итеративный DFS с удалением рёбер:
- Вместо стандартного рекурсивного DFS используется итеративный подход с явным стеком. Это повышает эффективность памяти и скорость.
- При посещении вершины рёбра удаляются из списка смежности, что гарантирует, что каждое ребро используется ровно один раз.
Читать дальше →
ответить
Задача: 2872. Maximum Number of K-Divisible Components
Описание задачи 📋
Дано неориентированное дерево с n узлами, пронумерованными от 0 до n−1. Также даны:
- массив рёбер edges, где каждое ребро связывает два узла,
- массив значений values, где значение values[i] связано с узлом i,
- число k.
- гарантируется, что сумма всех значений values кратна k
Необходимо найти максимальное количество компонентов, на которые можно разделить дерево, удаляя рёбра, чтобы сумма значений в каждом компоненте делилась на k.
Идея 💡
Будем разбивать дерево на компоненты рекурсивно (DFS), начиная с произвольного узла.
Несложно показать, что родительская вершина должна быть в одной компененте со всеми дочерними, для которых сумма значений в соответствующем поддереве не делится на k.
Детали подхода 🚀
-
Построение графа:
- Представляем дерево в виде списка смежности для удобного обхода.
-
Обход дерева:
Читать дальше →
ответить
Ссылка на задачу — 2460. Apply Operations to an Array.
📝 Описание задачи
Дан массив nums, состоящий из неотрицательных целых чисел. Нужно последовательно выполнить следующие операции:
- Для каждого валидного
i (в порядке возрастания):
- eсли
nums[i] == nums[i + 1], удвоить nums[i] и заменить nums[i + 1] на 0.
- После всех операций сдвинуть все нули в конец массива, сохраняя порядок оставшихся чисел.
- Вернуть изменённый массив.
💡 Идея
Решение можно выполнить за один проход, используя два указателя (read и write):
- Читаем массив и объединяем соседние одинаковые элементы.
- Перемещаем ненулевые элементы в начало массива.
- Оставшиеся ячейки заполняем нулями.
Такой подход позволяет изменять массив на месте, не используя дополнительную память.
📌 Детали подхода
- Используем два указателя (
read и write):
read проходит по массиву.write отслеживает следующую позицию для ненулевых чисел.
Читать дальше →
ответить
Сегодня мы разберём задачу 916. Word Subsets.
📝 Описание задачи
Вам даны два массива строк words1 и words2.
Задача: найти все строки из words1, которые являются универсальными относительно всех строк из words2.
Условие универсальности:
Строка a из words1 универсальна, если для каждой строки b из words2 строка b является подмножеством строки a (Подмножество строки: строка b является подмножеством строки a, если каждая буква в b встречается в a как минимум столько же раз).
Пример:
["warrior", "world"] и ["wrr"]
Ответ: ["warrior"], так как только warrior покрывает все буквы из wrr.
💡 Идея
Для эффективного решения задачи:
- Определим максимальное количество вхождений каждой буквы по всем строкам из words2.
- Для каждой строки из words1 проверим, удовлетворяет ли она этим требованиям.
🔍 Детали подхода
Читать дальше →
ответить
Наша очередная задача - 1930. Unique Length-3 Palindromic Subsequences.
📝 Описание задачи
Дана строка s. Необходимо определить количество уникальных палиндромов длины 3, которые являются подпоследовательностями строки.
Подпоследовательность — это строка, полученная из исходной строки удалением некоторых (возможно, нуля) символов без изменения их порядка. Например, для строки "abcde" строка "ace" является подпоследовательностью.
Палиндром — это строка, которая читается одинаково в прямом и обратном направлениях.
💡 Идея
Основная идея заключается в том, что палиндром длины 3 определяется первыми и последними символами, которые совпадают, а также любым допустимым символом посередине.
Мы можем эффективно отслеживать такие пары (первый и последний символы) с помощью битового массива (bitset), что позволяет минимизировать использование памяти.
🔍 Детали подхода
- Массивы частот:
prefix_frequency: хранит частоты символов слева от рассматриваемого.suffix_frequency: хранит частоты символов справа от рассматриваемого.
Читать дальше →
ответить
Сегодня нам предстоит решить задачу 2577. Minimum Time to Visit a Cell In a Grid.
📝 Описание задачи
- Дана матрица
grid размером m x n, где каждая ячейка (row, col) содержит время открытия ворот, ведущих в эту ячейку. До этого времени в ячейку попасть нельзя.
- Вы начинаете в ячейке (
0, 0) с временем 0 и можете двигаться на 1 ячейку за секунду в любом из 4 направлений (вверх, вниз, влево, вправо).
- Важно: стоять на месте запрещено — вы должны перемещаться на каждое движение.
- Цель — найти минимальное время, чтобы добраться до ячейки (
m-1, n-1). Если это невозможно, вернуть -1.
💡 Идея
Задача сводится к поиску кратчайшего пути с учётом времени открытия ворот в каждой ячейке. Можно представить задачу как динамический граф, где вершины — это пары (время, ячейка), а рёбра — это возможные переходы между ячейками. Вместо того чтобы хранить весь граф, мы динамически вычисляем возможные переходы из посещаемых вершин. Вершины будем перебирать в порядке времён достижимости ячейки (как в алгоритме Дейкстры).
🔑 Подход к решению
- 🧑💻 Графовая модель:
- Ячейки матрицы — вершины графа.
- Рёбра между вершинами имеют вес
1.
Читать дальше →
ответить
Задача, что мы рассмотрим сегодня - 2948. Make Lexicographically Smallest Array by Swapping Elements
📝 Описание задачи:
- Дан массив положительных чисел
nums и положительное число limit.
- Разрешено менять местами элементы массива
nums[i] и nums[j], если выполняется условие:
|nums[i] - nums[j]| <= limit.
- Необходимо получить лексикографически минимальный массив, выполняя такие операции любое количество раз.
Лексикографический порядок: Массив a меньше массива b, если на первой позиции i, где они различаются, a[i] < b[i].
💡 Идея:
Будем эксплуатировать следующие замечания:
- Элементы могут менять местами только внутри определённых групп, где (после её вырезания и сортировки) выполняется условие:
|nums[group[i+1]] - nums[group[i]]| <= limit.
- Индексная сортировка по значениям
nums поможет нас найти группы, внутри которых возможны перестановки.
- Сортировка каждой из этих групп может быть эффективно выполнена с помощью дополнительного индексного массива.
🔍 Детали подхода:
- Сортировка индексов: На первом шаге создаём массив
sorted_indices, заполняя его значениями [0, 1, ..., n-1]. Затем сортируем этот массив по значениям массива nums, чтобы определить относительный порядок элементов.
Читать дальше →
ответить
Сегодня нам предстоит решить задачу 1792. Maximum Average Pass Ratio.
Описание задачи 📚
У нас есть школа, где классы проводят итоговые экзамены. Каждый класс описывается массивом [pass_i,total_i], где:
pass_i — количество учеников,
Читать дальше →
2 ответа
На этот раз наша задача выглядит заковыристо - 2982. Find Longest Special Substring That Occurs Thrice II.
📝 Описание задачи
Необходимо найти длину самой длинной "особенной" подстроки, которая встречается в строке хотя бы три раза. Если такой подстроки нет, вернуть -1.
"Особенная" подстрока — это подстрока, содержащая один и тот же символ.
😊 Идея
Отбросим сразу идею перебора всех возможных подстрок (что крайне неэффективно).
Вместо этого мы сосредоточимся на последовательных участках каждого символа.
Для каждого символа достаточно рассмотреть только длины его подряд идущих сегментов, и это позволит нам эффективно вычислить искомый результат.
🚀 Подход
- Перебираем все строчные английские буквы (
'a' до 'z').
- Для каждой буквы:
- Находим все её подряд идущие сегменты (например, для
'aaaabbaab' сегменты: [4,2], [2,1] для 'a' и 'b').
- Сортируем длины сегментов по убыванию.
- Вычисляем максимальную возможную длину "особенной" подстроки, встречающейся как минимум три раза, используя метод
get_triple_length.
Читать дальше →
4 ответа
Ссылка на задачу – 3105. Longest Strictly Increasing or Strictly Decreasing Subarray.
😎 Описание задачи
Дан массив целых чисел nums. Необходимо найти длину самой длинной последовательности, которая является либо строго возрастающей, либо строго убывающей.
🤔 Идея
Разбить массив на группы (чанки) по непрерывной монотонности (либо возрастающей, либо убывающей).
Для каждой группы вычислить её длину, а затем выбрать максимальное значение среди всех групп.
🚀 Детали подхода
- Разбиение на чанки:
Используем метод chunk_by для разбиения массива:
- Для строго возрастающей последовательности используем сравнение
a < b.
- Для строго убывающей последовательности используем сравнение
a > b.
- Вычисление максимальной длины:
- Для каждого набора чанков вычисляем длину каждой группы, выбираем максимальную длину для возрастающих и убывающих групп.
- Результат:
- Возвращаем максимум между максимальной длиной возрастающей и максимальной длиной убывающей последовательности.
⏱ Асимптотика
- Время:
O(n) — каждый элемент обрабатывается один раз при разбиении на чанки.
- Память:
O(1) — используется дополнительная память только для итераторов, не зависящая от размера входного массива.
📜 Исходный код
impl Solution {
pub fn longest_monotonic_subarray(nums: Vec<i32>) -> i32 {
// Group strictly increasing segments using chunk_by
let max_increasing_len = nums.chunk_by(|a, b| a < b)
.map(|c| c.len()).max().unwrap_or(0);
// Group strictly decreasing segments using chunk_by
let max_decreasing_len = nums.chunk_by(|a, b| a > b)
.map(|c| c.len()).max().unwrap_or(0);
max_increasing_len.max(max_decreasing_len) as i32
}
}
Tags: #rust #algorithms #iterators
1 ответ
Задача на сегодня 3152. Special Array II.
📝 Условие:
- Нам дан массив
nums и запросы queries.
- Для каждого запроса
[from, to] нужно проверить, является ли подмассив nums[from..=to] "особым".
- Подмассив считается "особым", если каждая пара соседних элементов в нём имеет разную чётность (один чётный, другой нечётный).
🧠 Идея:
- Решение основано на идее "вычисли один раз — используй много раз".
- Сначала выполняем линейные предвычисления префиксных количеств пар соседних элементов разной чётности.
- Затём каждый запрос обрабатывается мгновенно за
O(1), что делает решение особенно эффективным для больших массивов и множества запросов 😊
💡 Подход:
-
Префиксная сумма:
- Создаём массив
prefix_count, где prefix_count[i] хранит количество пар соседних элементов с разной чётностью от начала массива до индекса i.
- Заполняем его за
O(n) в одном проходе.
-
Обработка запросов:
- Для каждого запроса
[from, to] считаем количество таких пар в диапазоне через разность: prefix_count[to] - prefix_count[from].
Читать дальше →
ответить
Ссылка на задачу - 2161. Partition Array According to Given Pivot.
В данной задаче нам предстоит реализовать базовую подзадачу Быстрой сортировки, но с дополнительным требованием сохранения относительного порядка, отчего стандартные методы реализации Q-sort нас не будут устраивать ☹
📌 Описание задачи
Дан массив nums и число pivot. Требуется переставить элементы массива так, чтобы:
- Все элементы меньше
pivot шли первыми.
- Все элементы равные
pivot находились в середине.
- Все элементы больше
pivot шли в конце.
- Относительный порядок элементов в каждой группе сохранялся.
💡 Идея
Мы хотим разделить массив на три части, не создавая лишние структуры данных.
Вместо этого заполним результирующий вектор напрямую, обрабатывая массив в три прохода.
🛠️ Детали подхода
1️⃣ Первый проход: добавляем в результат все элементы < pivot.
2️⃣ Подсчет и второй проход: вычисляем количество вхождений pivot в массиве и добавляем pivot в результат pivot_count раз.
3️⃣ Третий проход: добавляем все элементы > pivot в результат.
Используем Vec::with_capacity(nums.len()), чтобы избежать лишних аллокаций.
📊 Асимптотика
- Временная сложность:
O(n) — три прохода по nums.
- Дополнительная память:
O(1) — все данные хранятся только в результирующем массиве
(который всё же имеет размер O(n)).
💻 Исходный код
impl Solution {
pub fn pivot_array(nums: Vec<i32>, pivot: i32) -> Vec<i32> {
let mut result = Vec::with_capacity(nums.len());
// First pass: Collect elements smaller than pivot
result.extend(nums.iter().filter(|&&num| num < pivot));
// Count occurrences of pivot
let pivot_count = nums.iter().filter(|&&num| num == pivot).count();
// Insert pivot elements
result.extend(std::iter::repeat(pivot).take(pivot_count));
// Third pass: Collect elements greater than pivot using into_iter() to take ownership
result.extend(nums.into_iter().filter(|&num| num > pivot));
result
}
}
Tags: #rust #algorithms
1 ответ
Задача на сегодня 1368. Minimum Cost to Make at Least One Valid Path in a Grid - достаточно стандартная вариация лабиринта с бесплатными переходами.
📝 Описание задачи
У нас есть поле размером m×n, где каждая клетка содержит указание направления движения. Необходимо найти минимальную стоимость перехода из левого верхнего угла (0, 0) в правый нижний угол (m−1,n−1).
Каждая клетка указывает направление движения:
1 — вправо,2 — влево,3 — вниз,4 — вверх.
Изменение направления перехода возможно, но со стоимостью 1, и его можно выполнить только один раз для каждой клетки.
💡 Идея
Поле можно рассматривать как ориентированный граф, где клетки являются вершинами, а направления задают ребра. Наша цель — найти минимальную стоимость пути из начальной клетки в конечную. Для этого используется модифицированный BFS с двумя очередями, где приоритет отдается движениям без изменения направления.
🛠️ Детали подхода
- Две очереди:
Читать дальше →
ответить
Ссылка на задачу — 889. Construct Binary Tree from Preorder and Postorder Traversal.
📌 Описание задачи
Нам даны прямой (preorder) и обратный (postorder) обходы бинарного дерева.
Необходимо восстановить дерево по этим обходам.
Основные свойства обходов:
- Preorder (прямой обход):
[корень → левый → правый]
- Postorder (обратный обход):
[левый → правый → корень]
💡 Идея
Для построения дерева используем рекурсивный подход, основанный на двух ключевых наблюдениях:
- 1️⃣ Каждый новый узел получает значение из
preorder
→ так мы всегда сначала создаем корень поддерева.
- 2️⃣ Поддерево считается полностью построенным, когда его значение встречается в
postorder
→ это сигнал к завершению рекурсии.
🔍 Детали подхода
- Используем итераторы
Peekable<Iterator> для эффективного прохода по preorder и postorder.
- Берем значение из
preorder и создаем новый узел.
- Рекурсивно создаем левое поддерево, если
postorder пока не указывает на текущий корень.
Читать дальше →
ответить
Ссылка на задачу — 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
ответить
Ссылка на задачу - 1780. Check if Number is a Sum of Powers of Three.
📌 Описание задачи
Дано число n. Нужно определить, можно ли представить его в виде суммы различных степеней тройки.
🔹 Пример:
- 📥 Ввод:
n = 12
- 📤 Вывод:
true
- 💡 Объяснение:
12 = 3⁰+3¹+3² = 1 + 3 + 9.
💡 Идея
Рассмотрим представление n в троичной системе счисления:
- Если в записи числа есть цифра
2, то решения нет (так как нельзя взять две одинаковые степени).
- Если в записи есть только
0 и 1, то решение существует (мы просто берём соответствующие степени тройки).
Таким образом, задача сводится к поразрядной проверке числа в троичной системе счисления.
🚀 Детали подхода
Будем использовать рекурсию и деление числа на 3:
- База рекурсии: Если
n == 0, то мы успешно разложили число, возвращаем true.
- Шаг рекурсии: Если
n % 3 == 2, то n нельзя разложить, возвращаем false.
- Рекурсивный вызов: Проверяем
n / 3, повторяя процесс.
⏱ Асимптотика
- Временная сложность:
O(log n), так как n уменьшается в 3 раза за итерацию.
- Пространственная сложность:
O(log n) из-за глубины рекурсии
(несложно алгоритм преобразовать в цикл, чтобы получить O(1)).
📝 Исходный код
impl Solution {
pub fn check_powers_of_three(n: i32) -> bool {
n == 0 || (n % 3 != 2 && Self::check_powers_of_three(n / 3))
}
}
Tags: #rust #algorithms #math
ответить
Сегодня у нас интересная задача на битовые манипуляции – 2429. Minimize XOR.
📜 Описание задачи
Дано два положительных числа num1 и num2. Нужно найти число x, такое что:
- Количество установленных битов в числе
x равно количеству установленных битов в num2.
- Результат операции
XOR между x и num1 минимален.
💡 Идея
Для минимизации XOR мы
- Стремимся сохранить как можно больше старших битов из числа num1, так как они оказывают наибольшее влияние на минимизацию результата.
- Если остаются неиспользованные биты, мы добавляем младшие биты, чтобы завершить формирование числа x с требуемым количеством установленных битов.
✨ Детали подхода
-
Подсчёт установленных битов:
- Используем метод
count_ones, чтобы подсчитать количество установленных битов в числе num2.
-
Сохранение старших битов:
- Проходим по битам
num1 с самого старшего до младшего.
- Если бит установлен, включаем его в результат и уменьшаем счётчик оставшихся битов.
Читать дальше →
1 ответ
Ссылка на задачу – 1726. Tuple with Same Product.
📜 Описание задачи
Дан массив nums из различных положительных чисел. Нужно вернуть количество кортежей (a, b, c, d), таких что произведение a * b равно произведению c * d, при условии, что все элементы кортежа различны.
💡 Идея
- Для каждой уникальной пары элементов из массива nums вычисляем произведение и подсчитываем частоту его появления с помощью HashMap.
- Для каждого произведения, встречающегося больше одного раза необходимо учесть, что существует 8 уникальных вариантов составления кортежей:
a*b=c*d; a*b=d*c; b*a=c*d; b*a=d*c; c*d=a*b; c*d=b*a; d*c=a*b; d*c=b*a
- Соответственно, итоговый вклад, каждого произведения вычисляется как
4 * frequency * (frequency - 1)
🔍 Детали подхода
- Подсчет в HashMap:
- Используем два вложенных цикла для перебора всех уникальных пар
(i, j) с условием i < j и вычисляем их произведение.
- Результаты произведений сохраняем в
HashMap, где ключ — это само произведение, а значение — количество его вхождений.
- Расчет кортежей:
- Для каждого произведения с частотой больше
1, добавляем в итоговый результат значение
4 * frequency * (frequency - 1).
- Возврат результата:
Читать дальше →
1 ответ
Первая задача в этом году - 1422. Maximum Score After Splitting a String несложная, и интересно решить её за один проход по массиву.
📋 Описание задачи
Дана бинарная строка, состоящая из символов 0 и 1.
Требуется найти максимальный результат разбиения строки на две непустые подстроки.
Результат определяется как:
Результат = (Количество нулей в левой подстроке) + (Количество единиц в правой подстроке).
💡 Идея
Для эффективного решения задачи:
- Рассчитаем динамический баланс для каждого допустимого разбиения строки. Баланс показывает, насколько выгодно разделить строку в конкретной точке.
- Пройдем по строке, обновляя текущий баланс и максимальный результат. Пропустим последнюю итерацию, чтобы обе подстроки оставались непустыми.
🔍 Подробности подхода
- Формула результата: Для разбиения в точке
i:
Result = zero_count + (total_ones - ones_count)
, где:
zero_count – число нулей слева
Читать дальше →
ответить
Сегодня нас опять радует задачка на методы динамического программирования - 2466. Count Ways To Build Good Strings.
😊 Описание задачи
Нам нужно подсчитать количество "хороших строк", длина которых находится в диапазоне [low, high].
Хорошая строка создаётся из пустой строки путём выполнения следующих операций:
- Добавление символа
'0' ровно zero раз.
- Добавление символа
'1' ровно one раз.
Результат может быть очень большим, поэтому необходимо вернуть его по модулю 10⁹+7.
💡 Идея
Для решения задачи мы используем динамическое программирование.
Каждое состояние dp[length] хранит количество способов построить строку длины length.
Постепенно вычисляя значения для всех длин от 1 до high, мы получаем итоговый результат.
🔍 Подробности подхода
- Инициализация:
- Создаём массив
dp длиной high+1, где dp[length] будет содержать количество способов построить строку длины length.
- Базовый случай:
dp[0] = 1, так как существует ровно один способ создать пустую строку.
Читать дальше →
ответить
Сегодня рассмотрим достаточно простое решение задачи 2779. Maximum Beauty of an Array After Applying Operation.
Условие 📋
Дан массив nums и целое неотрицательное число k. Разрешается заменить каждый элемент массива (не более одного раза) любым числом из диапазона [nums[i]−k,nums[i]+k]. Требуется найти максимальную длину подпоследовательности массива, состоящей из одинаковых элементов (это называется "красота массива").
Идея 💡
Фактически задача сводится к нахождению наибольшего подмножества массива, все элементы которого укладываются в интервал длины 2×k. Чтобы эффективно найти такой диапазон, можно использовать метод скользящего окна по предварительно отсортированному массиву.
Подход 🛠️
- Сортировка массива: Упорядочиваем массив, чтобы элементы, которые могут принадлежать одному диапазону, оказались рядом.
- Скользящее окно: Используем два указателя (
l и r) для определения максимального диапазона, удовлетворяющего условию nums[r]−nums[l]≤2×k.
- Подсчёт длины диапазона: На каждом шаге обновляем результат как максимум текущей длины окна
r−l.
Асимптотика 📊
- Временная сложность:
O(nlogn) из-за сортировки + O(n) для скользящего окна, итого O(nlogn).
- Пространственная сложность:
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
}
}
На нашей новой задаче 2415. Reverse Odd Levels of Binary Tree есть повод продемонстировать продвинутые методы Rust работы с итераторами (std::iter::successors & std::iter::zip), а также "непристойную" работу c реф-каунт ячейками :(
📜 Описание задачи
Дано идеальное бинарное дерево. Требуется изменить порядок значений узлов на всех нечетных уровнях дерева.
Идеальное дерево — это дерево, где у каждого узла два потомка, а все листья находятся на одном уровне.
💡 Идея
Мы адаптируем BFS для обхода дерева по уровням. На каждом уровне проверяется, нужно ли инвертировать порядок значений (для нечетных уровней). С помощью вспомогательной функции формируются следующие уровни дерева.
📋 Подробности подхода
-
Вспомогательная функция
next_level:
- Формирует следующий уровень дерева, собирая всех левых и правых потомков текущих узлов.
-
Завершение обработки:
- Проверка, что текущий уровень является листовым, выполняется через условие
nodes[0].borrow().left.is_none().
- При достижении уровня листьев обработка завершается.
-
Обход уровней с помощью
std::iter::successors:
- Используется функциональный подход для последовательного формирования уровней дерева. Итератор автоматически останавливается при достижении листового уровня.
Читать дальше →
ответить
Очередная наша задача - 2593. Find Score of an Array After Marking All Elements. Ну и так как наша цель не просто решать, а показывать имплементацию разных техник, то воспользуемся-ка мы идеей битового множества (его в стандартную библиотеку Rust еще "не подвезли", так что и операции имплементируем сами).
Задача 🧩
Дан массив положительных целых чисел nums. Ваша цель — получить максимальное значение score, выполняя следующие действия:
- Выберите наименьший немаркированный элемент массива (при равенстве — элемент с меньшим индексом).
- Добавьте значение этого элемента к
score.
- Пометьте выбранный элемент и его двух соседей (если они существуют).
- Повторяйте, пока все элементы не будут помечены.
Необходимо вернуть итоговое значение score.
Идея 💡
В данной задаче нужно эффективно следовать указанным правилам. Чтобы сделать это:
- (а) Мы отсортируем индексы массива nums по значениям, чтобы обрабатывать элементы в правильном порядке, начиная с наименьших.
- (б) Используем битовое множество (
Vec<u128>) для компактного представления состояния "помечен" для элементов массива.
Подход 🚀
Читать дальше →
ответить
Страница
1
2
3
4
