Условие задачи — 2503. Maximum Number of Points From Grid Queries.
📘 Условие задачи
- Дана матрица
grid размером m × n и массив целых чисел queries, каждый из которых представляет пороговое значение.
- Для каждого запроса
queries[i] необходимо определить, сколько уникальных ячеек можно достичь, начиная с (0, 0), если разрешено:
- двигаться вверх, вниз, влево и вправо;
- заходить только в те ячейки, значение которых строго меньше
queries[i];
- Нужно вернуть массив
result, где result[i] — это общее количество очков, полученных для queries[i].
💡 Идея
Вместо того чтобы запускать поиск заново для каждого запроса, можно:
- выполнить один глобальный обход BFS, начиная с
(0, 0);
- посещать ячейки по возрастанию их значений (с помощью min-heap);
- на лету отвечать на все запросы, чьё значение не превышает текущей ячейки.
Такой метод за 1 проход отвечает сразу на все запросы.
🛠️ Детали реализации
- Сохраняем исходные индексы запросов и сортируем их по значениям.
Читать дальше →
ответить
Ссылка на задачу — 2033. Minimum Operations to Make a Uni-Value Grid.
📌 Описание задачи
Дан двумерный массив grid размером m x n, а также число x.
За одну операцию можно прибавить или
Читать дальше →
ответить
Ссылка на задачу — 3394. Check if Grid can be Cut into Sections.
📌 Описание задачи
Дано квадратное поле n×n, в котором размещены непересекающиеся прямоугольники.
Необходимо определить, можно ли сделать две горизонтальные или две вертикальные разрезки, чтобы:
- В каждой из трёх частей оказалось хотя бы по одному прямоугольнику.
- Каждый прямоугольник остался ровно в одной части.
Если такие разрезки возможны, вернуть true, иначе — false.
Пример
- Входные данные:
n = 5, rectangles = [[1,0,5,2],[0,2,2,4],[3,2,5,3],[0,4,4,5]]
- Ответ:
true
- Визуальное пояснение:
💡 Идея
Поскольку прямоугольники не пересекаются, возможные разрезки должны полностью разделять их на независимые группы.
Мы спроектируем прямоугольники на каждую ось. Если полученные отрезки отсортировать по координатам и просканировать их, можно определить количество неперекрывающихся сегментов, это позволит понять, возможно ли корректное разбиение.
Читать дальше →
ответить
Ссылка на задачу — 3108. Minimum Cost Walk in Weighted Graph.
📌 Описание задачи
- Дан неориентированный взвешенный граф с
n вершинами и m рёбрами.
- Каждое ребро представлено тройкой
[u, v, w], означающей, что существует ребро между u и v с весом w.
- Определим стоимость пути между двумя вершинами как битовое
AND всех рёбер, пройденных на пути (вершинам в таком пути разрешено повторяться).
- Для каждого запроса
[s, t] требуется найти минимальную AND-стоимость пути между s и t.
- Если пути не существует, ответ
-1.
Пример
- Входные данные:
n = 5; edges = [[0,1,7],[1,3,7],[1,2,1]]; query = [[0,3],[3,4]]
- Результаты:
[1, -1]
- Объяснение:
- Наилучший путь от
0 до 3: 0 → 1 → 2 → 1 → 3.
- Путей из
3 в 4 не существует.
- Графическая интерпретация:
💡 Идея
- Так как каждое новое ребро пути его стоимость не увеличивает, то внутри каждой компоненты связности стоимость минимального пути будет одинаковой (достаточно определить путь, проходящий через все рёбра компоненты связности).
Читать дальше →
1 ответ
Ссылка на задачу — 2401. Longest Nice Subarray.
📌 Описание задачи
Дан массив nums, состоящий из целых чисел.
Нужно найти наибольший подмассив, в котором ни одна пара чисел не имеет общих установленных битов
(т.е. их побитовое И (&) равно 0).
Пример
- 📥 Вход:
nums = [1, 3, 8, 48, 10]
- 📤 Выход:
3
- 🔍 Пояснение: Наибольший "красивый" подмассив:
[3, 8, 48], так как:
3 & 8 = 03 & 48 = 08 & 48 = 0- Никакой больший подмассив не удовлетворяет условиям.
💡 Идея
Будем решать задачу в чистом функциональном стиле, используя технику скользящего окна.
- Расширяем окно вправо, если
nums[right] не конфликтует с текущим битовым множеством.
- Сжимаем окно слева, если появляется конфликт.
- Отслеживаем текущее битовое множество (
cur_bitset), обновляя его при изменении окна.
Читать дальше →
1 ответ
Ссылка на задачу — 2115. Find All Possible Recipes from Given Supplies.
В этой задаче для эффективного решения важно не только выбрать эффективный алгоритм, но и аккуратно разложить строки по необходимым структурам данных, избежать лишних копирований и обеспечить ясную картину ownership'a за объектами.
📌 Описание задачи
- У нас есть список рецептов, каждому из которых соответствует список ингредиентов.
- Некоторые ингредиенты могут быть другими рецептами, а некоторые — изначально доступны (входят в список запасов).
- Нужно определить, какие рецепты можно приготовить, имея начальные запасы и возможность использовать приготовленные рецепты.
💡 Идея
Используем рекурсивный DFS для проверки доступности рецептов.
Чтобы избежать повторных вычислений, применяем мемоизацию (кеширование уже проверенных результатов).
Вместо хранения графа явным образом, мы используем индексирование рецептов и проходим по их списку ингредиентов.
🔍 Детали подхода
- Предобработка входных данных:
- Создаём хеш-таблицу для быстрого доступа к индексу каждого рецепта.
- Добавляем начальные запасы в кеш доступных ингредиентов.
Читать дальше →
ответить
Ссылка на задачу — 3480. Maximize Subarrays After Removing One Conflicting Pair.
📌 Описание задачи
- Дан массив чисел от
1 до n и список конфликтных пар conflicting_pairs,
где каждая пара [a, b] запрещает подотрезки[1, n] , в которых a и b встречаются совместно.
- Требуется удалить ровно одну конфликтную пару так,
чтобы получить максимальное количество подотрезков из [1, n], удовлетворяющих оставшимся ограничениям.
Пример
- Входные параметры:
n = 5, conflictingPairs = [[1,2],[2,5],[3,5]]
- Ответ:
12
- Объяснение:
Удаляем [1, 2] из массива конфликтных пар. Остаются: [[2, 5], [3, 5]].
Всего 12 подотрезков удовлетворяют условию не содержать одновременно 2 и 5 или 3 и 5.
Это отрезки: 1..1, 1..2, 1..3, 1..4, 2..2, 2..3, 2..4, 3..3, 3..4, 4..4, 4..5, 5..5
💡 Идея
- Ключевое наблюдение заключается в том, что конфликтные пары создают ограничения на диапазоны, ограничивая допустимые подотрезки.
Читать дальше →
ответить
Ссылка на задачу — 2226. Maximum Candies Allocated to K Children.
📌 Описание задачи
Дан массив candies, где candies[i] — это количество конфет в i-й куче. Нужно раздать конфеты k детям так, чтобы каждый ребёнок получил одинаковое количество конфет и все конфеты одного ребёнка были взяты из одной кучи.
Требуется найти максимальное возможное количество конфет, которое может получить каждый ребёнок.
💡 Идея
Перебор всех возможных вариантов распределения неэффективен. Вместо этого воспользуемся бинарным поиском по ответу:
- Минимальное возможное количество конфет на ребёнка —
0,
- Максимальное —
total_candies / k (тут total_candies — общее количество конфет).
Будем проверять, можно ли выдать каждому ребёнку candies_per_child конфет.
Если да, увеличиваем candies_per_child, иначе уменьшаем.
🛠 Подробности метода
- Вычисляем
total_candies — суммарное количество конфет.
- Условие быстрого выхода: если
total_candies < k, сразу возвращаем 0.
- Определяем предикат
can_share, который проверяет, можно ли распределить candies_per_child конфет на k детей.
Читать дальше →
ответить
Ссылка на задачу — 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] хранит последовательные изменения к декременту значений.
Читать дальше →
ответить
Страшилку "серой слизи" изобрел футуролог Эрик Дрекслер еще в прошлом веке. Суть идеи в том, что самовоспроизводящиеся наноботы, если упустить их из лаборатории, могут начать бесконечно копировать себя, и в результате Земля превратится в бесформенную "серую слизь", состоящую из гигантской массы нанороботов.
В 2024 году даже самые параноидальные исследователи экзистенциальных рисков относятся к "серой слизи" не слишком всерьёз. Мы не умеем делать самовоспроизводящихся наноботов и вряд ли научимся до того, как изобретём сильный искусственный интеллект который все равно нас уничтожит, с наноботами или без них.
Да?
Нет, первый реалистичный кандидат на роль "серой слизи" уже активно обсуждается, и именно в контексте "давайте сразу запретим, не дожидаясь, пока это начнут делать".
Чтобы понятно было, что это за зверь, почему его создание относительно реалистично, и чем всё это страшно, для начала напомню про понятие хиральности. Сложные органические молекулы могут быть несимметричными. В этом случае зеркальное отражение той же молекулы будет от неё отличаться. Например, для человека молекула "левой" хиральности может быть нормальным участником его метаболизма, а "правая" будет токсична.
Почему так происходит, ведь вроде бы законы химии инвариантны относительно зеркальной симметрии? Дело в том, в этом смысле почему-то несимметричны все живые существа. Аминокислоты, из которых состоят белки, в природе существуют почти исключительно в "левой" форме, а сахара, например, глюкоза, только в "правой". Хотя при замене хиральности у всех молекул, участвующих в реакции, ничего не поменялось бы, если заменить хиральность только у части из них, она может пойти совсем иначе, поэтому то, что жизнь несимметрична, важно.
Читать дальше →
3 ответа
Ссылка на задачу — 3479. Fruits Into Baskets III.
📌 Описание задачи
У нас есть два массива:
fruits[i] — количество фруктов i-го типаbaskets[j] — вместимость j-й корзины
Нужно распределить фрукты по корзинам слева направо по следующим правилам:
- Каждый тип фруктов должен быть помещён в самую левую подходящую корзину,
где вместимость соответствует (≥) количеству этих фруктов.
- Одна корзина может содержать только один тип фруктов.
- Если фрукт не удалось разместить — он остаётся неразмещённым.
Требуется вернуть количество неразмещённых фруктов.
💡 Идея
Используем дерево отрезков для эффективного поиска первой подходящей корзины.
Это позволит быстро находить и обновлять вместимость корзин за логарифмическое время, что намного быстрее наивного перебора.
🔍 Подробности подхода
- Построение дерева отрезков 🌳:
- Создаём дерево отрезков для максимумов на интервалах, инициализируюя его вместимостями корзин.
Читать дальше →
ответить
Ссылка на задачу — 3306. Count of Substrings Containing Every Vowel and K Consonants II.
📌 Условие задачи
Дана строка word и неотрицательное число k.
Необходимо подсчитать количество подстрок, в которых встречаются все гласные буквы ('a', 'e', 'i', 'o', 'u') хотя бы по одному разу и ровно k согласных.
💡 Идея
Будем использовать подход «скользящего окна», отслеживая позиции последних появлений гласных и согласных букв.
Это позволяет эффективно перемещать границы окна и быстро проверять условия задачи при изменении количества согласных и наличии всех гласных.
🛠️ Детали подхода
- Для каждой гласной буквы сохраняется её последняя позиция.
- Для согласных используется итератор, последовательно предоставляющий позиции согласных в строке.
- Если количество согласных становится больше
k, левая граница окна перемещается вперёд.
- При каждом совпадении условий (ровно
k согласных и присутствуют все гласные) подсчитывается количество допустимых подстрок.
⏳ Асимптотика
Читать дальше →
ответить
Ссылка на задачу — 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
ответить
Ссылка на задачу - 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 ответ
Очередная наша задача — 2579. Count Total Number of Colored Cells, как ни странно, красиво решается на шахматной доске ☺.
📜 Описание задачи
Дана бесконечная двумерная сетка с неокрашенными клетками. В течение n минут выполняются следующие действия:
- В первую минуту любая клетка окрашивается в синий цвет.
- В каждую следующую минуту закрашиваются все неокрашенные клетки, имеющие общую сторону с уже окрашенными.
Необходимо вычислить количество окрашенных клеток после n минут.
🧠 Идея
Если рассмотреть процесс закрашивания клеток на шахматной доске, можно увидеть, что в момент n окрашенные клетки образуют два наложенных квадрата:
- Квадрат размером
n × n
- Квадрат размером
(n-1) × (n-1)
Сумма площадей этих двух квадратов и дает общее количество окрашенных клеток.
🚀 Детали подхода
✅ Применяем формулу: Total = n²+(n−1)²
⏳ Асимптотика
- Временная сложность:
O(1)
(мгновенный расчет по формуле)
- Пространственная сложность:
O(1)
(используется только переменная n)
💻 Исходный код
impl Solution {
pub fn colored_cells(n: i32) -> i64 {
let n = n as i64;
n*n + (n-1)*(n-1)
}
}
Tags: #rust #algorithms #math
ответить
Следственное бюро Братьев Пилотов сообщает:
Во время загрузки страницы на сервере произошло нечто неладное.
Подозреваются:
- 🐧 Пингвин, слишком усердно ковырявшийся в настройках
- 🧠 Шеф, перепутавший кнопку "запустить" и "самоуничтожить"
- 🐈 Кот Мусипусик, проливший молоко на кабель
🕵️ Что произошло?
Сервер сломался, испугался или просто ушёл пить чай.
К счастью, Братья Пилоты уже ведут расследование!
🧩 Что делать?
- Вернитесь на главную — там безопаснее.
- Подождите пару минут и обновите страницу.
- Или напишите нам, если заметили что-то подозрительное: 📩 Связаться со службой
"Это вам не простая ошибка. Это — ошибка с усами!"
— Шеф (3 минуты назад, после падения сервера).
ответить
Ссылка на задачу - 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
ответить
Ссылка на задачу - 2570. Merge Two 2D Arrays by Summing Values.
📌 Описание задачи
Даны два отсортированных списка nums1 и nums2, где каждый элемент представлен в виде [id, value].
Нужно объединить их в один список, упорядоченный по id, при этом суммируя значения для совпадающих id.
💡 Идея
Так как оба списка уже отсортированы по id, можно пройтись по ним одновременно, сравнивая id и добавляя элементы в результат.
Такой метод позволяет решить задачу за O(n + m) без дополнительной сортировки.
🛠 Подробности подхода
- Используем два индекса
i и j для итерации по nums1 и nums2.
- Сравниваем текущие
id:
- Если
id1 < id2 → добавляем nums1[i] в результат, сдвигаем i.
- Если
id1 > id2 → добавляем nums2[j] в результат, сдвигаем j.
- Если
id1 == id2 → суммируем значения, добавляем результат, сдвигаем оба указателя.
- Добавляем оставшиеся элементы из
nums1 и nums2, если таковые имеются.
Читать дальше →
ответить
Ссылка на задачу — 873. Length of Longest Fibonacci Subsequence.
📌 Описание задачи
Дан монотонно возрастающий массив arr. Нужно найти длину самой длинной фибоначчиевой подпоследовательности, где каждые три последовательных элемента x, y, z удовлетворяют свойству: z = x + y
Если такой подпоследовательности нет, вернуть 0.
💡 Идея
- Мы используем динамическое программирование для отслеживания самой длинной допустимой фибоначчиевой подпоследовательности для всех нетривиальных пар
(z, y), где:
x,y,z=x+y ∈ arr и x<y<z
- Рекурентное правило ДП:
dp[z,y]=dp[y,x]+1
- Для поиска подходящих
(x, y) к текущему z применяем двунаправленный итератор.
📌 Подробности метода
- Перебираем
z = arr[k], начиная с k = 2, так как нужны минимум 3 числа.
- Будем использовать два указателя (
front и back) на arr[..k]:
front движется вперёд (x увеличивается).back движется назад (y уменьшается).
- Сравниваем
x + y и z:
Читать дальше →
1 ответ
Для задачи 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
}
}
Ссылка на задачу — 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 отслеживает следующую позицию для ненулевых чисел.
Читать дальше →
ответить
Задача 8-го дня Advent of Code — Resonant Collinearity.
🧩 Часть I. Условие задачи
В городе расставлены антенны, каждая из которых настроена на определённую частоту, обозначенную символом (a–z,A–Z,0–9). Если две антенны одной частоты расположены на прямой, и одна из них находится ровно в два раза дальше от точки, чем другая, то в этой точке возникает антинод.
Нужно найти количество уникальных позиций на карте, в которых возникает антинод. Позиции должны лежать в пределах карты. Антенны с разными частотами не создают антиноду.
💡 Идея
Для каждой частоты рассматриваем все пары антенн, стоящих на одной частоте. Каждая пара порождает ровно два симметричных антинода, расположенных по формуле:
(2*r0 - r1, 2*c0 - c1) и (2*r1 - r0, 2*c1 - c0)
Затем добавляем эти позиции в хеш-сет, если они находятся в пределах границ карты.
🧩 Часть II. Условие задачи
Читать дальше →
ответить
Ссылка на задачу — 1524. Number of Sub-arrays With Odd Sum.
📌 Описание задачи
Дан массив целых чисел arr. Необходимо найти количество подмассивов с нечётной суммой.
Так как ответ может быть очень большим, его необходимо вернуть по модулю 10⁹+7.
💡 Идея
Вместо явного перебора всех подмассивов (O(N²)), можно следить за чётностью суммы префикса.
Ключевое наблюдение:
- Если текущая сумма чётная, то количество новых подмассивов с нечётной суммой равно числу префиксов с нечётной суммой.
- Если текущая сумма нечётная, то число новых подмассивов с нечётной суммой равно количеству префиксов с чётной суммой.
🛠 Детали подхода
- Следим за чётностью префиксной суммы, храня в
prefix_parity (0 - чётная, 1 - нечётная).
- Считаем количество чётных (
even_count) и нечётных (odd_count) префиксных сумм.
- Используем
fold для итеративного обновления результата.
- Добавляем соответствующие значения к result:
- Если
prefix_parity чётный, к result прибавляем odd_count.
- Если
prefix_parity нечётный, к result прибавляем even_count.
⏳ Асимптотика
- Время:
O(N) — один проход по массиву.
- Память:
O(1) — используем только несколько переменных.
💻 Исходный код
impl Solution {
pub fn num_of_subarrays(arr: Vec<i32>) -> i32 {
const MODULO: i32 = 1_000_000_007;
let (result, _, _, _) = arr.into_iter()
.fold((0, 0, 0, 1), |(result, prefix_parity, odd_count, even_count), num| {
match(prefix_parity + num) % 2 {
0 => // Even prefix → account subarrays from odd prefixes
((result + odd_count) % MODULO, 0, odd_count, even_count + 1),
_ => // Odd prefix → account subarrays from even prefixes
((result + even_count) % MODULO, 1, odd_count + 1, even_count),
}
});
result
}
}
Tags: #rust #algorithms #prefixsum
ответить
Ссылка на задачу — 2467. Most Profitable Path in a Tree.
📌 Описание задачи
Дано неориентированное корневое дерево с n узлами (нумерованными от 0 до n-1).
- У каждого узла есть врата, открытие которых может принести прибыль или потребовать затрат (
amount[i]).
- Алиса начинает движение от корня (
0) к какому-либо листу, выбирая максимально выгодный путь.
- Боб начинает движение из указанной вершины
bob и движется к корню (0).
- Если Алиса и Боб одновременно посещают узел, они делят
стоимость/прибыль пополам.
Нужно найти максимальный чистый доход Алисы при оптимальном выборе пути.
💭 Идея
Вместо раздельного запуска BFS для поиска пути Боба и последующего прохода динамического программирования по узлам дерева, мы решим задачу одним рекурсивным DFS-проходом.
Для каждого узла будем вычислять:
alice_profit[node] – максимальный доход, который может собрать Алиса из поддерева.bob_distance[node] – расстояние на пути Боба до этой вершины.- Если Боб раньше доберётся до узла → Алиса ничего не получит.
Читать дальше →
ответить
Ссылка на задачу — 889. Construct Binary Tree from Preorder and Postorder Traversal.
📌 Описание задачи
Нам даны прямой (preorder) и обратный (postorder) обходы бинарного дерева.
Необходимо восстановить дерево по этим обходам.
Основные свойства обходов:
- Preorder (прямой обход):
[корень → левый → правый]
- Postorder (обратный обход):
[левый → правый → корень]
💡 Идея
Для построения дерева используем рекурсивный подход, основанный на двух ключевых наблюдениях:
- 1️⃣ Каждый новый узел получает значение из
preorder
→ так мы всегда сначала создаем корень поддерева.
- 2️⃣ Поддерево считается полностью построенным, когда его значение встречается в
postorder
→ это сигнал к завершению рекурсии.
🔍 Детали подхода
- Используем итераторы
Peekable<Iterator> для эффективного прохода по preorder и postorder.
- Берем значение из
preorder и создаем новый узел.
- Рекурсивно создаем левое поддерево, если
postorder пока не указывает на текущий корень.
Читать дальше →
ответить
Страница
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
