Итак, думаю этот hot take будет прям hot.
Тезис: современная этика в науке и медицине очень сильно ограничивает прогресс. Смягчение некоторых этических норм позволит очень сильно продвинуть прогресс вперед. Предлагаемые изменения в этике:
- все что делается с информированного добровольного согласия дееспособного человека - допустимо
- любые научные эксперименты на животных допустимы
- запреты на клонирование и генетические модификации человека отменяются
Примеры и аргументы почему да:
- медицина: даже на смертельно больном пациенте провести авантюрное лечение по принципу "ну 1% что поможет, 99% что умрет - так ведь и так умрет" не получится просто взять и применить. Даже при его информированном согласии.
- наука: опыты на животных - боль. Нужно 50 одобрений; хрен вам(в смысле мыши) а не шимпанзе, комитет по этике против; на человеческих эмбрионах что-то делать это вообще бюрократический ад. И да, мыши от человека сильно дальше чем шимпанзе - талидомид например для них не тератоген как для нас, а вот для нас и шимпанзе да. В итоге, воспроизводимость исследований на людях страдает, мы проводим 10 тестов на мышах, а на 11ом на шимпанзе понимаем что занимались изначально обреченной идеей.
- Клонирование человека + генетические модификации - путь к истребелению множества наследственных заболеваний. Как вам мир в котором "синдром дауна" и "спинально-мышечная атрофия" - это какие-то понятия из прошлого?
18 ответов
а где сейчас не зашквар и работа мечты? просто понять что на другой стороне от маккинзи
from #yachan
Контекст: утверждается, что работать в местах а-ля Яндекс становится скучнее, потому что все боьше похоже на маккинзи - вместо чего-то сильно импактящего пользователей, просто оптимизируем еденжные метрики. Где работа не похожа на это, то есть есть либо "мы на острие прогресса, никто раньше так не делал", либо "мы делаем супер-импактящую общество штуку"
16 ответов
С самого начала развития теории ветвящихся процессов было ясно, что в некоторых случаях они могут быть применены в генетике. Но в 1948 году в СССР был окончательно завершен разгром генетики. При существовавшем тогда официальном государственном мировоззрении разгром генетики привел к тому, что даже теория вероятностей оказалась под угрозой стать в глазах властей «вредной наукой». В 1946 году вышел в четвертом издании учебник академика Сергея Натановича Бернштейна «Теория вероятностей», в котором было много задач, связанных с законами Менделя. Учебник быстро разошелся, и все попытки автора издать стереотипно следующее издание не привели к успеху. От автора требовали убрать эти задачи, на что он не согласился. Одним из тех, кто принимал активное участие в уничтожении генетики в СССР, был академик Трофим Денисович Лысенко, президент Всесоюзной академии сельскохозяйственных наук. Лысенко тогда бросил лозунг: «Наука – враг случайности». Отсюда недалеко и до организационных выводов. Я не могу забыть, как блестяще в МГУ публично выступил член-корреспондент Академии наук СССР Александр Яковлевич Хинчин. Он сказал: «Известен лозунг: «Наука – враг случайности». И это абсолютно верно. Но врага надо изучать. И это делает теория вероятностей».
воспоминания Б.А. Севастьянова
Заметка из Телеграм-канала "Воспоминания математиков", который всем рекомендую @mathmemories
6 ответов
Благодаря журналистам всем известно, что за возникновение массы ответсвенен бозон Хиггса.
Благодаря фантастам и не только всем известна разрушительная сила антивещества.
Всё что нужно - это объединить 2 понятия!
Антибозон Хиггса пока что остается гипотетической частицей. Но мы можем представить его потенциальное воздействие на процессы в организме, основываясь на предполагаемых свойствах и характеристиках частицы Хиггса и античастицы.
Антибозон Хиггса взаимодействует с фундаментальными частицами, такими как кварки или лептоны, и изменяет их массу. Уменьшение массы этих частиц может привести к снижению массы всего организма в целом.
Это можно сравнить с изменением веса предмета на земле и на луне: из-за различий в гравитационной силе предмет будет иметь разную массу. Аналогично, изменение массы элементарных частиц под воздействием антибозона Хиггса может привести к уменьшению общей массы организма.
7 ответов
На фоне происходящих сейчас электоральных мероприятий закину новый hot take, связанный как раз с этим процессом.
Возможна ли само-модерирущюаяся распределённая система принятия справедливых решений любой сложности и важности, способная заменить централизованную государственную власть? В каких единицах вообще выражается власть, в какой пропорции это деньги и сила, а в какой что-то ещё?
Моё мнение: хотелось бы мечтать о такой штуке, но совершенно непонятно, каким образом, кроме силового принуждения, можно заставить людей соблюдать решения, принятые даже в такой "честной" системе. Власть, с другой стороны, в моём понимании выражается как деньги + авторитет + сила (не личная, а групповая), причём авторитет (уважение, полученное за продуцирование справедливых решений) в этой сумме играет меньшую роль, чем два других слагаемых. Бедное население не может влиять на власть с помощью кошелька, поэтому и демократии среди такого населения построить не получится, какую бы доступную и честную систему принятия решений не придумать.
Когда я об этом думал, то представлял себе многоуровневую систему фильтрации идей - грубо говоря, любой может закинуть идею, а пять случайных человек её пропускают наверх или аргументированно отбивают, а другие пять случайных человек проверяют аргументы первой группы. Отфильтрованные идеи попадают уже не в пятиугольник, а в группу побольше, и там фильтруются в таком же формате, таким образом, наверх всплывают потенциально хорошие идеи.
Другая идея у меня была в назначении экспертных представителей по различным важным жизненным вопросам. Грубо говоря, я знаю несколько человек, которые точно являются специалистами в какой-то области, и могу доверить им принимать за себя решения в этой области (здравоохранение, образование, строительство, и так далее). Те люди, в свою очередь, могут или сами принимать решения с весом, равным количеству представляемых людей, или передавать их дальше, где веса будут суммироваться по такому же принципу. Получается некоторый аналог министерств, но решения принимаются на основе экспертизы, а не на основе карьерного продвижения во власти. Забавное следствие в такой системе - уважение и вес можно легко растерять, если принять непопулярное решение, так как сделанный выбор будет легко увидеть. Таким образом, голосовать выбранные представители будут более серьёзно. В целом Госдуму можно было бы организовать по такому же принципу, но политика, в отличие от экспертных областей, гораздо грязнее, и там уже работают другие законы.
9 ответов
Сегодня мы рассмотрим решение задачи 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 ответ
Сегодня чуток похулиганим и предоставим переоптимизированное решение для задачи 2554. Maximum Number of Integers to Choose From a Range I. В реальном интервью такое могут потребовать лишь на уровне идеи, но нам интересно запрограммировать самим :)
Описание задачи 📋
Необходимо выбрать максимально возможное количество чисел из диапазона [1,n], при этом соблюдая ограничения:
- Числа из списка banned выбирать нельзя.
- Каждое число можно использовать не более одного раза.
- Сумма выбранных чисел не должна превышать maxSum.
Результатом должно быть количество чисел, которые можно выбрать, удовлетворяя этим условиям.
Идея решения 💡
Предвычисляем суммы запрещённых чисел и используем двоичный поиск, чтобы найти максимальное k, для которого сумма допустимых чисел в диапазоне [1,k] не превышает maxSum. Это позволяет эффективно учитывать ограничения и избежать лишних вычислений.
Обзор решения 🧠
-
Сортировка и удаление дубликатов:
- Сортируем массив
banned и удаляем повторяющиеся элементы.
-
Предвычисление кумулятивных сумм:
- Создаем массив
ban_sums, где на позиции i содержится сумма первых i запрещённых чисел. Это позволяет быстро вычислять сумму запрещённых чисел до любого предела.
Читать дальше →
ответить
Ссылка на задачу – 1718. Construct the Lexicographically Largest Valid Sequence.
📌 Условие задачи
Дано число n. Необходимо построить последовательность, удовлетворяющую следующим условиям:
- Число
1 встречается ровно один раз.
- Каждое число
i от 2 до n встречается ровно дважды.
- Для каждого числа
i > 1, два его вхождения в последовательность находятся на расстоянии ровно i.
- Среди всех возможных последовательностей требуется выбрать лексикографически наибольшую.
💡 Идея
Бэктрекинг — хороший способ решения данной задачи.
Чтобы получить лексикографически наибольшую последовательность, мы должны размещать сначала наибольшие числа.
🔄 Подробности метода
- Рекурсивно заполняем последовательность, начиная с первого свободного индекса.
- Используем массив
used, который отслеживает, какие числа уже размещены.
- Пропускаем занятые позиции.
- Проверяем возможность размещения числа заранее, прежде чем выполнять рекурсию.
Читать дальше →
ответить
Сегодняшняя задача 1475. Final Prices With a Special Discount in a Shop решается с помощью стандартного стека, но интересно и нестандартно выглядит мотивация его использования.
Описание задачи 🛒
У вас есть массив цен prices, где prices[i] — это цена i-го товара. Если вы покупаете товар i, вы можете получить скидку, равную цене первого товара с индексом j>i, для которого выполняется условие prices[j] ≤ prices[i]. Если такого товара нет, скидка не применяется. Требуется вернуть массив, где каждая позиция показывает финальную цену с учётом скидки.
Идея 🤔
- Мы идём по массиву цен и обрабатываем товары по порядку.
- Для каждого товара находим, для каких товаров он определяет скидку, проверяя необработанные товары с индексами слева, чья цена больше или равна текущей.
- Чтобы эффективно отслеживать эти необработанные товары, используем монотонный стек. Этот стек хранит индексы товаров, цены которых упорядочены по возрастанию. Это позволяет быстро находить и применять скидки.
Подход 🚀
- Создаём стек
discount_candidates, чтобы хранить индексы товаров, ожидающих применения скидки.
- Итерируем по массиву
prices:
- Пока верхний элемент стека соответствует условию скидки (
цена товара в стеке ≥ текущей цене), применяем скидку и удаляем элемент из стека.
Читать дальше →
ответить
Сегодня нам предстоит решить задачу 494. Target Sum.
Описание задачи 📜
Нам дана последовательность чисел nums и целевая сумма target.
Необходимо определить количество способов поставить знаки + или - перед числами так, чтобы выражение из всех чисел дало в результате target.
Пример
Для nums = [1, 1, 1, 1, 1] и target = 3, всего 5 правильных комбинаций:
-1+1+1+1+1+1-1+1+1+1+1+1-1+1+1+1+1+1-1+1+1+1+1+1-1
Идея 💡
Эту задачу можно свести к известной задаче о рюкзаке:
-
Разделим числа на две группы:
Sum_Positive — сумма чисел со знаком +,Sum_Negative — сумма чисел со знаком -.
-
Из уравнений:
Sum_Positive − Sum_Negative = Target
Читать дальше →
ответить
Ссылка на задачу – 2364. Count Number of Bad Pairs.
📌 Описание задачи
Дан массив nums, где пара индексов (i, j) называется плохой, если выполняется:
Требуется найти общее количество таких плохих пар.
💡 Идея
- Запишем условие хорошей пары:
j−i = nums[j]−nums[i]
- Переставляя слагаемые, получаем:
nums[j]−j = nums[i]−i
То есть если два индекса имеют одинаковое значение позиционной разности (nums[k] - k), – они образуют хорошую пару!
🛠️ Детали метода
- Создаём массив позиционных разностей:
pos_diff[i]=nums[i]−i
- Сортируем массив
pos_diff, группируя одинаковые значения.
- Используем метод
chunk_by для подсчёта частот одинаковых значений.
- Для каждой такой частоты
count, вычисляем количество хороших пар:
count×(count−1)/2
- Всего существует
n × (n - 1) / 2 пар, из них вычитаем хорошие пары и получаем ответ.
⏳ Асимптотика
- Время:
O(n·log n), так как сортировка доминирует над остальными операциями.
- Память:
O(n), так как храним pos_diff.
🔥 Хотя сортировка для подсчёта частот медленнее хеш-таблиц в асимптотике, на практике она быстрее из-за низкой константы!
📝 Исходный код
impl Solution {
pub fn count_bad_pairs(nums: Vec<i32>) -> i64 {
let n = nums.len() as i64;
// Compute adjusted values (nums[i] - i) and sort
let mut pos_diff: Vec<_> = nums.into_iter()
.enumerate()
.map(|(idx, num)| num - idx as i32)
.collect();
pos_diff.sort_unstable();
// Count good pairs using `chunk_by`
let good_pairs: i64 = pos_diff
.chunk_by(|a, b| a == b)
.map(|chunk| (chunk.len() as i64 * (chunk.len() as i64 - 1)) / 2)
.sum();
// Total pairs - good pairs = bad pairs
let total_pairs = n * (n - 1) / 2;
total_pairs - good_pairs
}
}
Tags: #rust #algorithms #math
ответить
Задача - 2493. Divide Nodes Into the Maximum Number of Groups.
📌 Постановка задачи
Дан неориентированный граф с n вершинами, возможно несвязный. Требуется разбить вершины на m групп, соблюдая условия:
✔ Каждая вершина принадлежит ровно одной группе.
✔ Если вершины соединены ребром [a, b], то они должны находиться в смежных группах (|group[a] - group[b]| = 1).
✔ Найти максимальное количество таких групп m.
✔ Вернуть -1, если разбиение невозможно.
💡 Идея
- Граф можно корректно разбить на группы ↔ он двудольный.
- Максимальное количество групп связано с максимальной глубиной BFS в каждой компоненте.
- Мы проверяем BFS из каждой вершины, чтобы найти наилучший возможный корень для каждой компоненты.
🔍 Детали подхода
- Строим граф в виде списка смежности.
- Запускаем
BFS из каждой вершины (а не только из одной в компоненте) для:
- Проверки двудольности (по уровням
BFS).
- Поиска максимальной глубины
BFS (max_level).
- Определения уникального идентификатора компоненты (
min_index).
Читать дальше →
ответить
Сегодня мы решаем задачу 3243. Shortest Distance After Road Addition Queries I
Постановка
В задаче требуется вычислить кратчайший путь от города 0 до города n-1 после каждой из последовательных добавлений новых дорог в граф. Изначально города соединены цепочкой дорог, и после каждой операции добавляется новая односторонняя дорога между двумя городами. Необходимо после каждой операции находить кратчайшее расстояние от города 0 до города n-1.
🔍 Идея
Данное решение использует оптимизированный подход с поочередным обновлением расстояний с помощью BFS и ранним выходом при нахождении цели (города n-1). Мы обновляем граф и расстояния только при необходимости, что позволяет сократить количество ненужных вычислений и повысить производительность.
📚 Обзор решения
-
Инициализация графа и расстояний:
- Сначала создаем список смежности
succ, который представляет дороги между городами, инициализируем его так, чтобы города были соединены цепочкой (каждый город соединен с следующим).
- Массив
dist инициализируется так, что расстояние от города 0 до города i равно i (для начальной цепочки).
-
Обработка запросов:
- Для каждого запроса добавляется новая дорога между городами
u и v. После этого запускается BFS с города v для обновления кратчайших расстояний до всех достижимых городов.
Читать дальше →
ответить
Новый день - новая задача 2109. Adding Spaces to a String.
Условие 🧩
Дана строка s и массив индексов spaces. Нужно добавить пробелы перед символами строки, расположенными по данным индексам, и вернуть новую строку. Например, для s = "EnjoyYourCoffee" и spaces = [5, 9] результатом будет "Enjoy Your Coffee".
Если решать абы как, то можно и в ней запутаться в индексах. Мы же будем делать все максимально просто.
Идея решения 🧠
Вместо создания промежуточных строк или модификации исходной строки, мы используем построение строки с выделением памяти заранее, чтобы минимизировать накладные расходы.
Подход 🔍
- Предварительно выделяем память для результирующей строки с помощью
String::with_capacity, учитывая длину строки и количество пробелов.
- Проходим по массиву индексов spaces:
- Добавляем в результат подстроку от предыдущей позиции до текущего индекса.
- Добавляем пробел.
- После цикла добавляем оставшуюся часть строки.
- Возвращаем итоговую строку.
Анализ сложности 📊
- Временная сложность:
O(n), где n=длина строки+количество пробелов. Все операции выполняются за один проход.
- Пространственная сложность:
O(n), поскольку результирующая строка создаётся с заранее выделенной памятью.
Исходный код решения
impl Solution {
pub fn add_spaces(s: String, spaces: Vec<i32>) -> String {
let mut result = String::with_capacity(s.len() + spaces.len()); // Pre-allocate capacity for efficiency
let mut word_pos = 0;
for &space_pos in &spaces {
let space_pos = space_pos as usize; // Convert i32 to usize for indexing
result.push_str(&s[word_pos..space_pos]); // Add the substring
result.push(' '); // Add the space
word_pos = space_pos;
}
result.push_str(&s[word_pos..]); // Add the remaining substring
result
}
}
Ссылка на задачу – 1352. Product of the Last K Numbers.
📌 Описание задачи
Необходимо создать структуру ProductOfNumbers, которая:
- Позволяет добавлять числа в поток (
add(num)).
- Вычисляет произведение последних k чисел (
get_product(k)).
Гарантируется, что ответы не приведут к переполнению 32-битного целого.
💡 Идея
Будем использовать префиксные произведения.
Это позволит получать результат за O(1), выполняя деление последних значений.
Но так как деление на 0 запрещено, придётся аккуратно отслеживать этот случай и сбрасывать произведения при появлении нуля.
⚙️ Подход
- Используем
Vec<i64> для хранения префиксных произведений.
- Добавление числа:
- Если
num == 0, очищаем хранилище, так как любое произведение после нуля будет равно нулю.
- Иначе умножаем предыдущее произведение на текущее число и сохраняем результат.
- Вычисление
get_product(k):
- Если
k больше количества сохранённых чисел, возвращаем 0.
- Иначе делим последнее префиксное произведение на значение
k шагов назад.
Читать дальше →
ответить
Сегодня разберём ещё одну простую задачу 1455. Check If a Word Occurs As a Prefix of Any Word in a Sentence.
Описание задачи 📜
Дана строка sentence, состоящая из слов, разделённых пробелами, и строка searchWord. Нужно определить индекс (считаем с 1), где searchWord является префиксом какого-либо слова в sentence. Если такого слова нет — вернуть -1.
Решение 🛠️
Идея 💡
Задача сводится к простому проходу по словам строки. Мы должны проверить каждое слово: начинается ли оно с searchWord. Возвращаем индекс первого подходящего слова.
Алгоритм 🚀
- Разделяем строку
sentence на слова с помощью метода split_whitespace, который возвращает ссылки на части исходной строки.
- Проходим по словам с их индексами через
enumerate.
- Для каждого слова проверяем, начинается ли оно с
searchWord с помощью метода starts_with.
- Если находим соответствие, возвращаем индекс (преобразуем его в формат 1-based). Если совпадений нет, возвращаем
-1.
Анализ Сложности 📊
-
Временная сложность:
O(n), где n — длина строки sentence. Разделение строки и проверка префикса выполняются за линейное время.
-
Пространственная сложность:
O(k), где k — количество слов в предложении. Дополнительная память используется только для хранения указателей на слова, а не самих слов.
Исходный код решения
impl Solution {
pub fn is_prefix_of_word(sentence: String, search_word: String) -> i32 {
// Split the sentence into words using whitespace as a delimiter
let words = sentence.split_whitespace();
// Iterate through the words with their indices
for (index, word) in words.enumerate() {
// Check if search_word is a prefix of the current word
if word.starts_with(&search_word) {
return (index + 1) as i32; // Convert 1-based index to i32 and return
}
}
-1 // Return -1 if no prefix match is found
}
}
Ссылка на задачу – 3174. Clear Digits.
📌 Описание задачи
Дана строка s, содержащая буквы и цифры. Из неё возможно удалять цифры только путем выполнения следующей операции:
- Удалить первую найденную цифру и ближайший нецифровой символ слева.
Вернуть итоговую строку после итеративного выполнения указанной операции до исчезновения всех цифр.
💡 Идея
Достаточно легко придумать алгоритм, формирующий ответ справа-налево (просто запоминаем, сколько символов нужно скипнуть после встреченных цифр).
Мы же реализуем решение с прямым (слева-направо) обходом строки без необходимости переворачивания результата.
- Используем буфер (
buffer) для хранения промежуточного результата.
- Используем указатель
write_index, который отслеживает место для записи следующего символа.
- При встрече цифры уменьшаем
write_index (удаляем ближайший нецифровой символ).
⚙ Подробности подхода
- Инициализируем буфер размером
s.len() (заполняем заглушками '\0').
Читать дальше →
ответить
Очередная наша задача - 3381. Maximum Subarray Sum With Length Divisible by K
Описание задачи
Дано целое число k и массив чисел nums. Необходимо найти максимальную сумму подмассива, длина которого кратна k.
🚀 Идея
Данная задача расширяет классический алгоритм нахождения максимальной суммы подмассива (алгоритм Кадане) для случаев, когда длина подмассива должна быть кратной k. Чтобы учесть это условие, мы перебираем все смещения в полуинтервале [0,k) и анализируем подмассивы с шагом k.
🔍 Подход
- Префиксные суммы:
- Вычисляем массив префиксных сумм, чтобы быстро находить сумму любого подмассива.
- Перебор смещений:
- Итерируем по всем возможным начальным смещениям
[0,k), чтобы обрабатывать подмассивы длиной, кратной k.
- Модификация алгоритма Кадане:
- Для каждого смещения применяем алгоритм нахождения максимальной суммы подмассива.
- Если текущая сумма становится отрицательной, начинаем новый расчет с текущей позиции (сброс индекса начала подмассива).
Читать дальше →
ответить
Начну-ка я минипроект по разбору ежедневных задач с LeetCode.
Решения будут на раст, ибо: модно, стильно, молодёжно!
Rust идеально подходит для задач с LeetCode благодаря высокой производительности, безопасному управлению памятью и удобным инструментам для работы с данными, обеспечивая компактный и надёжный код.
Надеюсь, такой контент будет полезен аудитории.
ответить
Сегодня у нас еще одна задача на аккуратное манипулирование индексами 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', и уменьшаем счётчик.
Читать дальше →
ответить
Ссылка на задачу — 1415. The k-th Lexicographical String of All Happy Strings of Length n.
📝 Описание задачи
"Счастливая строка" – это строка длины n, состоящая только из символов ['a', 'b', 'c'], в которой нет двух одинаковых подряд идущих символов.
Нужно найти k-ю счастливую строку в лексикографическом порядке, либо вернуть "", если таких строк меньше k.
💡 Идея
Рассмотрим связь счастливых строк с двоичными строками.
Каждая счастливая строка:
- Начинается с одного из трёх символов (
'a', 'b', 'c') → 3 варианта.
- Остальные
(n-1) символов формируются по аналогии с двоичной строкой, где у каждого символа есть ровно два возможных варианта → ×2 на каждую позицию.
Таким образом, двоичное представление k-1 почти полностью определяет структуру требуемой строки (без первого символа).
Мы можем использовать биты 0 и 1 из этого двоичного представления, чтобы выбирать между двумя допустимыми символами при итеративной генерации каждого следующего символа конкретной счастливой строки. 🚀
🔍 Детали подхода
- Определяем количество возможных строк с фиксированным первым символом:
Читать дальше →
ответить
Следующая задача для разбора - 1462. Course Schedule IV
✨ Описание задачи
У нас есть 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 отмечаем прямые зависимости в матрице.
Читать дальше →
ответить
В нашей новой задаче - 1765. Map of Highest Peak продолжим закреплять работу с семейством простых графовых алгоритмов.
📜 Описание задачи
Вам дана матрица isWater размером m×n, где:
isWater[i][j] == 1 указывает, что клетка — это вода.isWater[i][j] == 0 указывает, что клетка — это суша.
Требуется назначить высоты каждой клетке таким образом, чтобы:
- Высота каждой клетки была неотрицательной.
- Высота любой клетки с водой была равна 0.
- Абсолютная разница высот у соседних клеток не превышала 1.
- Максимальная высота в назначенной карте была как можно больше.
💡 Идея
Мы используем поиск в ширину с несколькими источниками (multi-source BFS), начиная с клеток воды (высота 0).
На каждом шаге ближайшие клетки суши получают высоту на 1 больше текущей.
Этот метод гарантирует, что все клетки суши получают наилучшую из возможных высот, что приводит к максимизации самой высокой высоты в матрице.
🛠 Подробности подхода
- Инициализация:
- Создаём очередь и добавляем в неё все клетки воды, помечая их высотой
0.
Читать дальше →
ответить
Следующая наша задача - 1014. Best Sightseeing Pair.
Описание задачи 📝
Дано: массив values, где
values[i] — это ценность туристической достопримечательности,j-i — расстояние между двумя достопримечательностями i и j.
Требуется: найти пару достопримечательностей (i < j) с максимальной совместной ценностью по формуле:
score = values[i] + values[j] + i − j
Идея 💡
Основная задача заключается в оптимизации вычислений. Если переписать формулу как:
score = (values[i] + i) + (values[j] − j),
то видно, что для эффективного решения нужно поддерживать максимум для values[j]−j во время итерации.
Это позволяет избежать вложенных циклов и сократить сложность до O(n).
Детали подхода 🛠️
- Используем обратный обход массива с помощью
.enumerate().rev().
- На каждой итерации:
- Вычисляем текущую наилучшую ценность:
score = values[i] + i + max_right,
Читать дальше →
ответить
Очередная задача — 2375. Construct Smallest Number From DI String сходу выглядит переборной, но может быть эффективно реализована за счёт использования графовых алгоритмов.
📝 Описание задачи
Дан строковый шаблон 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).
⚙️ Детали подхода
Читать дальше →
ответить
Страница
1
2
3
4
