Ссылка на задачу – 1718. Construct the Lexicographically Largest Valid Sequence.
📌 Условие задачи
Дано число n. Необходимо построить последовательность, удовлетворяющую следующим условиям:
- Число
1 встречается ровно один раз.
- Каждое число
i от 2 до n встречается ровно дважды.
- Для каждого числа
i > 1, два его вхождения в последовательность находятся на расстоянии ровно i.
- Среди всех возможных последовательностей требуется выбрать лексикографически наибольшую.
💡 Идея
Бэктрекинг — хороший способ решения данной задачи.
Чтобы получить лексикографически наибольшую последовательность, мы должны размещать сначала наибольшие числа.
🔄 Подробности метода
- Рекурсивно заполняем последовательность, начиная с первого свободного индекса.
- Используем массив
used, который отслеживает, какие числа уже размещены.
- Пропускаем занятые позиции.
- Проверяем возможность размещения числа заранее, прежде чем выполнять рекурсию.
Читать дальше →
ответить
Продолжаем череду задач на перебор - 1079. Letter Tile Possibilities.
📜 Описание задачи
У нас есть набор плиток, на каждой из которых напечатана одна буква, представленный в виде строки.
Необходимо подсчитать количество различных возможных непустых последовательностей букв, которые можно составить, используя плитки.
💡 Идея решения
- Будем использовать бэктрекинг.
- Чтобы избежать проверки на уникальность через
HashSet, сначала сортируем плитки, а затем группируем одинаковые плитки в сегменты.
- Далее, с помощью рекурсии, перебираем все возможные последовательности, гарантируя, что одинаковые плитки не будут использоваться более одного раза в одном наборе последовательностей.
🧑💻 Подробности подхода
- Сортировка плиток:
- Плитки сортируются для того, чтобы одинаковые плитки оказались рядом. Это позволяет нам эффективно группировать их в сегменты.
- Группировка плиток:
- Создаем массив сегментов, где каждый элемент представляет собой количество одинаковых плиток.
- Например, для строки
"AAB" сегменты будут равны [2, 1] (2 плитки "A" и 1 плитка "B").
- Бэктрекинг — для каждого сегмента мы:
- пытаемся использовать плитку (уменьшаем количество плиток в этом сегменте);
Читать дальше →
ответить
Очередная задача — 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).
⚙️ Детали подхода
Читать дальше →
ответить
Ссылка на задачу — 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 из этого двоичного представления, чтобы выбирать между двумя допустимыми символами при итеративной генерации каждого следующего символа конкретной счастливой строки. 🚀
🔍 Детали подхода
- Определяем количество возможных строк с фиксированным первым символом:
Читать дальше →
ответить
Ссылка на задачу — 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
ответить
Ссылка на задачу – 1261. Find Elements in a Contaminated Binary Tree.
📝 Описание задачи
Дано двоичное дерево, в котором:
- Корень всегда имеет значение
0.
- Для каждого узла со значением
x:
- Если есть левый потомок, то его значение
2 * x + 1.
- Если есть правый потомок, то его значение
2 * x + 2.
Значения всех узлов загрязнены (-1).
Нужно реализовать структуру FindElements, которая:
- Принимает корень «загрязнённого» дерева в конструкторе.
- Реализует
find(target) — метод, проверяющий существует ли узел с таким значением.
💡 Идея
Восстанавливать дерево не требуется!
Вместо этого мы вычисляем путь к узлу target, определяя его родителя и положение.
🔍 Детали подхода
- Поиск родителя (
parent):
Читать дальше →
ответить
