На этот раз наша задача выглядит заковыристо - 2982. Find Longest Special Substring That Occurs Thrice II.
📝 Описание задачи
Необходимо найти длину самой длинной "особенной" подстроки, которая встречается в строке хотя бы три раза. Если такой подстроки нет, вернуть -1.
"Особенная" подстрока — это подстрока, содержащая один и тот же символ.
😊 Идея
Отбросим сразу идею перебора всех возможных подстрок (что крайне неэффективно).
Вместо этого мы сосредоточимся на последовательных участках каждого символа.
Для каждого символа достаточно рассмотреть только длины его подряд идущих сегментов, и это позволит нам эффективно вычислить искомый результат.
🚀 Подход
- Перебираем все строчные английские буквы (
'a' до 'z').
- Для каждой буквы:
- Находим все её подряд идущие сегменты (например, для
'aaaabbaab' сегменты: [4,2], [2,1] для 'a' и 'b').
- Сортируем длины сегментов по убыванию.
- Вычисляем максимальную возможную длину "особенной" подстроки, встречающейся как минимум три раза, используя метод
get_triple_length.
Читать дальше →
4 ответа
Статья спасена из Яндекс.Кью
Сразу после февральских событий 1917 у большевиков возникла навязчивая идея увековечить память павших героев революции, воздвигнув в их честь некий грандиозный монумент, который непременно должен был «украсить» исторический центр города на Неве. Планов и решений было представлено множество: самые «безобидные» предполагали, в частности, вырубку Александровского сада перед Адмиралтейством и устроение на его месте площади «Свободы» с соответствующим памятным знаком. Также был популярен проект возведения монумента на площади перед Казанским собором; определённую поддержку имел план вырубки Таврического сада под мемориал жертвам революции; прозвучала идея убрать и Летний сад всё для тех же «памятных» нужд или перестроить Знаменскую площадь (нынешнюю площадь Восстания).
Однако самым дерзким во всех отношениях был проект по сносу Александровской колонны и организации мемориального кладбища непосредственно на Дворцовой площади. Рассматривали четыре варианта: строительство монумента у Дворцового проезда (ближе к Адмиралтейству); снос колонны, братская могила на её месте и памятник поверх захоронений посреди площади; третья идея — линия могил вдоль фасада Зимнего дворца; четвёртая — монумент во внутреннем дворе бывшей царской резиденции. Популярный журнал «Зодчий» ратовал за второй вариант (с братской могилой на месте Александровской колонны), а видный политик и публицист Владимир Дмитриевич Набоков (отец знаменитого писателя) в мемуарах «Временное правительство» писал: «Исполнительный комитет назначил день, опубликовал церемониал похорон и выбрал местом для братской могилы Дворцовую площадь, где, как известно, даже приступили к рытью могилы».
Похороны были назначены на 10 марта 1917, потому на детальное рассмотрение проектов времени отводилось немного. Однако практически все варианты, продвигаемые партийным руководством, не получили поддержки жителей Петрограда, а в среде «творческой интеллигенции» образовалась особая комиссия во главе с Максимом Горьким, которая раскритиковала все представленные проекты, один за другим спасая памятники архитектуры Северной столицы. Эта же группа, в состав которой вошли Бенуа, Петров-Водкин, Рерих, Шаляпин и другие, составляла различные документы и записки о невозможности разрушения одного объекта или перестройки другого, опираясь на необходимость соблюдения стилистического единства архитектурных ансамблей.
«Любовь» новой власти к Дворцовой площади объяснялась тремя моментами: во-первых, это самый центр столицы; во-вторых, здесь в 1905 году произошёл расстрел рабочей демонстрации царскими войсками («Кровавое воскресенье»); в-третьих, именно Зимний дворец был символом «гидры Дома Романовых», источника всех несчастий трудового народа (по мнению большевиков).
В итоге, точку в дискуссии поставил опытный архитектор Иван Александрович Фомин, который в своём авторитетном докладе разъяснил «начинающим градостроителям», что новый памятник требует особого места, в котором его не будут заслонять памятники прошлого. Более того, значимость событий, которые надлежит увековечить, требует размаха и простора, потому единственным местом в Петрограде, которое удовлетворит всем идейным и эстетическим требованиям, является Марсово поле. К тому же, бывший Царицын луг, который всегда служил то плацем для войсковых смотров и «экзерциций», то площадкой для масленичных и рождественских гуляний, не требовал сноса или перестройки чего-либо, что было несомненным плюсом. Интересно, что изначально Марсово поле, похороны на котором состоялись 5 апреля 1917 года, не пользовалось особой поддержкой в качестве места для памятника жертвам революции: видимо, сама идея предполагала непременное уничтожение чего-либо старого для постройки на его «костях» чего-то нового.
Читать дальше →
ответить
Сегодня у нас интересная задача на битовые манипуляции – 2429. Minimize XOR.
📜 Описание задачи
Дано два положительных числа num1 и num2. Нужно найти число x, такое что:
- Количество установленных битов в числе
x равно количеству установленных битов в num2.
- Результат операции
XOR между x и num1 минимален.
💡 Идея
Для минимизации XOR мы
- Стремимся сохранить как можно больше старших битов из числа num1, так как они оказывают наибольшее влияние на минимизацию результата.
- Если остаются неиспользованные биты, мы добавляем младшие биты, чтобы завершить формирование числа x с требуемым количеством установленных битов.
✨ Детали подхода
-
Подсчёт установленных битов:
- Используем метод
count_ones, чтобы подсчитать количество установленных битов в числе num2.
-
Сохранение старших битов:
- Проходим по битам
num1 с самого старшего до младшего.
- Если бит установлен, включаем его в результат и уменьшаем счётчик оставшихся битов.
Читать дальше →
1 ответ
Здесь я приведу все посты, разделенные по тематикам и отсортированные по рейтингу.
Наука
Математика
★4 Почему 1 не является простым числом? - notq
★4 Бывает ли так, что доказательство сложной математической теоремы, проверенное узким кругом учёных, имеет незамеченную ошибку? - notq
★3 В чем причина деления математиков в вопросе принятия количественной бесконечности — в логике, в вере или в самом фундаменте математики? - notq
★2 Тему «События с нулевой вероятностью» на научном форуме "dxdy" пытаются обсудить. Что мы можем добавить ? - notq
★2 Непрофессионалы в математике - notq
★2 Самое большое число в мире. Как изобрести число больше числа ГРЭМА? - notq
★2 В чем суть теоремы Эрроу? Он правда математически доказал, что демократия невозможна? - notq
★2 Что произойдет после доказательства теоремы Ферма? - notq
★2 Есть ли обобщение поля с определенными гипероперациями высших степеней, например, тетрация и т.д? - notq
★2 Какие есть приложения у теории узлов? - notq
★2 Неожиданные математические факты - notq
★1 Можно ли представить, каким было бы современное научное мировосприятие, если бы случай обернулся по-другому и не было бы Ньютона и Эйнштейна? - notq
★1 Какой минимальный набор понятий и концепций статистики стоит освоить для решения прикладных задач? - notq
Читать дальше →
4 ответа
Очередная наша задача - 2593. Find Score of an Array After Marking All Elements. Ну и так как наша цель не просто решать, а показывать имплементацию разных техник, то воспользуемся-ка мы идеей битового множества (его в стандартную библиотеку Rust еще "не подвезли", так что и операции имплементируем сами).
Задача 🧩
Дан массив положительных целых чисел nums. Ваша цель — получить максимальное значение score, выполняя следующие действия:
- Выберите наименьший немаркированный элемент массива (при равенстве — элемент с меньшим индексом).
- Добавьте значение этого элемента к
score.
- Пометьте выбранный элемент и его двух соседей (если они существуют).
- Повторяйте, пока все элементы не будут помечены.
Необходимо вернуть итоговое значение score.
Идея 💡
В данной задаче нужно эффективно следовать указанным правилам. Чтобы сделать это:
- (а) Мы отсортируем индексы массива nums по значениям, чтобы обрабатывать элементы в правильном порядке, начиная с наименьших.
- (б) Используем битовое множество (
Vec<u128>) для компактного представления состояния "помечен" для элементов массива.
Подход 🚀
Читать дальше →
ответить
Сегодня мы решаем задачу 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.
Сложность алгоритма 📊
Читать дальше →
ответить
Наша новая задача – 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
}
}
Последняя в уходящем году задача 983. Minimum Cost For Tickets требует от нас несложного сочетания техник динамического программирования и скользящего окна.
📜 Условие задачи
У вас есть запланированные дни поездок в течение года, указанные в массиве days. Билеты можно приобрести по следующим ценам:
- Однодневный билет за
costs[0] долларов.
- Семидневный билет (покрывает любые последовательно идущие 7 дней) за
costs[1] долларов.
- Тридцатидневный билет (покрывает любые последовательно идущие 30 дней) за
costs[2] долларов.
Необходимо определить минимальные затраты, чтобы покрыть все дни из списка days.
💡 Идея
Для минимизации затрат можно использовать динамическое программирование.
Основная идея — поочередно вычислять минимальную стоимость для каждой даты из массива days, учитывая разные виды билетов, а также использовать индексы скользящих окон для эффективного вычисления диапазонов покрытия билетов.
🛠️ Детали подхода
- Создаем массив
dp, где dp[i] хранит минимальную стоимость поездок для первых i дней.
Читать дальше →
ответить
Ответ спасен из Яндекс.Кью
Это, внезапно, одна из лучших научно-популярных книжек из тех, что я читал за последние годы. Тема, казалось бы, узкая (о некотором античном механизме, найденном в останках кораблекрушения, и попытках разгадать, для чего он служил и как был устроен), но автор настолько фантастически и разносторонне образован, и настолько системно мыслит, что за пару абзацев мимоходом меняет читателю представление о целых масштабных областях.
Чтобы не быть голословным: все мы со школы помним про "бронзовый век", да? Не знаю, как вы, а я с тех пор его так и представлял как-то очень упрощенно. Были люди в шкурах и всё такое, потом научились обработке металлов, люди с бронзовыми мечами легко выносили людей с каменными или даже с медными топорами, ну и понеслась. Так вот, как известно, бронза -- сплав меди с оловом. То ли первая, то ли одна из первых цивилизаций бронзового века, Эгейская (3200 до н.э.), выплавляла бронзу на Кипре, где были удобные для разработки месторождения меди, а олово для этого доставлялось, тадам, из Англии. Представьте себе размеры и сложность необходимых для этого торговых путей и общества в целом. Вот вам и пещерные люди.
Отличие хороших книжек от интернета, если кому-то нужно его доказывать, иллюстрируется тем фактом, что из википедии, например, понять это невозможно, даже если читать именно статью "Бронзовый век", просто не поймешь, на что смотреть.
Или вот другой факт: оказывается, императорская Япония вполне себе разрабатывала ядерное оружие и в 1945 году даже приступила к строительству установки по обогащению урана, чуть-чуть не успели, в общем. Как так получается, что я об этом впервые читаю в книжке, вообще совершенно не об этом написанной?!
Ещё очень радует, что автор, когда ему что-то непонятно, в отличие от большинства своих коллег, не стесняется так и писать: непонятно. После распространенного в научпопе сциентистского высокомерия это освежает. Почему античная цивилизация, дойдя до паровой машины и точных механических калькуляторов, вместо вступления в индустриальную эру решила погибнуть, непонятно. Имеющиеся разъяснения выглядят как средневековое "чеснок исцеляет благодаря своей исцелительной силе", исчерпывающего и убедительного объяснения нет.
На всякий случай, передам предупреждение от старших товарищей, увлекающихся историей техники: говорят, что автор местами увлекается сенсационными интерпретациями в ущерб более банальным, так что самые удивляющие фрагменты лучше перепроверять по независимым источникам. Тем не менее, книжку горячо рекомендую, давайте весь тираж срочно скупим, чтобы такое продолжали переводить и издавать.
ответить
Спасибо загадочному пользователю
leetcoder, здесь опять есть какая-то жизнь. По такому случаю попробуем сюда писать в формате классического web log, вдруг получится не бросить?
Прикольная статья про силу воли и выгорание. Как всегда на lesswrong, длинновато и напоминает домашнюю философию, но основная мысль крайне простая и что-то в ней есть.
У каждого человека есть "бюджет" силы воли. Внутренний нарратор-планировщик, он же "Система 2", когда вы хотите сделать что-то неприятное, берёт кредит из этого "бюджета". Когда в вашей жизни происходит что-то приятное (приятное на базовом, бессознательном уровне), связанное с предыдущими решениями планировщика, бюджет пополняется. Если в бюджете нет средств, вы "выгорели", у вас "не хватает силы воли". Важная часть мысли состоит в том, что "приятное" определяется бессознательно, "системой 1". Например, вы очень любите мороженое; съесть мороженое и заработать $1000 могут оказаться одинаково ценными пополнениями бессознательного бюджета, хотя объективно первое примерно в тысячу раз дешевле. Это позволяет управлять "бюджетом" на сознательном уровне, решая оптимизационную задачу, и помогать другим в том же. Например, взрослые люди, как правило, недохвалены: если они делают свою работу профессионально, затратив на это немало усилий, в том числе и волевых, то это "само собой разумеется".
ответить
Следующая задача 407. Trapping Rain Water II даёт возможность потренировать пространственное воображение (по крайней мере на этапе выбора адекватного для её решения алгоритма).
📋 Описание задачи
Дана 3D-сетка, представляющая высоты ячеек. Необходимо вычислить объем воды, который можно удержать после дождя. Вода может заполнять только области, окруженные ячейками с большей высотой.
💡 Идея
Мы рассматриваем каждую ячейку как часть сетки, где вода может стекать только в соседние ячейки с меньшей или равной высотой. Используя структуру данных непересекающихся множеств (Disjoint-Set или Union-Find), мы группируем соединённые ячейки и отслеживаем их связь с границами, чтобы определить, какие ячейки могут удерживать воду.
🛠️ Детали подхода
-
Представление и сортировка:
- Преобразуем все ячейки в список, где каждая ячейка представлена своей высотой и координатами.
- Сортируем ячейки по высоте в порядке возрастания.
-
Структура объединения множеств:
- Создаем дискретное множество для ячеек, добавляя виртуальный узел для границ сетки.
Читать дальше →
ответить
Сегодня мы рассмотрим решение задачи 2116. Check if a Parentheses String Can Be Valid.
🧩 Описание задачи
Дана строка s, состоящая только из символов '(' и ')', и строка locked длины n, состоящая из символов '0' и '1'. Каждая позиция в locked указывает, можно ли изменить символ в s на этой позиции:
- Если
locked[i] == '1', символ s[i] нельзя менять.
- Если
locked[i] == '0', символ s[i] можно изменить на '(' или ')'.
Нужно определить, можно ли сделать строку s корректной скобочной записью.
💡 Идея
Решение основывается на двух проходах по строке:
- Прямой проход: Проверяем баланс открывающих и закрывающих скобок слева направо, учитывая символы, которые можно менять.
- Обратный проход: Инвертируем строку (меняем '(' на ')' и наоборот) и проверяем баланс справа налево.
При каждом проходе используем два счётчика:
- balance для отслеживания текущего баланса скобок.
- free для отслеживания количества символов, которые можно изменить.
Если на любом этапе баланс становится отрицательным, и его нельзя компенсировать изменением свободных символов, строка не может быть сделана валидной.
Читать дальше →
1 ответ
Наверняка у вас были книжки о математике/программированию, которыми вы зачитывались в подростковом возрасте?
Из тех, которые запомнились мне:
"Математические новеллы", Гарднера и "Алиса в стране смекалки" Рэймонда Смаллиана - обе могу порекомендовать как взрослым, так и детям. #books #math
4 ответа
Сегодня у нас еще одна задача на аккуратное манипулирование индексами 2337. Move Pieces to Obtain a String.
Описание задачи
Даны две строки start и target длины n, содержащие символы 'L', 'R' и '_'.
- Символ
'L' может двигаться только влево, если есть пустое место ('_') слева.
- Символ
'R' может двигаться только вправо, если есть пустое место ('_') справа.
- Необходимо определить, можно ли преобразовать строку
start в строку target с соблюдением этих правил.
Идея 🧠
Задача сводится к тому, чтобы проверить, совпадают ли позиции и направления символов 'L' и 'R' в двух строках с учётом их ограничений на движение. Мы используем итерацию по строкам одновременно, отслеживая доступные символы 'L' и 'R' через счётчики.
Подход 🛠️
- Используем метод
as_bytes(), чтобы быстро перебрать символы в виде байтов.
- Одновременно проходим по обеим строкам:
- Если видим
'L' в target, увеличиваем счётчик доступных 'L'.
- Если видим
'L' в start, проверяем, есть ли доступный 'L', и уменьшаем счётчик.
Читать дальше →
ответить
Итак, я нагло спарсил notq(спасибо @finder за отсутствие антифрода) и решил посмотреть топовые статьи по голосам пользователей. Текущий топ выглядит так:
| rating | link_title |
|---------:|:----------------------------------------------------------------------------------------|
| 45 | Что здесь происходит - notq |
| 31 | Совет молодому руководителю в IT - notq |
| 16 | Планы на будущее - notq |
| 16 | Космическая интуиция - notq |
| 13 | Печенье "Юбилейное" - notq |
| 11 | Глубокая мысль - notq |
| 10 | Как рассчитывать цену производных финансовых инструментов - notq |
| 9 | Performing productivity at Google: It’s All Bullshit - notq |
| 9 | Кардиологи и китайские грабители - notq |
| 8 | Интервью с директором советского продуктового магазина - notq |
Наиболее рейтинговым автором стал(кто бы сомневался) @robot-q-reposter. За ним идут @finder, @notq и @1e9y.
Читать дальше →
2 ответа
Задача на выходные - 2097. Valid Arrangement of Pairs
Описание задачи 📜
Нужно переставить заданные пары [starti,endi] так, чтобы получилось корректное расположение,
где для каждой пары i: endi−1=starti. Гарантируется, что такое расположение существует.
Обзор решения 🛠
Для решения задачи используется алгоритм Хирхольцера, который позволяет построить Эйлеров путь (или цикл) в ориентированном графе. Основная идея — удалять рёбра во время обхода, что упрощает структуру данных и предотвращает повторное использование рёбер.
Ключевые шаги 🚀
-
Построение графа:
- Граф представляется в виде списка смежности (
HashMap<i32, Vec<i32>>), где каждая вершина хранит список своих исходящих рёбер.
- Параллельно вычисляются разницы степеней вершин (входящих и исходящих рёбер) для определения начальной вершины пути.
-
Поиск начальной вершины:
- Начальная вершина — это вершина с положительным балансом исходящих рёбер. Если таких нет, берётся любая вершина из входных данных.
-
Итеративный DFS с удалением рёбер:
- Вместо стандартного рекурсивного DFS используется итеративный подход с явным стеком. Это повышает эффективность памяти и скорость.
- При посещении вершины рёбра удаляются из списка смежности, что гарантирует, что каждое ребро используется ровно один раз.
Читать дальше →
ответить
Год назад, когда Карпатый присоединился к OpenAI, я удивлялся, как они умудряются нанимать таких людей на такие роли. Вроде как он у них занимался тем же, чем у нас условные миддлы занимаются. Если кто вдруг не знает, до этого он был директором по AI в Тесла, и вообще очень известный в индустрии человек со своей страничкой в Википедии, десятками тысяч звезд на Гитхабе и т.п.
Через год они себя переплюнули, уволив его как не справляющегося. В твиттере этого в явном виде не написано, но уход в никуда, отсутствие рассказов о том, что классное он успел сделать, и обще-обтекаемые фразы, что все всеми довольны и никаких претензий нет вызывают четкое узнавание ситуации.
Так вот вопрос, как они умудрились собрать команду, в которой Андрей выглядит "ниже ожиданий", и которая силами 200-300 человек регулярно унижает остальной мир, включая фаанги? У меня есть единственное предположение - они тупо платят втрое больше других, но при этом хорошо знают, кому, и потому перекупают у остальных действительно ключевых людей. Но даже это весьма непросто устроить.
7 ответов
Задача: 2872. Maximum Number of K-Divisible Components
Описание задачи 📋
Дано неориентированное дерево с n узлами, пронумерованными от 0 до n−1. Также даны:
- массив рёбер edges, где каждое ребро связывает два узла,
- массив значений values, где значение values[i] связано с узлом i,
- число k.
- гарантируется, что сумма всех значений values кратна k
Необходимо найти максимальное количество компонентов, на которые можно разделить дерево, удаляя рёбра, чтобы сумма значений в каждом компоненте делилась на k.
Идея 💡
Будем разбивать дерево на компоненты рекурсивно (DFS), начиная с произвольного узла.
Несложно показать, что родительская вершина должна быть в одной компененте со всеми дочерними, для которых сумма значений в соответствующем поддереве не делится на k.
Детали подхода 🚀
-
Построение графа:
- Представляем дерево в виде списка смежности для удобного обхода.
-
Обход дерева:
Читать дальше →
ответить
Сегодня нам предстоит решить задачу 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.
Читать дальше →
ответить
Задача на сегодня 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 с двумя очередями, где приоритет отдается движениям без изменения направления.
🛠️ Детали подхода
- Две очереди:
Читать дальше →
ответить
Сегодня нас опять радует задачка на методы динамического программирования - 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
}
}
Задача на сегодня 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] как "увиденные".
- Увеличиваем счетчик общих элементов, если текущий элемент уже был встречен в другом массиве.
- На каждом шаге добавляем текущее значение счетчика общих элементов в результат.
Читать дальше →
ответить
Сегодня нам предстоит несложная задача - 2182. Construct String With Repeat Limit. Но технически она получилась муторной - требует от программиста очень аккуратного подхода к себе :)
Задача 📜
Дана строка s, состоящая из произвольных символов, и число repeat_limit. Необходимо построить лексикографически максимальную строку, используя символы из s, но с ограничением:
- один и тот же символ не может встречаться более
repeat_limit раз подряд.
Подход 🚀
-
Подсчёт частоты символов:
- Используем массив размера
256, чтобы подсчитать количество вхождений каждого байта (символа).
-
Жадный выбор символов:
- Обходим пространство символов (
0–255), начиная с самого большого.
- Добавляем текущий символ в результат до
repeat_limit раз или пока его количество не исчерпается.
- Если нужно "разорвать" последовательность, вставляем следующий по величине символ, уменьшая его количество.
-
Эффективный поиск следующего символа:
- Вспомогательная функция
find_last_valid_index ищет ближайший допустимый символ с ненулевой частотой, используя знание о текущем символе как ускоряющую подсказку.
Читать дальше →
2 ответа
Страница
1
2
3
4
