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