Любимые факты об английском. Просто так, может, вы тоже порадуетесь. Ничего сверхъестественного, но удивляет, когда задумаешься.
"Ученик" ("школьник") по-английски "зрачок". То есть, "я весь внимание", буквально.
По-английски в радуге тоже семь цветов. Но это другие семь цветов. Синий и голубой ведь один и тот же цвет, а вот фиолетовые бывают разные.
"Государство" по-английски звучит примерно как "состояние дел". "Failed state" это не когда из крана перестает течь вода, а террористы мародерят в пригородах столицы, это просто констатация того, что некое "состояние дел" перестало самовоспроизводиться. "State", впрочем, даже в узком значении "состояние дел, связанное с управлением людьми на определенном куске земного шара" бывает не только таким, к которому мы привыкли (то, скорее, "nation state").
Слова "gore" в русском языке нет, хотя понятие, казалось бы, абсолютно базовое.
Слово "убийца" можно перевести на английский по меньшей мере 8 разными способами (slayer, killer, murderer, assassin, hitman, triggerman, manslayer, cutthroat). Наверное, есть больше. По-русски есть ещё душегуб, головорез (хотя он, скорее, thug, чем cutthroat) и позаимствованный "киллер". Вроде бы, всё?
Слова "зависть" и "ревность" почти взаимозаменяемы и носители языка считают нужным многословно пояснять разницу между ними, причем "зависть" (по крайней мере, в подобных заметках) считается более позитивным чувством. С другой стороны, "ревность" это вообще-то два разных слова, jealousy и insecurity, в зависимости от того, обладает ли испытывающий это чувство предметом вожделения в настоящий момент. "Insecurity", впрочем, это далеко не только "ревность". Сложна.
"Интеллигенция" по-английски "intelligentsia". В XXI веке употребляется далеко не только (и уже, по-моему, не столько) в значении "...в СССР", хотя раньше слово с таким значением почему-то никому не требовалось.
2 ответа
Страшилку "серой слизи" изобрел футуролог Эрик Дрекслер еще в прошлом веке. Суть идеи в том, что самовоспроизводящиеся наноботы, если упустить их из лаборатории, могут начать бесконечно копировать себя, и в результате Земля превратится в бесформенную "серую слизь", состоящую из гигантской массы нанороботов.
В 2024 году даже самые параноидальные исследователи экзистенциальных рисков относятся к "серой слизи" не слишком всерьёз. Мы не умеем делать самовоспроизводящихся наноботов и вряд ли научимся до того, как изобретём сильный искусственный интеллект который все равно нас уничтожит, с наноботами или без них.
Да?
Нет, первый реалистичный кандидат на роль "серой слизи" уже активно обсуждается, и именно в контексте "давайте сразу запретим, не дожидаясь, пока это начнут делать".
Чтобы понятно было, что это за зверь, почему его создание относительно реалистично, и чем всё это страшно, для начала напомню про понятие хиральности. Сложные органические молекулы могут быть несимметричными. В этом случае зеркальное отражение той же молекулы будет от неё отличаться. Например, для человека молекула "левой" хиральности может быть нормальным участником его метаболизма, а "правая" будет токсична.
Почему так происходит, ведь вроде бы законы химии инвариантны относительно зеркальной симметрии? Дело в том, в этом смысле почему-то несимметричны все живые существа. Аминокислоты, из которых состоят белки, в природе существуют почти исключительно в "левой" форме, а сахара, например, глюкоза, только в "правой". Хотя при замене хиральности у всех молекул, участвующих в реакции, ничего не поменялось бы, если заменить хиральность только у части из них, она может пойти совсем иначе, поэтому то, что жизнь несимметрична, важно.
Читать дальше →
3 ответа
Ссылка на задачу — 3191. Minimum Operations to Make Binary Array Elements Equal to One I.
📌 Описание задачи
- Дан массив
nums, состоящий из 0 и 1.
- Можно переворачивать любые три подряд идущих элемента (
0 становится 1, а 1 — 0).
- Нужно найти минимальное количество операций, чтобы сделать все элементы
1. Если это невозможно, вернуть -1.
Пример:
- Вход:
nums = [0,1,1,1,0,0]
- Выход:
3
- Объяснение: Можно выполнить следующие операции:
1️⃣ Выбираем элементы с индексами [0,1,2]. Новый массив: [1,0,0,1,0,0]
2️⃣ Выбираем элементы с индексами [1,2,3]. Новый массив: [1,1,1,0,0,0]
3️⃣ Выбираем элементы с индексами [3,4,5]. Новый массив: [1,1,1,1,1,1] ✅
💡 Идея
- Будем искать необходимые перевороты слева-направо (это валидно, ибо 3-перевороты коммутируют друг с другом).
- Вместо непосредственного изменения
nums будем использовать битовый сдвиговый регистр flip_state (на 2 бита) для отслеживания переворотов вперед на 2 значения.
Читать дальше →
ответить
Ссылка на задачу — 2551. Put Marbles in Bags.
📌 Описание задачи
- Дан массив
weights, где weights[i] — вес i-го куска мрамора.
- Требуется разделить все куски на
k непустых мешков, соблюдая следующие правила:
- Каждый мешок содержит хотя бы один кусок.
- Если в мешке есть куски с индексами
i и j, то все элементы между ними также должны входить в этот мешок.
- Стоимость мешка — это сумма весов первого и последнего куска в нём, то есть:
weights[i] + weights[j].
- Нужно вернуть разность между максимально возможной и минимально возможной общей стоимостью всех
k мешков.
💡 Идея
При разбиении на k подряд идущих мешков мы делаем k - 1 разрез между кусками.
Каждый разрез влияет на итоговую сумму добавлением пары вида weights[i] + weights[i+1],
где i — индекс последнего элемента в предыдущем мешке.
Следовательно, вся задача сводится к выбору k - 1 пар соседних кусков, которые:
- минимизируют сумму (для минимального варианта),
- максимизируют сумму (для максимального варианта).
Читать дальше →
ответить
Для задачи 769. Max Chunks To Make Sorted у меня есть очень короткое решение, а значит и разбор не стоит делать длинным ;)
Задача: Максимальное количество отсортированных блоков 🧩
Дана перестановка arr длины n. Нужно разделить массив на максимальное количество блоков, таких, что, отсортировав каждый блок по отдельности и объединив их, получится полностью отсортированный массив.
Идея
Вводим функцию баланса, зависящую от частичных сумм по индексам и значениям. Каждый новый блок формируем при нулевых балансах.
Подход
Напишем код самым коротким и непонятным читателю образом, как только умеем.
Сложность:
O(n) по времениO(1) по памяти
Исходный код
impl Solution {
pub fn max_chunks_to_sorted(arr: Vec<i32>) -> i32 {
arr.into_iter().enumerate().fold(
(0, 0), |acc, (val, idx)| (
acc.0 + val as i64 - idx as i64,
acc.1 - (acc.0.abs()-1).min(0) as i32)
).1
}
}
Ссылка на задачу — 2594. Minimum Time to Repair Cars.
❓ Описание задачи
Дано:
ranks — список рангов механиков.- механик с рангом
r может починить n машин за r * n² минут.
cars — общее количество машин, ожидающих ремонта.
Нужно найти минимальное время, за которое все машины будут отремонтированы.
Предполагается, что все механики работают одновременно.
💡 Идея
Механики с меньшим рангом работают быстрее.
Произведём первичное распределение машин, используя обратный квадратный корень ранга как вес, определяющий долю машин, переданных каждому механику.
Однако это распределение не покрывает все машины. Для распределения оставшихся машин мы посчитаем для каждого механика оценку времени его работы, если взять несколько дополнительных машин (тем больше, чем больше вес механика). После остаётся лишь выбрать k-ое минимальное значение среди посчитанных времён с помощью алгоритма «QuickSelect» (любезно реализованного в стандартной библиотеке Rust).
🔍 Детали подхода
1️⃣ Быстрое распределение — вычисляем вес каждого механика и распределяем машины пропорционально.
Читать дальше →
ответить
Ссылка на задачу — 3169. Count Days Without Meetings.
📌 Описание задачи
- Данo
days — количество дней, в течение которых сотрудник доступен для работы.
- Также дан массив
meetings, где meetings[i] = [starti, endi] обозначает дни проведения встречи.
Нужно посчитать количество дней, когда сотрудник свободен от встреч и может работать.
💡 Идея
Мы сортируем встречи по дню начала, чтобы затем обходить их в порядке возрастания.
Это позволяет использовать метод заметания линии как эффективный способ вычислить количество свободных дней между встречами.
🚀 Детали подхода
1️⃣ Сортируем встречи по начальной дате.
2️⃣ Проходим по списку встреч, отслеживая next_free (следующий свободный день).
3️⃣ Подсчитываем разрывы между next_free и началом следующей встречи.
4️⃣ Обновляем next_free после каждой встречи, сдвигая его на день после её окончания.
5️⃣ Добавляем свободные дни после последней встречи.
⏳ Асимптотика
-
Время:
O(n·logn)
O(n·logn) на сортировку.O(n) на обход.
-
Память:
O(1)
- Используем только несколько переменных.
💻 Исходный код
impl Solution {
pub fn count_days(days: i32, mut meetings: Vec<Vec<i32>>) -> i32 {
meetings.sort_unstable_by_key(|meet| meet[0]);
let (next_free, free_count) = meetings.into_iter()
.fold((1, 0), |(next_free, free_count), meet| {
let [start, end] = meet[..2] else { unreachable!("bad meet format") };
let gap = (start - next_free).max(0);
let next_free = next_free.max(end + 1);
(next_free, free_count + gap)
});
free_count + (days - next_free + 1).max(0)
}
}
Tags: #rust #algorithms #counting
ответить
Ссылка на задачу — 2780. Minimum Index of a Valid Split.
📘 Описание задачи
- Дан массив целых чисел
nums, в котором гарантированно существует один доминирующий элемент
(то есть такой элемент, который встречается чаще, чем половина длины массива).
- Необходимо найти наименьший индекс
i, такой что массив можно разделить на две части:
nums[0],..,nums[i] и nums[i+1],..,nums[n-1],- и обе части будут иметь одинаковый доминирующий элемент.
- Если такого разделения не существует — вернуть
-1.
💡 Идея
Для эффективного поиска доминирующего элемента хорошо подходит алгоритм большинства голосов Бойера — Мура.
Зная доминирующий элемент, можно пройти по массиву и в каждой возможной точке разделения отслеживать:
- Сколько раз этот элемент встречался слева;
- Сколько осталось справа;
- Затем проверяется, является ли он доминирующим в обеих частях.
🔍 Детали подхода
- Применяем алгоритм голосования большинства для нахождения доминанты.
- Подсчитываем точное количество его вхождений, чтобы использовать для отслеживания остатка справа.
Читать дальше →
ответить
Проблема: локальные virtualenv'ы для ML-проектов жрут до хрена места, но при этом часто имеют очень много дублирующегося контента.
В моём случае 4 простеньких проекта сходу съедают 21 GB.
$ du -hs ~/.pyenv/versions/*/envs/*
7.6G /home/rutsh/.pyenv/versions/3.11.11/envs/ASpanFormer
6.0G /home/rutsh/.pyenv/versions/3.11.11/envs/LightGlue
502M /home/rutsh/.pyenv/versions/3.11.11/envs/Navigation
5.8G /home/rutsh/.pyenv/versions/3.11.11/envs/yolo
Хочется как-то более-менее просто дубликаты найти и хардлинками связать друг с другом.
Решение: утилита rdfind уже умеет всё автоматически разрешать - https://github.com/pauldreik/rdfind
В моём случае запуск "rdfind -makehardlinks true /data/pyenv_versions/" превратил 21 GB в 8.7 GB!
Пользуйтесь!!!
Tags: #tools
ответить
Сегодня чуток похулиганим и предоставим переоптимизированное решение для задачи 2554. Maximum Number of Integers to Choose From a Range I. В реальном интервью такое могут потребовать лишь на уровне идеи, но нам интересно запрограммировать самим :)
Описание задачи 📋
Необходимо выбрать максимально возможное количество чисел из диапазона [1,n], при этом соблюдая ограничения:
- Числа из списка banned выбирать нельзя.
- Каждое число можно использовать не более одного раза.
- Сумма выбранных чисел не должна превышать maxSum.
Результатом должно быть количество чисел, которые можно выбрать, удовлетворяя этим условиям.
Идея решения 💡
Предвычисляем суммы запрещённых чисел и используем двоичный поиск, чтобы найти максимальное k, для которого сумма допустимых чисел в диапазоне [1,k] не превышает maxSum. Это позволяет эффективно учитывать ограничения и избежать лишних вычислений.
Обзор решения 🧠
-
Сортировка и удаление дубликатов:
- Сортируем массив
banned и удаляем повторяющиеся элементы.
-
Предвычисление кумулятивных сумм:
- Создаем массив
ban_sums, где на позиции i содержится сумма первых i запрещённых чисел. Это позволяет быстро вычислять сумму запрещённых чисел до любого предела.
Читать дальше →
ответить
Сегодня у нас еще одна задача на аккуратное манипулирование индексами 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', и уменьшаем счётчик.
Читать дальше →
2 ответа
Но и постов давно не было. Не уверен, что получилось коммьюнити :-(
4 ответа
Сегодня нам предстоит решить задачу 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.
Читать дальше →
ответить
Задача на сегодня 3152. Special Array II.
📝 Условие:
- Нам дан массив
nums и запросы queries.
- Для каждого запроса
[from, to] нужно проверить, является ли подмассив nums[from..=to] "особым".
- Подмассив считается "особым", если каждая пара соседних элементов в нём имеет разную чётность (один чётный, другой нечётный).
🧠 Идея:
- Решение основано на идее "вычисли один раз — используй много раз".
- Сначала выполняем линейные предвычисления префиксных количеств пар соседних элементов разной чётности.
- Затём каждый запрос обрабатывается мгновенно за
O(1), что делает решение особенно эффективным для больших массивов и множества запросов 😊
💡 Подход:
-
Префиксная сумма:
- Создаём массив
prefix_count, где prefix_count[i] хранит количество пар соседних элементов с разной чётностью от начала массива до индекса i.
- Заполняем его за
O(n) в одном проходе.
-
Обработка запросов:
- Для каждого запроса
[from, to] считаем количество таких пар в диапазоне через разность: prefix_count[to] - prefix_count[from].
Читать дальше →
ответить
Сегодня мы решаем задачу 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
}
}
}
Очередная задача: 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 с накопленной максимальной ценностью событий (справа-налево).
-
Итерация и поиск:
- Для каждого события находим первое, заканчивающееся раньше его, через двоичный поиск.
- Суммируем ценности текущего события и накопленной максимальной ценности по найденному индексу, обновляя общий максимум.
Читать дальше →
ответить
Сегодня мы рассмотрим решение задачи 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 ответ
Ссылка на задачу – 1718. Construct the Lexicographically Largest Valid Sequence.
📌 Условие задачи
Дано число n. Необходимо построить последовательность, удовлетворяющую следующим условиям:
- Число
1 встречается ровно один раз.
- Каждое число
i от 2 до n встречается ровно дважды.
- Для каждого числа
i > 1, два его вхождения в последовательность находятся на расстоянии ровно i.
- Среди всех возможных последовательностей требуется выбрать лексикографически наибольшую.
💡 Идея
Бэктрекинг — хороший способ решения данной задачи.
Чтобы получить лексикографически наибольшую последовательность, мы должны размещать сначала наибольшие числа.
🔄 Подробности метода
- Рекурсивно заполняем последовательность, начиная с первого свободного индекса.
- Используем массив
used, который отслеживает, какие числа уже размещены.
- Пропускаем занятые позиции.
- Проверяем возможность размещения числа заранее, прежде чем выполнять рекурсию.
Читать дальше →
ответить
Ссылка на задачу - 2570. Merge Two 2D Arrays by Summing Values.
📌 Описание задачи
Даны два отсортированных списка nums1 и nums2, где каждый элемент представлен в виде [id, value].
Нужно объединить их в один список, упорядоченный по id, при этом суммируя значения для совпадающих id.
💡 Идея
Так как оба списка уже отсортированы по id, можно пройтись по ним одновременно, сравнивая id и добавляя элементы в результат.
Такой метод позволяет решить задачу за O(n + m) без дополнительной сортировки.
🛠 Подробности подхода
- Используем два индекса
i и j для итерации по nums1 и nums2.
- Сравниваем текущие
id:
- Если
id1 < id2 → добавляем nums1[i] в результат, сдвигаем i.
- Если
id1 > id2 → добавляем nums2[j] в результат, сдвигаем j.
- Если
id1 == id2 → суммируем значения, добавляем результат, сдвигаем оба указателя.
- Добавляем оставшиеся элементы из
nums1 и nums2, если таковые имеются.
Читать дальше →
ответить
Ссылка на задачу — 2379. Minimum Recolors to Get K Consecutive Black Blocks.
📌 Описание задачи
Дана строка blocks, состоящая из символов 'W' (белый) и 'B' (чёрный).
Необходимо определить минимальное число перекрашиваний белых блоков в чёрные, чтобы получить хотя бы одну последовательность из k подряд идущих чёрных блоков.
💡 Идея
Используем технику скользящего окна:
- будем двигать окно размера
k по строке и считать количество белых блоков внутри окна;
- минимальное количество белых блоков среди всех окон и будет ответом.
📖 Детали подхода
- Посчитаем число белых блоков в первом окне размера
k.
- Сдвигаем окно вправо на один символ за раз:
- если символ, который «входит» в окно, белый (
'W'), увеличиваем счётчик;
- если символ, который «выходит» из окна, белый, уменьшаем счётчик.
- После каждого сдвига окна обновляем минимальное найденное значение.
- Итоговый ответ — это минимальное число белых блоков за всё время обхода.
⏳ Асимптотика
- Время:
O(n) — каждый символ просматривается не более двух раз.
- Память:
O(1) — используется константная дополнительная память.
🛠️ Исходный код
impl Solution {
pub fn minimum_recolors(blocks: String, k: i32) -> i32 {
let blocks = blocks.as_bytes();
let k = k as usize;
// Count white blocks ('W') in the first window of size k
let initial_recolors = blocks[..k].iter().filter(|&&b| b == b'W').count() as i32;
// Slide window over the blocks using iterator methods
blocks
.windows(k+1)
.fold((initial_recolors, initial_recolors), |(current, min), window| {
// Update recolors based on outgoing and incoming blocks
let next = current
+ (window.last() == Some(&b'W')) as i32
- (window.first() == Some(&b'W')) as i32;
(next, min.min(next))
}).1
}
}
Tags: #rust #algorithms #counting
ответить
Сегодняшняя задача 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
ответить
Ссылка на задачу — 3108. Minimum Cost Walk in Weighted Graph.
📌 Описание задачи
- Дан неориентированный взвешенный граф с
n вершинами и m рёбрами.
- Каждое ребро представлено тройкой
[u, v, w], означающей, что существует ребро между u и v с весом w.
- Определим стоимость пути между двумя вершинами как битовое
AND всех рёбер, пройденных на пути (вершинам в таком пути разрешено повторяться).
- Для каждого запроса
[s, t] требуется найти минимальную AND-стоимость пути между s и t.
- Если пути не существует, ответ
-1.
Пример
- Входные данные:
n = 5; edges = [[0,1,7],[1,3,7],[1,2,1]]; query = [[0,3],[3,4]]
- Результаты:
[1, -1]
- Объяснение:
- Наилучший путь от
0 до 3: 0 → 1 → 2 → 1 → 3.
- Путей из
3 в 4 не существует.
- Графическая интерпретация:
💡 Идея
- Так как каждое новое ребро пути его стоимость не увеличивает, то внутри каждой компоненты связности стоимость минимального пути будет одинаковой (достаточно определить путь, проходящий через все рёбра компоненты связности).
Читать дальше →
1 ответ
Страница
1
2
3
4
