Ссылка на задачу – 1790. Check if One String Swap Can Make Strings Equal.
Описание задачи 😊
Даны две строки s1 и s2 равной длины. Необходимо определить, можно ли сделать строки равными, совершив не более одного обмена символов в одной из строк.
Обмен — это операция, когда выбираются два индекса в строке и символы на этих позициях меняются местами.
Идея 😊
Основная идея заключается в поиске позиций, на которых символы в строках различаются.
- Если различий нет, строки уже равны.
- Если различия ровно в двух позициях, то проверяем, поможет ли один обмен исправить ситуацию.
- В остальных случаях (1 или более 2 отличий) сделать строки равными одним обменом невозможно.
Детали подхода 🚀
-
Сбор различающихся индексов:
- Пройдемся по всем индексам строк и соберем в вектор те индексы, на которых символы в s1 и s2 различаются.
При этом достаточно собрать максимум 3 индекса.
-
Проверка случаев:
- Нет различий: Если вектор пуст, строки равны.
Читать дальше →
ответить
Ссылка на задачу – 3066. Minimum Operations to Exceed Threshold Value II.
📝 Описание задачи
Дан массив nums и число k. Мы можем выполнять следующую операцию, пока в массиве есть хотя бы два элемента:
- Взять два наименьших числа
x и y.
- Удалить их из массива.
- Добавить новое число
2·min(x,y) + max(x,y).
Необходимо найти количество операций, чтобы все числа в массиве стали ≥ k.
💡 Идея
Мы объединяем два наименьших числа, поэтому важно быстро находить и извлекать их.
Для этого можно использовать очередь с приоритетами (BinaryHeap), но в нашем случае можно действовать эффективнее.
🔹 Заведём две очереди (VecDeque):
orig_values — содержит исходные числа < k, отсортированные по возрастанию.new_values — хранит новые числа, появляющиеся в процессе операций, в гарантированно возрастающем порядке.
Благодаря двум упорядоченным очередям, минимальные элементы можно извлекать за O(1), а вся процедура будет работать эффективнее, чем с BinaryHeap.
Читать дальше →
ответить
Сегодня мы решаем задачу 2924. Find Champion II
🏆 Задача:
В турнире n команд представлены как вершины DAG (ориентированного ацикличного графа). Если команда a сильнее команды b, это отображается направленным ребром от a к b. Требуется найти чемпиона турнира — вершину, из которой достижимы все остальные вершины. Если чемпиона нет или их несколько, вернуть −1.
😊 Идея:
В DAG вершина с отсутствующими входящими рёбрами (in_degree = 0) является источником. Если в графе ровно один источник, он становится кандидатом в чемпионы, так как из него достижимы все остальные вершины
(Нетривиальный момент: это утверждение не верно в общем случе, но в случае DAG его несложно доказать).
Если источников больше или ни одного, чемпиона не существует.
Сложность
-
🕒 Временная сложность:
O(m): Обход рёбер для подсчёта входящих рёбер.O(n): Проход по массиву in_degree.- Итого:
O(n+m).
-
🗂️ Пространственная сложность:
O(n): Для хранения массива in_degree.
Исходный код решения
impl Solution {
pub fn find_champion(n: i32, edges: Vec<Vec<i32>>) -> i32 {
let mut in_degree = vec![0; n as usize];
// Calculate in-degrees for each node
for e in &edges {
in_degree[e[1] as usize] += 1;
}
// Identify the potential champion
let mut champion = -1;
let mut n_champions = 0;
for (node, °ree) in in_degree.iter().enumerate() {
if degree == 0 {
champion = node as i32;
n_champions += 1;
}
}
// There must be exactly one node with in-degree 0
if n_champions == 1 {
champion
} else {
-1
}
}
}
Сегодня на очереди задача 2825. Make String a Subsequence Using Cyclic Increments.
Описание задачи 📝
Даны две строки str1 и str2. Нужно определить, можно ли сделать str2 подпоследовательностью строки str1, выполнив не более одной операции циклического увеличения произвольного набора символов в str1.
Циклический сдвиг означает, что 'a' становится 'b', 'b' — 'c', ..., 'z' — 'a'.
Идея решения 💡
Задача почти идентична проверке подпоследовательности в строке. Единственное отличие — сравнение символов становится чуть сложнее из-за необходимости учитывать циклический сдвиг.
Мы выделяем проверку совпадения символов в отдельный метод, а в остальном используем стандартный алгоритм проверки подпоследовательности.
Реализация подхода 🚀
- Используем два итератора для последовательного прохода по символам строк.
- Для сравнения символов применяем отдельную функцию, учитывающую как прямое совпадение, так и циклический сдвиг.
- При совпадении текущего символа строки
str2 с символом из str1, переходим к следующему символу в str2.
- Если все символы
str2 найдены в str1 в правильном порядке, возвращаем true, иначе — false.
Сложность алгоритма 📊
Читать дальше →
ответить
Ссылка на задачу — 1980. Find Unique Binary String.
Кайфовая задачка для тех, кто не прогуливал лекции по мат. анализу ☺
📌 Описание задачи
Дан массив 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.
Визуальный пример
🦀 Исходный код
impl Solution {
pub fn find_different_binary_string(nums: Vec<String>) -> String {
let n = nums.len();
// Generate a new binary string by flipping the diagonal elements.
(0..n)
.map(|i| Self::inverse_char(nums[i].as_bytes()[i] as char))
.collect()
}
fn inverse_char(c: char) -> char {
match c {
'0' => '1',
'1' => '0',
_ => unreachable!("Unexpected character: {}", c),
}
}
}
Tags: #rust #algorithms #math
ответить
Наша новая задача – 2425. Bitwise XOR of All Pairings решается "размышлениями на салфетке" и потом очень быстро и просто программируется.
📋 Описание задачи
Даны два массива nums1 и nums2, содержащие неотрицательные числа. Для каждой пары чисел, взятых из этих массивов, вычисляется побитовый XOR. Нужно вернуть результат XOR всех таких пар.
🧠 Идея
XOR обладает полезными свойствами:
- Результат XOR числа с самим собой равен
0 (a ^ a = 0).
- XOR ассоциативен и коммутативен, что позволяет упрощать вычисления.
Только если длина одного массива нечётная, элементы второго массива оказывают влияние на результат, так как они "непарные".
В итоге вклад в результат зависит от длины второго массива для каждого массива из входной пары.
😃 Детали подхода
- Найти длины массивов
nums1 и nums2.
- Если длина
nums2 нечётная, XOR всех элементов nums1 добавляется в результат.
- Если длина
nums1 нечётная, XOR всех элементов nums2 добавляется в результат.
- Возвратить результат как итоговый XOR.
⏱️ Асимптотика
-
Время:
O(n + m), где n и m — длины массивов nums1 и nums2.- XOR всех элементов каждого массива занимает линейное время.
-
Память:
O(1), используется небольшое число дополнительных переменных.
💻 Исходный код
use std::ops::BitXor;
impl Solution {
pub fn xor_all_nums(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {
let len_nums1 = nums1.len();
let len_nums2 = nums2.len();
// Initialize result as 0
let mut result = 0;
// If nums1 has an odd number of elements, XOR all elements of nums2
if len_nums1 % 2 == 1 {
result ^= nums2.into_iter().fold(0, i32::bitxor);
}
// If nums2 has an odd number of elements, XOR all elements of nums1
if len_nums2 % 2 == 1 {
result ^= nums1.into_iter().fold(0, i32::bitxor);
}
result
}
}
Задача на сегодня 2657. Find the Prefix Common Array of Two Arrays решается в лоб, но иногда стоит рассматривать и такие простые!
📝 Описание задачи
Даны две перестановки целых чисел A и B длины n. Необходимо вычислить массив общего префикса C, где C[i] равен количеству чисел, присутствующих в обеих перестановках на индексах от 0 до i.
Пример:
- Input:
A = [1,3,2,4], B = [3,1,2,4]
- Output:
[0,2,3,4]
💡 Идея
Чтобы быстро подсчитать количество общих элементов в префиксе, мы будем использовать два булевых массива для отслеживания того, какие элементы уже встречались в каждой из перестановок. Это позволит эффективно определять, какие элементы являются общими на каждом шаге.
📋 Подробности подхода
- Создаем два булевых массива
seen_in_a и seen_in_b длины n + 1 для отслеживания элементов, уже встреченных в A и B.
- Проходим по массивам
A и B одновременно:
- Помечаем текущие элементы
A[i] и B[i] как "увиденные".
- Увеличиваем счетчик общих элементов, если текущий элемент уже был встречен в другом массиве.
- На каждом шаге добавляем текущее значение счетчика общих элементов в результат.
Читать дальше →
ответить
Последняя в уходящем году задача 983. Minimum Cost For Tickets требует от нас несложного сочетания техник динамического программирования и скользящего окна.
📜 Условие задачи
У вас есть запланированные дни поездок в течение года, указанные в массиве days. Билеты можно приобрести по следующим ценам:
- Однодневный билет за
costs[0] долларов.
- Семидневный билет (покрывает любые последовательно идущие 7 дней) за
costs[1] долларов.
- Тридцатидневный билет (покрывает любые последовательно идущие 30 дней) за
costs[2] долларов.
Необходимо определить минимальные затраты, чтобы покрыть все дни из списка days.
💡 Идея
Для минимизации затрат можно использовать динамическое программирование.
Основная идея — поочередно вычислять минимальную стоимость для каждой даты из массива days, учитывая разные виды билетов, а также использовать индексы скользящих окон для эффективного вычисления диапазонов покрытия билетов.
🛠️ Детали подхода
- Создаем массив
dp, где dp[i] хранит минимальную стоимость поездок для первых i дней.
Читать дальше →
ответить
Ссылка на задачу — 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
💡 Идея
- Ключевое наблюдение заключается в том, что конфликтные пары создают ограничения на диапазоны, ограничивая допустимые подотрезки.
Читать дальше →
ответить
Очередная наша задача — 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
ответить
Сегодня нам предстоит несложная задача - 2182. Construct String With Repeat Limit. Но технически она получилась муторной - требует от программиста очень аккуратного подхода к себе :)
Задача 📜
Дана строка s, состоящая из произвольных символов, и число repeat_limit. Необходимо построить лексикографически максимальную строку, используя символы из s, но с ограничением:
- один и тот же символ не может встречаться более
repeat_limit раз подряд.
Подход 🚀
-
Подсчёт частоты символов:
- Используем массив размера
256, чтобы подсчитать количество вхождений каждого байта (символа).
-
Жадный выбор символов:
- Обходим пространство символов (
0–255), начиная с самого большого.
- Добавляем текущий символ в результат до
repeat_limit раз или пока его количество не исчерпается.
- Если нужно "разорвать" последовательность, вставляем следующий по величине символ, уменьшая его количество.
-
Эффективный поиск следующего символа:
- Вспомогательная функция
find_last_valid_index ищет ближайший допустимый символ с ненулевой частотой, используя знание о текущем символе как ускоряющую подсказку.
Читать дальше →
2 ответа
Наступление зимы отметим разбором простой задачи 1346. Check If N and Its Double Exist.
Описание задачи 🧮
Дан массив целых чисел arr. Нужно определить, существуют ли такие индексы i и j, что:
- i≠j,
- arr[i]=2⋅arr[j].
Обзор решения 🚀
Решение использует два простых прохода по массиву:
-
Первый проход:
- Создаем хеш-таблицу, где для каждого элемента записываем количество его удвоенных значений.
-
Второй проход:
- Проверяем, существует ли текущий элемент в хеш-таблице.
- Для нуля (
0) дополнительно проверяем, встречается ли он в массиве как минимум дважды (так как 2⋅0=0).
Временная сложность ⏱️
- Первый проход:
O(n) — построение хеш-таблицы.
- Второй проход:
O(n) — проверка условий.
- Итоговая сложность:
O(n).
Пространственная сложность 📦
O(n) — память для хеш-таблицы.
Исходый код решения
use std::collections::HashMap;
impl Solution {
pub fn check_if_exist(arr: Vec<i32>) -> bool {
let mut double_map = HashMap::new();
// Populate the map with counts of doubled values
for &num in &arr {
*double_map.entry(2 * num).or_insert(0) += 1;
}
// Check for the required condition
for &num in &arr {
if num == 0 {
// Special case for 0 (2 * 0 == 0)
if *double_map.get(&0).unwrap_or(&0) > 1 {
return true;
}
} else if double_map.get(&num).is_some() {
return true;
}
}
false
}
}
Ссылка на задачу — 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 ответ
Очередная задача: 2290. Minimum Obstacle Removal to Reach Corner.
📄 Описание задачи
Дана двумерная матрица grid размером m x n, где каждая клетка может быть либо пустой (0), либо препятствием (1), которое можно удалить. Задача заключается в том, чтобы найти минимальное количество препятствий, которые нужно удалить, чтобы пройти из верхнего левого угла (0, 0) в нижний правый угол (m-1, n-1), передвигаясь только по пустым клеткам или удаляя препятствия.
🔑 Идея
Для решения задачи используем модификацию алгоритма поиска в ширину (BFS), который эффективно обрабатывает препятствия. Вместо приоритизации клеток по расстоянию, как в стандартном алгоритме Дейкстры, в 0-1 BFS (именно так эту модификацию принято называть) мы обрабатываем сначала пустые клетки, а затем клетки с препятствиями, что позволяет нам минимизировать количество удаляемых препятствий.
📋 Подробное описание подхода
-
Инициализация: Мы создаем две очереди:
front и back. Во front помещаем клетки, которые можно пройти без удаления препятствий, а в back — клетки, для которых потребуется удалить препятствие.
-
Поиск в ширину (BFS):
- Начинаем с верхнего левого угла и устанавливаем расстояние для этой клетки в
0 (т.е. препятствий еще не удалено).
- Если клетка пустая (значение
0), мы добавляем её в front. Если клетка — препятствие (значение 1), то в back.
Читать дальше →
ответить
Сегодня решаем задачу 2054. Two Best Non-Overlapping Events. Будем закреплять двоичный поиск ;)
😇 Описание задачи
Дан список событий с известными для них start_time, end_time и value. Нужно выбрать максимум два непересекающихся события с максимальной общей ценностью. События пересекаются, если одно начинается до окончания другого.
💡 Идея
Сортируем события по end_time (в убывающем порядке). Для каждого события используем двоичный поиск, чтобы найти все заканчивающиеся до его начала. Остаётся найти среди них событие с максимальной ценностью, для этого будем хранить накопленные максимальные ценности в отдельном массиве max_vals.
🛠️ Подход
-
Сортировка событий: По
end_time в порядке убывания.
-
Предобработка максимальных ценностей: Создаём массив
max_vals с накопленной максимальной ценностью событий (справа-налево).
-
Итерация и поиск:
- Для каждого события находим первое, заканчивающееся раньше его, через двоичный поиск.
- Суммируем ценности текущего события и накопленной максимальной ценности по найденному индексу, обновляя общий максимум.
Читать дальше →
ответить
Следуюшая задача для нашего обзора - 827. Making A Large Island.
Интересный способ для постобработки результатов стандартного поиска в графе.
📌 Описание Задачи
Дан n × n бинарный массив grid, где 1 — это суша, а 0 — вода.
Можно изменить ровно один 0 на 1, после чего необходимо найти размер самого большого острова.
Остров — это группа соседних единичек (соседи считаются по 4-м направлениям).
💡 Идея
1️⃣ Сначала находим и маркируем все острова, присваивая им уникальные ID.
2️⃣ Затем проверяем каждую клетку 0 и считаем, насколько большой станет остров, если заменить её на 1.
🛠️ Детали Подхода
- Маркируем острова с помощью
BFS
- Обход в ширину помечает все клетки острова уникальным
ID (начиная с 2).
- Запоминаем размер каждого острова.
Читать дальше →
ответить
Следуюшая задача для нашего разбора: 2270. Number of Ways to Split Array.
Описание задачи 📝
Дан массив целых чисел nums длины n. Требуется найти количество индексов i, где выполняются следующие условия:
- Сумма первых
i+1 элементов массива больше или равна сумме оставшихся элементов.
- Индекс
i удовлетворяет 0≤i<n−1, то есть правая часть должна содержать хотя бы один элемент.
Идея 💡
Вместо того чтобы каждый раз вычислять суммы левой и правой частей массива, мы используем баланс для их трекинга.
Изначально баланс равен −total_sum, где total_sum — сумма всех элементов массива. На каждом шаге баланс обновляется с помощью текущего элемента, а проверка условий выполняется через простое сравнение баланса с нулём.
Подробности подхода 🛠️
- Вычислить сумму всех элементов массива и сохранить её в
total_sum.
- Проитерироваться по массиву до предпоследнего элемента:
- Обновить баланс, добавляя
2×текущий элемент.
- Если баланс становится больше или равен нулю, увеличивать счётчик допустимых разбиений.
- Вернуть итоговый счётчик, который отражает количество валидных разбиений.
Читать дальше →
ответить
Ссылка на задачу – 3160. Find the Number of Distinct Colors Among the Balls.
Описание задачи 😊
- Даны шарики с уникальными метками от
0 до limit (всего limit + 1 шариков)
- И список запросов, где каждый запрос имеет вид
[x, y]
- При каждом запросе шарик с меткой
x окрашивается в цвет y.
- После каждого запроса необходимо вернуть количество различных цветов, присутствующих среди раскрашенных шариков (неокрашенные не учитываются).
Идея 💡
Основная идея заключается в использовании двух хеш-таблиц:
ball_to_color – для хранения текущего цвета каждого шарика.color_counts – для подсчёта количества шариков каждого цвета.
Это позволяет за константное (в среднем) время обновлять информацию при каждом запросе и быстро определять число уникальных цветов.
Детали подхода 🔍
- Обновление цвета шарика:
- При выполнении запроса, если шарик уже был раскрашен, получаем его старый цвет и уменьшаем счётчик в
color_counts. Если счётчик для старого цвета становится равным нулю, уменьшаем количество уникальных цветов.
Читать дальше →
4 ответа
Ссылка на задачу — 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] хранит последовательные изменения к декременту значений.
Читать дальше →
ответить
Спасибо загадочному пользователю
leetcoder, здесь опять есть какая-то жизнь. По такому случаю попробуем сюда писать в формате классического web log, вдруг получится не бросить?
Прикольная статья про силу воли и выгорание. Как всегда на lesswrong, длинновато и напоминает домашнюю философию, но основная мысль крайне простая и что-то в ней есть.
У каждого человека есть "бюджет" силы воли. Внутренний нарратор-планировщик, он же "Система 2", когда вы хотите сделать что-то неприятное, берёт кредит из этого "бюджета". Когда в вашей жизни происходит что-то приятное (приятное на базовом, бессознательном уровне), связанное с предыдущими решениями планировщика, бюджет пополняется. Если в бюджете нет средств, вы "выгорели", у вас "не хватает силы воли". Важная часть мысли состоит в том, что "приятное" определяется бессознательно, "системой 1". Например, вы очень любите мороженое; съесть мороженое и заработать $1000 могут оказаться одинаково ценными пополнениями бессознательного бюджета, хотя объективно первое примерно в тысячу раз дешевле. Это позволяет управлять "бюджетом" на сознательном уровне, решая оптимизационную задачу, и помогать другим в том же. Например, взрослые люди, как правило, недохвалены: если они делают свою работу профессионально, затратив на это немало усилий, в том числе и волевых, то это "само собой разумеется".
ответить
Очередная наша задача - 2471. Minimum Number of Operations to Sort a Binary Tree by Level
🚀 Описание задачи
Дано бинарное дерево. На каждом уровне дерева нужно отсортировать значения узлов в строго возрастающем порядке, минимизируя количество операций. За одну операцию можно поменять значения двух узлов одного уровня местами.
🧠 Идея
Для решения задачи:
1. Выполним обход дерева по уровням и соберем значения узлов для каждого уровня.
2. Для каждого уровня определим минимальное количество перестановок, необходимых для сортировки значений, используя алгоритм обнаружения циклов.
📋 Подробности подхода
-
Сбор уровней:
- Используем
std::iter::successors для выполнения обхода дерева по уровням.
- На каждом шаге собираем значения текущего уровня и формируем следующий уровень из дочерних узлов.
-
Минимальные перестановки:
- Для каждого уровня создаем массив индексов, отсортированный по значениям.
- Используя алгоритм обнаружения циклов, подсчитываем минимальное количество операций для приведения массива к упорядоченному состоянию.
Читать дальше →
ответить
Ссылка на задачу — 2467. Most Profitable Path in a Tree.
📌 Описание задачи
Дано неориентированное корневое дерево с n узлами (нумерованными от 0 до n-1).
- У каждого узла есть врата, открытие которых может принести прибыль или потребовать затрат (
amount[i]).
- Алиса начинает движение от корня (
0) к какому-либо листу, выбирая максимально выгодный путь.
- Боб начинает движение из указанной вершины
bob и движется к корню (0).
- Если Алиса и Боб одновременно посещают узел, они делят
стоимость/прибыль пополам.
Нужно найти максимальный чистый доход Алисы при оптимальном выборе пути.
💭 Идея
Вместо раздельного запуска BFS для поиска пути Боба и последующего прохода динамического программирования по узлам дерева, мы решим задачу одним рекурсивным DFS-проходом.
Для каждого узла будем вычислять:
alice_profit[node] – максимальный доход, который может собрать Алиса из поддерева.bob_distance[node] – расстояние на пути Боба до этой вершины.- Если Боб раньше доберётся до узла → Алиса ничего не получит.
Читать дальше →
ответить
Ссылка на задачу — 3306. Count of Substrings Containing Every Vowel and K Consonants II.
📌 Условие задачи
Дана строка word и неотрицательное число k.
Необходимо подсчитать количество подстрок, в которых встречаются все гласные буквы ('a', 'e', 'i', 'o', 'u') хотя бы по одному разу и ровно k согласных.
💡 Идея
Будем использовать подход «скользящего окна», отслеживая позиции последних появлений гласных и согласных букв.
Это позволяет эффективно перемещать границы окна и быстро проверять условия задачи при изменении количества согласных и наличии всех гласных.
🛠️ Детали подхода
- Для каждой гласной буквы сохраняется её последняя позиция.
- Для согласных используется итератор, последовательно предоставляющий позиции согласных в строке.
- Если количество согласных становится больше
k, левая граница окна перемещается вперёд.
- При каждом совпадении условий (ровно
k согласных и присутствуют все гласные) подсчитывается количество допустимых подстрок.
⏳ Асимптотика
Читать дальше →
ответить
Сегодня в нашей задаче 2017. Grid Game требуется рассчитать оптимальную стратегию в игре с 2 участниками. И большая часть решения опять – "размышления на салфетке".
🖍️ Условие задачи
Дано: двумерный массив grid размером 2 x n, где grid[r][c] представляет количество очков в ячейке (r, c).
- Два робота начинают игру в ячейке
(0, 0) и должны достичь ячейки (1, n-1).
- Оба робота могут двигаться только вправо или вниз.
- Первый робот проходит от начальной точки до финиша, собирая все очки на своём пути.
- Затем второй робот выполняет аналогичный маршрут, при этом очки с пройденных первым роботом ячеек обнуляются.
Цель первого робота: минимизировать максимальное количество очков, которые сможет собрать второй робот.
💡 Идея
Легко увидеть, что только две стратегии второго робота могут оказаться оптимальными:
- Право → Вниз: Сначала пройти весь верхний ряд, а затем спуститься вниз на последней колонке.
- Вниз → Право: Спуститься вниз сразу, а затем двигаться вправо вдоль нижнего ряда.
Читать дальше →
ответить
Следующая задача 407. Trapping Rain Water II даёт возможность потренировать пространственное воображение (по крайней мере на этапе выбора адекватного для её решения алгоритма).
📋 Описание задачи
Дана 3D-сетка, представляющая высоты ячеек. Необходимо вычислить объем воды, который можно удержать после дождя. Вода может заполнять только области, окруженные ячейками с большей высотой.
💡 Идея
Мы рассматриваем каждую ячейку как часть сетки, где вода может стекать только в соседние ячейки с меньшей или равной высотой. Используя структуру данных непересекающихся множеств (Disjoint-Set или Union-Find), мы группируем соединённые ячейки и отслеживаем их связь с границами, чтобы определить, какие ячейки могут удерживать воду.
🛠️ Детали подхода
-
Представление и сортировка:
- Преобразуем все ячейки в список, где каждая ячейка представлена своей высотой и координатами.
- Сортируем ячейки по высоте в порядке возрастания.
-
Структура объединения множеств:
- Создаем дискретное множество для ячеек, добавляя виртуальный узел для границ сетки.
Читать дальше →
ответить
Страница
1
2
3
4
