Любимые факты об английском. Просто так, может, вы тоже порадуетесь. Ничего сверхъестественного, но удивляет, когда задумаешься.
"Ученик" ("школьник") по-английски "зрачок". То есть, "я весь внимание", буквально.
По-английски в радуге тоже семь цветов. Но это другие семь цветов. Синий и голубой ведь один и тот же цвет, а вот фиолетовые бывают разные.
"Государство" по-английски звучит примерно как "состояние дел". "Failed state" это не когда из крана перестает течь вода, а террористы мародерят в пригородах столицы, это просто констатация того, что некое "состояние дел" перестало самовоспроизводиться. "State", впрочем, даже в узком значении "состояние дел, связанное с управлением людьми на определенном куске земного шара" бывает не только таким, к которому мы привыкли (то, скорее, "nation state").
Слова "gore" в русском языке нет, хотя понятие, казалось бы, абсолютно базовое.
Слово "убийца" можно перевести на английский по меньшей мере 8 разными способами (slayer, killer, murderer, assassin, hitman, triggerman, manslayer, cutthroat). Наверное, есть больше. По-русски есть ещё душегуб, головорез (хотя он, скорее, thug, чем cutthroat) и позаимствованный "киллер". Вроде бы, всё?
Слова "зависть" и "ревность" почти взаимозаменяемы и носители языка считают нужным многословно пояснять разницу между ними, причем "зависть" (по крайней мере, в подобных заметках) считается более позитивным чувством. С другой стороны, "ревность" это вообще-то два разных слова, jealousy и insecurity, в зависимости от того, обладает ли испытывающий это чувство предметом вожделения в настоящий момент. "Insecurity", впрочем, это далеко не только "ревность". Сложна.
"Интеллигенция" по-английски "intelligentsia". В XXI веке употребляется далеко не только (и уже, по-моему, не столько) в значении "...в СССР", хотя раньше слово с таким значением почему-то никому не требовалось.
Для задачи 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
}
}
Сегодня нам предстоит решить задачу 1792. Maximum Average Pass Ratio.
Описание задачи 📚
У нас есть школа, где классы проводят итоговые экзамены. Каждый класс описывается массивом [pass_i,total_i], где:
pass_i — количество учеников,
Читать дальше →
Сегодня нам предстоит несложная задача - 2182. Construct String With Repeat Limit. Но технически она получилась муторной - требует от программиста очень аккуратного подхода к себе :)
Задача 📜
Дана строка s, состоящая из произвольных символов, и число repeat_limit. Необходимо построить лексикографически максимальную строку, используя символы из s, но с ограничением:
- один и тот же символ не может встречаться более
repeat_limit раз подряд.
Подход 🚀
-
Подсчёт частоты символов:
- Используем массив размера
256, чтобы подсчитать количество вхождений каждого байта (символа).
-
Жадный выбор символов:
- Обходим пространство символов (
0–255), начиная с самого большого.
- Добавляем текущий символ в результат до
repeat_limit раз или пока его количество не исчерпается.
- Если нужно "разорвать" последовательность, вставляем следующий по величине символ, уменьшая его количество.
-
Эффективный поиск следующего символа:
- Вспомогательная функция
find_last_valid_index ищет ближайший допустимый символ с ненулевой частотой, используя знание о текущем символе как ускоряющую подсказку.
Читать дальше →
Сегодняшняя задача 1475. Final Prices With a Special Discount in a Shop решается с помощью стандартного стека, но интересно и нестандартно выглядит мотивация его использования.
Описание задачи 🛒
У вас есть массив цен prices, где prices[i] — это цена i-го товара. Если вы покупаете товар i, вы можете получить скидку, равную цене первого товара с индексом j>i, для которого выполняется условие prices[j] ≤ prices[i]. Если такого товара нет, скидка не применяется. Требуется вернуть массив, где каждая позиция показывает финальную цену с учётом скидки.
Идея 🤔
- Мы идём по массиву цен и обрабатываем товары по порядку.
- Для каждого товара находим, для каких товаров он определяет скидку, проверяя необработанные товары с индексами слева, чья цена больше или равна текущей.
- Чтобы эффективно отслеживать эти необработанные товары, используем монотонный стек. Этот стек хранит индексы товаров, цены которых упорядочены по возрастанию. Это позволяет быстро находить и применять скидки.
Подход 🚀
- Создаём стек
discount_candidates, чтобы хранить индексы товаров, ожидающих применения скидки.
- Итерируем по массиву
prices:
- Пока верхний элемент стека соответствует условию скидки (
цена товара в стеке ≥ текущей цене), применяем скидку и удаляем элемент из стека.
Читать дальше →
На нашей новой задаче 2415. Reverse Odd Levels of Binary Tree есть повод продемонстировать продвинутые методы Rust работы с итераторами (std::iter::successors & std::iter::zip), а также "непристойную" работу c реф-каунт ячейками :(
📜 Описание задачи
Дано идеальное бинарное дерево. Требуется изменить порядок значений узлов на всех нечетных уровнях дерева.
Идеальное дерево — это дерево, где у каждого узла два потомка, а все листья находятся на одном уровне.
💡 Идея
Мы адаптируем BFS для обхода дерева по уровням. На каждом уровне проверяется, нужно ли инвертировать порядок значений (для нечетных уровней). С помощью вспомогательной функции формируются следующие уровни дерева.
📋 Подробности подхода
-
Вспомогательная функция
next_level:
- Формирует следующий уровень дерева, собирая всех левых и правых потомков текущих узлов.
-
Завершение обработки:
- Проверка, что текущий уровень является листовым, выполняется через условие
nodes[0].borrow().left.is_none().
- При достижении уровня листьев обработка завершается.
-
Обход уровней с помощью
std::iter::successors:
- Используется функциональный подход для последовательного формирования уровней дерева. Итератор автоматически останавливается при достижении листового уровня.
Читать дальше →
Описание задачи 📋
Дано неориентированное дерево с nn узлами, пронумерованными от 0 до n−1. Также даны:
- массив рёбер edges, где каждое ребро связывает два узла,
- массив значений values, где значение values[i] связано с узлом i,
- число k.
- гарантируется, что сумма всех значений values кратна k
Необходимо найти максимальное количество компонентов, на которые можно разделить дерево, удаляя рёбра, чтобы сумма значений в каждом компоненте делилась на k.
Идея 💡
Будем разбивать дерево на компоненты рекурсивно (DFS), начиная с произвольного узла.
Несложно показать, что родительская вершина должна быть в одной компененте со всеми дочерними, для которых сумма значений в соответствующем поддереве не делится на k.
Детали подхода 🚀
-
Построение графа:
- Представляем дерево в виде списка смежности для удобного обхода.
-
Обход дерева:
- Запускаем DFS от корня.
- Для каждого узла вычисляем остаток от суммы поддерева (
sum%k) и проверяем, можно ли выделить текущую часть как отдельный компонент.
Читать дальше →