Сегодня чуток похулиганим и предоставим переоптимизированное решение для задачи 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 ответа
Сегодня на очереди задача 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.
Сложность алгоритма 📊
Читать дальше →
ответить
Новый день - новая задача 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
}
}
Сегодня разберём ещё одну простую задачу 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
}
}
Наступление зимы отметим разбором простой задачи 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
}
}
Задача на выходные - 2097. Valid Arrangement of Pairs
Описание задачи 📜
Нужно переставить заданные пары [starti,endi] так, чтобы получилось корректное расположение,
где для каждой пары i: endi−1=starti. Гарантируется, что такое расположение существует.
Обзор решения 🛠
Для решения задачи используется алгоритм Хирхольцера, который позволяет построить Эйлеров путь (или цикл) в ориентированном графе. Основная идея — удалять рёбра во время обхода, что упрощает структуру данных и предотвращает повторное использование рёбер.
Ключевые шаги 🚀
-
Построение графа:
- Граф представляется в виде списка смежности (
HashMap<i32, Vec<i32>>), где каждая вершина хранит список своих исходящих рёбер.
- Параллельно вычисляются разницы степеней вершин (входящих и исходящих рёбер) для определения начальной вершины пути.
-
Поиск начальной вершины:
- Начальная вершина — это вершина с положительным балансом исходящих рёбер. Если таких нет, берётся любая вершина из входных данных.
-
Итеративный DFS с удалением рёбер:
- Вместо стандартного рекурсивного DFS используется итеративный подход с явным стеком. Это повышает эффективность памяти и скорость.
- При посещении вершины рёбра удаляются из списка смежности, что гарантирует, что каждое ребро используется ровно один раз.
Читать дальше →
ответить
Сегодня нам предстоит решить задачу 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.
Читать дальше →
ответить
Очередная задача: 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.
Читать дальше →
ответить
Сегодня мы решаем задачу 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 для обновления кратчайших расстояний до всех достижимых городов.
Читать дальше →
ответить
Сегодня мы решаем задачу 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
}
}
}
Начну-ка я минипроект по разбору ежедневных задач с LeetCode.
Решения будут на раст, ибо: модно, стильно, молодёжно!
Rust идеально подходит для задач с LeetCode благодаря высокой производительности, безопасному управлению памятью и удобным инструментам для работы с данными, обеспечивая компактный и надёжный код.
Надеюсь, такой контент будет полезен аудитории.
ответить
Страница
1
2
3
4
5
