Дан массив целых чисел 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) — используем только несколько переменных.
💻 Исходный код
implSolution{pubfnnum_of_subarrays(arr: Vec<i32>) -> i32{constMODULO: 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}}
Дано неориентированное корневое дерево с n узлами (нумерованными от 0 до n-1).
У каждого узла есть врата, открытие которых может принести прибыль или потребовать затрат (amount[i]).
Алиса начинает движение от корня (0) к какому-либо листу, выбирая максимально выгодный путь.
Боб начинает движение из указанной вершины bob и движется к корню (0).
Если Алиса и Боб одновременно посещают узел, они делят стоимость/прибыль пополам.
Нужно найти максимальный чистый доход Алисы при оптимальном выборе пути.
💭 Идея
Вместо раздельного запуска BFS для поиска пути Боба и последующего прохода динамического программирования по узлам дерева, мы решим задачу одним рекурсивным DFS-проходом.
Для каждого узла будем вычислять:
alice_profit[node] – максимальный доход, который может собрать Алиса из поддерева.
bob_distance[node] – расстояние на пути Боба до этой вершины.
Если Боб раньше доберётся до узла → Алиса ничего не получит.
Дан массив nums, содержащий n различных бинарных строк длины n.
Необходимо найти любую бинарную строку длины n, которая не содержится в nums.
💡 Идея
Используем диагонализацию Кантора:
Если пройти по диагонали массива строк и инвертировать каждый символ ('0' → '1', '1' → '0'), то полученная строка гарантированно отличается от каждой строки в nums хотя бы в одном символе.
Это означает, что такая строка не может присутствовать в nums.
🔍 Подробности подхода
Итерируемся по индексам 0..n.
Берем i-й символ i-й строки.
Инвертируем его ('0' → '1', '1' → '0').
Собираем новые символы в строку и возвращаем её.
📊 Асимптотика
Временная сложность:O(n) — один проход по n элементам.
Дополнительная память:O(n) — единственное, что создаётся, это строка длины n.
Визуальный пример
🦀 Исходный код
implSolution{pubfnfind_different_binary_string(nums: Vec<String>) -> String{letn=nums.len();// Generate a new binary string by flipping the diagonal elements.(0..n).map(|i|Self::inverse_char(nums[i].as_bytes()[i]aschar)).collect()}fninverse_char(c: char) -> char{matchc{'0'=>'1','1'=>'0',_=>unreachable!("Unexpected character: {}",c),}}}
"Счастливая строка" – это строка длины n, состоящая только из символов ['a', 'b', 'c'], в которой нет двух одинаковых подряд идущих символов.
Нужно найти k-ю счастливую строку в лексикографическом порядке, либо вернуть "", если таких строк меньше k.
💡 Идея
Рассмотрим связь счастливых строк с двоичными строками.
Каждая счастливая строка:
Начинается с одного из трёх символов ('a', 'b', 'c') → 3 варианта.
Остальные (n-1) символов формируются по аналогии с двоичной строкой, где у каждого символа есть ровно два возможных варианта → ×2 на каждую позицию.
Таким образом, двоичное представление k-1 почти полностью определяет структуру требуемой строки (без первого символа).
Мы можем использовать биты 0 и 1 из этого двоичного представления, чтобы выбирать между двумя допустимыми символами при итеративной генерации каждого следующего символа конкретной счастливой строки. 🚀
🔍 Детали подхода
Определяем количество возможных строк с фиксированным первым символом:
Дан строковый шаблон pattern, состоящий из символов I и D.
Необходимо построить лексикографически наименьшее число длины n+1, используя цифры от 1 до 9 без повторений, которое соответствует следующим требованиям:
'I' (увеличение) на позиции i → требует, чтобы num[i] < num[i+1].
'D' (уменьшение) на позиции i → требует, чтобы num[i] > num[i+1].
💡 Идея
Рассмотрим шаблон как ориентированный граф, где каждая позиция (i) — это вершина.
Если pattern[i] == 'I', создаём ребро i → i+1.
Если pattern[i] == 'D', создаём ребро i+1 → i.
После построения графа можно выполнить топологическую сортировку, начиная с вершин с нулевой степенью захода.
Чтобы гарантировать лексикографически наименьший порядок, обрабатываем вершины через приоритетную очередь (Min-Heap).
У нас есть набор плиток, на каждой из которых напечатана одна буква, представленный в виде строки.
Необходимо подсчитать количество различных возможных непустых последовательностей букв, которые можно составить, используя плитки.
💡 Идея решения
Будем использовать бэктрекинг.
Чтобы избежать проверки на уникальность через HashSet, сначала сортируем плитки, а затем группируем одинаковые плитки в сегменты.
Далее, с помощью рекурсии, перебираем все возможные последовательности, гарантируя, что одинаковые плитки не будут использоваться более одного раза в одном наборе последовательностей.
🧑💻 Подробности подхода
Сортировка плиток:
Плитки сортируются для того, чтобы одинаковые плитки оказались рядом. Это позволяет нам эффективно группировать их в сегменты.
Группировка плиток:
Создаем массив сегментов, где каждый элемент представляет собой количество одинаковых плиток.
Например, для строки "AAB" сегменты будут равны [2, 1] (2 плитки "A" и 1 плитка "B").
Бэктрекинг — для каждого сегмента мы:
пытаемся использовать плитку (уменьшаем количество плиток в этом сегменте);
Дано число n. Необходимо построить последовательность, удовлетворяющую следующим условиям:
Число 1 встречается ровно один раз.
Каждое число i от 2 до n встречается ровно дважды.
Для каждого числа i > 1, два его вхождения в последовательность находятся на расстоянии ровно i.
Среди всех возможных последовательностей требуется выбрать лексикографически наибольшую.
💡 Идея
Бэктрекинг — хороший способ решения данной задачи.
Чтобы получить лексикографически наибольшую последовательность, мы должны размещать сначала наибольшие числа.
🔄 Подробности метода
Рекурсивно заполняем последовательность, начиная с первого свободного индекса.
Используем массив used, который отслеживает, какие числа уже размещены.
Пропускаем занятые позиции.
Проверяем возможность размещения числа заранее, прежде чем выполнять рекурсию.
Необходимо создать структуру ProductOfNumbers, которая:
Позволяет добавлять числа в поток (add(num)).
Вычисляет произведение последних k чисел (get_product(k)).
Гарантируется, что ответы не приведут к переполнению 32-битного целого.
💡 Идея
Будем использовать префиксные произведения.
Это позволит получать результат за O(1), выполняя деление последних значений.
Но так как деление на 0 запрещено, придётся аккуратно отслеживать этот случай и сбрасывать произведения при появлении нуля.
⚙️ Подход
Используем Vec<i64> для хранения префиксных произведений.
Добавление числа:
Если num == 0, очищаем хранилище, так как любое произведение после нуля будет равно нулю.
Иначе умножаем предыдущее произведение на текущее число и сохраняем результат.
Вычисление get_product(k):
Если k больше количества сохранённых чисел, возвращаем 0.
Иначе делим последнее префиксное произведение на значение k шагов назад.
Дан массив nums и число k. Мы можем выполнять следующую операцию, пока в массиве есть хотя бы два элемента:
Взять два наименьших числа x и y.
Удалить их из массива.
Добавить новое число 2·min(x,y) + max(x,y).
Необходимо найти количество операций, чтобы все числа в массиве стали ≥ k.
💡 Идея
Мы объединяем два наименьших числа, поэтому важно быстро находить и извлекать их.
Для этого можно использовать очередь с приоритетами (BinaryHeap), но в нашем случае можно действовать эффективнее.
🔹 Заведём две очереди (VecDeque):
orig_values — содержит исходные числа < k, отсортированные по возрастанию.
new_values — хранит новые числа, появляющиеся в процессе операций, в гарантированно возрастающем порядке.
Благодаря двум упорядоченным очередям, минимальные элементы можно извлекать за O(1), а вся процедура будет работать эффективнее, чем с BinaryHeap.
Дан массив положительных чисел nums. Необходимо найти максимальную сумму двух различных элементов, у которых одинаковая сумма цифр. Если таких пар нет — вернуть -1.
💡 Идея решения
Вместо хранения всех чисел с одинаковой суммой цифр, достаточно хранить только максимальное из них.
Таким образом, при встрече нового числа с такой же суммой цифр можно сразу проверять, образует ли оно лучшую пару.
🔍 Подход к решению
Используем массивmax_per_dsum, в котором храним наибольшее число для каждой суммы цифр.
Максимальная сумма цифр для i32 — 82, но мы ограничиваем массив сотней для простоты.
Обрабатываем nums за один проход, применяя функциональный стиль с filter_map:
вычисляем сумму цифр d_sum для числа n;
если уже есть число с таким d_sum, определяем текущую сумму пары и сохраняем обновлённое максимальное число;
если это первое число с данным d_sum, просто сохраняем его в max_per_dsum;
filter_map отбрасывает неопределённые суммы пар (None), оставляя только валидные.
Даны шарики с уникальными метками от 0 до limit (всего limit + 1 шариков)
И список запросов, где каждый запрос имеет вид [x, y]
При каждом запросе шарик с меткой x окрашивается в цвет y.
После каждого запроса необходимо вернуть количество различных цветов, присутствующих среди раскрашенных шариков (неокрашенные не учитываются).
Идея 💡
Основная идея заключается в использовании двух хеш-таблиц:
ball_to_color – для хранения текущего цвета каждого шарика.
color_counts – для подсчёта количества шариков каждого цвета.
Это позволяет за константное (в среднем) время обновлять информацию при каждом запросе и быстро определять число уникальных цветов.
Детали подхода 🔍
Обновление цвета шарика:
При выполнении запроса, если шарик уже был раскрашен, получаем его старый цвет и уменьшаем счётчик в color_counts. Если счётчик для старого цвета становится равным нулю, уменьшаем количество уникальных цветов.
Переставляя слагаемые, получаем: nums[j]−j = nums[i]−i
То есть если два индекса имеют одинаковое значение позиционной разности(nums[k] - k), – они образуют хорошую пару!
Используем метод chunk_by для подсчёта частот одинаковых значений.
Для каждой такой частоты count, вычисляем количество хороших пар: count×(count−1)/2
Всего существует n × (n - 1) / 2 пар, из них вычитаем хорошие пары и получаем ответ.
⏳ Асимптотика
Время:O(n·log n), так как сортировка доминирует над остальными операциями.
Память:O(n), так как храним pos_diff.
🔥 Хотя сортировка для подсчёта частот медленнее хеш-таблиц в асимптотике, на практике она быстрее из-за низкой константы!
📝 Исходный код
implSolution{pubfncount_bad_pairs(nums: Vec<i32>) -> i64{letn=nums.len()asi64;// Compute adjusted values (nums[i] - i) and sortletmutpos_diff: Vec<_>=nums.into_iter().enumerate().map(|(idx,num)|num-idxasi32).collect();pos_diff.sort_unstable();// Count good pairs using `chunk_by`letgood_pairs: i64=pos_diff.chunk_by(|a,b|a==b).map(|chunk|(chunk.len()asi64*(chunk.len()asi64-1))/2).sum();// Total pairs - good pairs = bad pairslettotal_pairs=n*(n-1)/2;total_pairs-good_pairs}}
Дан массив 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).
Даны две строки s1 и s2 равной длины. Необходимо определить, можно ли сделать строки равными, совершив не более одного обмена символов в одной из строк. Обмен — это операция, когда выбираются два индекса в строке и символы на этих позициях меняются местами.
Идея 😊
Основная идея заключается в поиске позиций, на которых символы в строках различаются.
Если различий нет, строки уже равны.
Если различия ровно в двух позициях, то проверяем, поможет ли один обмен исправить ситуацию.
В остальных случаях (1 или более 2 отличий) сделать строки равными одним обменом невозможно.
Детали подхода 🚀
Сбор различающихся индексов:
Пройдемся по всем индексам строк и соберем в вектор те индексы, на которых символы в s1 и s2 различаются.
При этом достаточно собрать максимум 3 индекса.
Дан массив целых чисел nums. Необходимо найти длину самой длинной последовательности, которая является либо строго возрастающей, либо строго убывающей.
🤔 Идея
Разбить массив на группы (чанки) по непрерывной монотонности (либо возрастающей, либо убывающей).
Для каждой группы вычислить её длину, а затем выбрать максимальное значение среди всех групп.
🚀 Детали подхода
Разбиение на чанки:
Используем метод chunk_by для разбиения массива:
Для строго возрастающей последовательности используем сравнение a < b.
Для строго убывающей последовательности используем сравнение a > b.
Вычисление максимальной длины:
Для каждого набора чанков вычисляем длину каждой группы, выбираем максимальную длину для возрастающих и убывающих групп.
Результат:
Возвращаем максимум между максимальной длиной возрастающей и максимальной длиной убывающей последовательности.
⏱ Асимптотика
Время:O(n) — каждый элемент обрабатывается один раз при разбиении на чанки.
Память:O(1) — используется дополнительная память только для итераторов, не зависящая от размера входного массива.
📜 Исходный код
implSolution{pubfnlongest_monotonic_subarray(nums: Vec<i32>) -> i32{// Group strictly increasing segments using chunk_byletmax_increasing_len=nums.chunk_by(|a,b|a<b).map(|c|c.len()).max().unwrap_or(0);// Group strictly decreasing segments using chunk_byletmax_decreasing_len=nums.chunk_by(|a,b|a>b).map(|c|c.len()).max().unwrap_or(0);max_increasing_len.max(max_decreasing_len)asi32}}
Следуюшая задача для нашего обзора - 827. Making A Large Island.
Интересный способ для постобработки результатов стандартного поиска в графе.
📌 Описание Задачи
Дан n × n бинарный массив grid, где 1 — это суша, а 0 — вода.
Можно изменить ровно один 0 на 1, после чего необходимо найти размер самого большого острова. Остров — это группа соседних единичек (соседи считаются по 4-м направлениям).
💡 Идея
1️⃣ Сначала находим и маркируем все острова, присваивая им уникальные ID.
2️⃣ Затем проверяем каждую клетку 0 и считаем, насколько большой станет остров, если заменить её на 1.
🛠️ Детали Подхода
Маркируем острова с помощью BFS
Обход в ширину помечает все клетки острова уникальным ID (начиная с 2).
Дан неориентированный граф с n вершинами, возможно несвязный. Требуется разбить вершины на m групп, соблюдая условия:
✔ Каждая вершина принадлежит ровно одной группе.
✔ Если вершины соединены ребром [a, b], то они должны находиться в смежных группах (|group[a] - group[b]| = 1).
✔ Найти максимальное количество таких групп m.
✔ Вернуть -1, если разбиение невозможно.
💡 Идея
Граф можно корректно разбить на группы ↔ он двудольный.
Максимальное количество групп связано с максимальной глубиной BFS в каждой компоненте.
Мы проверяем BFS из каждой вершины, чтобы найти наилучший возможный корень для каждой компоненты.
🔍 Детали подхода
Строим граф в виде списка смежности.
Запускаем BFS из каждой вершины (а не только из одной в компоненте) для:
Проверки двудольности (по уровням BFS).
Поиска максимальной глубины BFS (max_level).
Определения уникального идентификатора компоненты (min_index).
Любимые факты об английском. Просто так, может, вы тоже порадуетесь. Ничего сверхъестественного, но удивляет, когда задумаешься.
"Ученик" ("школьник") по-английски "зрачок". То есть, "я весь внимание", буквально.
По-английски в радуге тоже семь цветов. Но это другие семь цветов. Синий и голубой ведь один и тот же цвет, а вот фиолетовые бывают разные.
"Государство" по-английски звучит примерно как "состояние дел". "Failed state" это не когда из крана перестает течь вода, а террористы мародерят в пригородах столицы, это просто констатация того, что некое "состояние дел" перестало самовоспроизводиться. "State", впрочем, даже в узком значении "состояние дел, связанное с управлением людьми на определенном куске земного шара" бывает не только таким, к которому мы привыкли (то, скорее, "nation state").
Слова "gore" в русском языке нет, хотя понятие, казалось бы, абсолютно базовое.
Слово "убийца" можно перевести на английский по меньшей мере 8 разными способами (slayer, killer, murderer, assassin, hitman, triggerman, manslayer, cutthroat). Наверное, есть больше. По-русски есть ещё душегуб, головорез (хотя он, скорее, thug, чем cutthroat) и позаимствованный "киллер". Вроде бы, всё?
Слова "зависть" и "ревность" почти взаимозаменяемы и носители языка считают нужным многословно пояснять разницу между ними, причем "зависть" (по крайней мере, в подобных заметках) считается более позитивным чувством. С другой стороны, "ревность" это вообще-то два разных слова, jealousy и insecurity, в зависимости от того, обладает ли испытывающий это чувство предметом вожделения в настоящий момент. "Insecurity", впрочем, это далеко не только "ревность". Сложна.
"Интеллигенция" по-английски "intelligentsia". В XXI веке употребляется далеко не только (и уже, по-моему, не столько) в значении "...в СССР", хотя раньше слово с таким значением почему-то никому не требовалось.
У нас есть numCourses курсов, пронумерованных от 0 до numCourses - 1.
Даны:
Массив prerequisites, где prerequisites[i] = [a, b] указывает, что курс a необходимо пройти перед курсом b.
Массив запросов queries, где queries[j] = [u, v] спрашивает: является ли курс u предшественником курса v.
Нужно вернуть массив булевых значений, где для каждого запроса ответ — true, если курс u является прямым или косвенным предшественником курса v; или false, если нет.
💡 Идея
Представим зависимости курсов в виде графа, где вершины — это курсы, а ребра указывают на зависимости между ними. Наша цель — определить, существует ли путь между двумя вершинами графа. Для этого можно использовать алгоритм Флойда-Уоршелла, чтобы вычислить транзитивное замыкание графа.
🛠️ Подробности подхода
Инициализация матрицы зависимостей: Создаем булевую матрицу n x n, где dep_matrix[i][j] обозначает, что курс i является предшественником курса j.
Заполнение прямых зависимостей: На основе массива prerequisites отмечаем прямые зависимости в матрице.
leetcoder
finder