Имплементировать префиксное дерево (Trie)

Иногда, на алгоритмических секциях дают задачки с хитрыми формулировками, иногда — задачи, для которых нужно придумать хитрый алгоритм.

Но, время от времени, попадаются задачи где нужно просто имплементировать ту или иную структуру данных. Конечно же, обычно интервьюер таким образом пытается понять, знаете ли вы какую-нибудь хитрую (или не очень) структуру данных, которую так хорошо знает он сам, и сумеете ли вы реализовать ее с закрытыми глазами.

Конечно же, я большой противник таких подходов — структур данных превиликое множество, а знать их и помнить все невозможно.

Что делать, если вам попалась такая задача и вы не знаете что от вас просят? Вспомните, что софт скилы не менее важны чем харды и попросите интервьюера рассказать, какую проблему должна решать структура, какие методы должны быть имплементированы, какие требование к скорости/памяти предъявляются и так далее.

Если интервьер адекватный, он обязательно поможет вам понять, что от вас требуется.

Сегодняшняя наша задача — имплементировать префиксное дерево.

Сложность: 🟠 Cредняя

ℹ️ Описание

Необходимо написать реализацию структуры данных «Префиксное дерево». Данная структура должна имплементировать следующие методы:

▶️ Insert(word string) —сохранение слова в дерево

▶️ Search(word string) bool —проверка наличия слова в дереве. Важно помнить, что данный метод должен отвечать true только в случае, если найдено конечное слово (а не префикс)

▶️ StartsWith(prefix string) bool — проверка наличия префикса в дереве. В отличии от предыдущего метода true вернется как в случае нахождения полноценного слова, так и при наличии префикса.

⚠️ Ограничения

🔹Длина одного слова не превышает 2000 символов
🔹Слова могут состоять только из латинских букв в нижнем регистре
🔹Суммарное максимальное кол-во вызовов всех методов - 30000

Пример

trie := Constructor()

trie.insert("apple")
trie.search("apple") // return True
trie.search("app") // return False
trie.startsWith("app") // return True
trie.insert("app")
trie.search("app") // return True


✅ Решение

Суть префиксного дерева — слово раскладывается посимвольно. Каждый символ будет нодой дерева. Связи между нодами соответствуют последовательности симолов в строке.

Таким образом, слово «apple» должно в нашей структуре превратиться в «ветку» a -> p -> p -> l -> e.

Для того, чтобы реализовать дерево, нам нужно описать структуру ноды. В нашем случае она будет очень простой.

type Trie struct {
    children   map[rune]*Trie
    isFullWord bool
}

children — набор дочерних нод.

isFullWord — признак того, является ли текущая нода конечной буквой слова (нам нужен этот флаг, так как одно слово может полностью являться префиксом для более длинного слова).

Более подробное описание структуры можно найти по ссылке.

Для реализации метода вставки нам потребуется вспомогательный рекурсивный метод. На каждой итерации рекурсии мы будем отрезать по одной букве слева, превращая ее в префиксную ноду. В ноде последней буквы мы проставим флаг isFullWord в true.

Методы Search и StartsWith отличаются только тем, что в последней найденной ноде нам нужно проверить флаг isFullWord (для Search он должен оказаться true, а для StartsWith значение флага не имеет никакого значения). Поэтому для реализации обоих методов нам понадобится один вспомогательный метод traverse, который сможет рекурсивно обходить дерево вглубь. В этом методе мы будем отрезать по одной букве слева и искать ее в мапе children текущей ноды. Если такой ключ существует — переходить к найденной дочерней ноде.

Посмотреть подробное решение в блоге

🅾️ Оценка сложности

По времени

Функции Insert, Search и StartsWith используют рекурсивные вспомогательные функции insert и traverse. У обеих функций глубина рекурсии равна длине префикса.

Таким образом, все 3 функции имеют сложность O(n), где n - длина префикса.

По памяти

Для работы функций не используются промежуточные структуры, зависящие от длины префикса. Сложность по памяти O(1).

#tries #medium

Столкновение астероидов

Привет, друзья. Помните задачку на валидацию скобочной последовательности? Она считается очень легкой и на leetcode она в разряде easy задач. Я же никогда не считал, что ее по сложности можно сравнить с каким-нибудь слиянием отсортированных массивов. Львиная доля ее легкости заключается в мейнстримности этой задачи - едва ли не каждый знает каноническое решение через стек. А между тем, это далеко не единственная задача, которую можно оптимально решить через эту структуру данных. И, если попросить кандидата решить немного другую задачу с похожей идеей решения, то вполне можно вогнать человека в ступор :). Как всегда, дело в умении распознать класс задачи, а вот применить паттерн решения уже не составляет труда.

Поэтому, сегодня мы разберем задачу о столкновении астероидов.

P.S. Если быть честным, у меня ушло около 40 минут на реализацию и отладку решения через 2 индекса, прежде чем я догадался воспользоваться стеком. Решение через стек вышло сильно лаконичнее и быстрее в реализации 🙂

Сложность: 🟠 Средняя

ℹ️ Описание

Напишите функцию, которая будет рассчитывать результаты столкновения астероидов.

Входные данные: массив целых ненулевых чисел. Каждое число обозначает массу астероида, знак - направление движения.

Выходные данные: массив целых ненулевых чисел. Массив будет описывать множество астероидов, их массу и направление, после того, как все астероиды, которые могут столкнуться, столкнутся.

Все астероиды движутся с одинаковой скоростью. Таким образом, астероиды, летящие в одном направлении никогда не столкнутся друг с другом.

В отличие от реальной жизни, при столкновении масса и направление движение астероидов после никак не изменяются. Меньший из двух полностью уничтожается, больший продолжает лететь в прежнем направлении, не меняя массу.

⚠️ Ограничения

- Количество астероидов (длина входного массива) находится в диапазоне от 2 до 10000
- Масса астероида лежит в диапазоне от 1 до 1000 (знак влияет только на направление движения)
- Астероидов с нулевой массой не существует

1️⃣Пример

Входящие данные

[]int{5,10,-5}

Ответ

[]int{5,10}

Пояснение

Первые два астероида движутся вправо, последний - влево. В результате, второй и третий астероид должны столкнуться. Второй астероид имеет большую массу, поэтому он полностью уничтожит третий.

2️⃣ Пример

Входящие данные

[]int{8,-8}

Ответ

[]int{}

Пояснение

Астероиды движутся навстречу друг другу и имеют одинаковую массу. В результате оба астероида будут уничтожены.


3️⃣ Пример

Входящие данные

[]int{10,2,-5}

Ответ

[]int{10}

Пояснение

Первые два астероида движутся вправо, последний - влево. В результате, третий астероид уничтожит второй. и продолжит движение влево. После этого столкнуться первый и третий астероиды, а так как первый имеет большую массу, он уничтожит третий.


✅ Решение

Посмотреть подробное объяснение решения

#stack #medium

Дневная температура

Всем привет!
Продолжаем закреплять знание структуры данных «стек» и умение определять этот паттерн. Мы уже разбирали самую мейнстримную задачу на валидацию скобочной последовательности. На прошлой неделе мы моделировали столкновение астероидов. Сегодня будем считать количество дней до ближайшего более теплого дня 🙂

Сложность: 🟠 Средняя

ℹ️ Описание

Напишите функцию, которая будет рассчитывать количество дней между текущим и днем с большей температурой.

Входные данные: Массив целых неотрицательных чисел. Каждое число в массиве, это температура в соответствующий день.

Выходные данные: Массив целых неотрицательных чисел. Каждое число в массиве, это количество дней от i'го дня до дня с большей температурой.

⚠️ Ограничения

- Количество дней (длина входного массива) находится в диапазоне от 1 до 100000
- Температура для каждого дня находится в диапазоне от 30 до 100

1️⃣Пример

Входящие данные

[73, 74, 75, 71, 69, 72, 76, 73]

Ответ

[1, 1, 4, 2, 1, 1, 0, 0]

2️⃣ Пример

Входящие данные

[30, 40, 50, 60]

Ответ

[1, 1, 1, 0]

3️⃣ Пример

Входящие данные

[0, 60, 90]

Ответ

[1, 1, 0]

✅ Решение

Посмотреть подробное объяснение решения

#stack #medium

Можно ли посадить цветы?

Всем привет!
Долго думал, какую задачку запостить перед новым годом 🙂 Сперва хотел найти что-нибудь интересное и хитрое, но в итоге решил, что думать перед новогодними каникулами не хочется. Поэтому можно просто расслабиться и решить что-нибудь простое и тривиальное.

P.S. Всех с наступающим и счастливого Нового Года!
Мы тоже уйдем на небольшие каникулы и вернемся к каналу после 9го января. Оставайтесь с нами, в новом году мы продолжим решать алгоритмические задачки, а также попробуем запустить еще один или несколько новых форматов 🙂

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дан целочисленный массив flowerbed и число n.

Массив описывает цветочную клумбу, каждый элемент массива может принимать значение 1 (на этом месте посажен цветок) и 0 (пустое место). Существует ограничение - цветы не могут быть посажены на соседних местах.

Необходимо написать функцию, которая определит, можем ли мы посадить в нашу клумбу n новых цветов.

⚠️ Ограничения

- Длина клумбы лежит в диапазоне от 1 до 20000
- Значение каждого элемента массива может равняться либо 0, либо 1
- В исходном массиве не может быть двух цветков на соседних местах (то есть, исходно мы имеем валидный массив)
- n лежит в диапазоне от 0 до длины массива flowerbed (то есть, не превышает размер клумбы)

1️⃣Пример

Входящие данные

flowerbed = [1,0,0,0,1], n = 1

Ответ

true

2️⃣ Пример

Входящие данные

[1,0,0,0,1], n = 2

Ответ

false

✅ Решение

Посмотреть подробное объяснение решения

#array #easy

Неповторяющееся число

Привет, друзья!

Новогодние праздники прошли и пришла пора возвращаться к задачам. Я понимаю, что эта рабочая почти неделя многим далась тяжело, поэтому мы начнем с простой задачи, но на ту тему, которую еще не разбирали. Будет интересно!

Сложность: 🟢 Легкая

ℹ️ Описание

Дан непустой массив целых чисел nums, каждый элемент в котором появляется дважды, кроме одного. Найдите этот уникальный элемент.

Вы должны реализовать решение с линейной сложностью по времени и константной по памяти.

⚠️ Ограничения

- В массиве может быть от 1 до 30 000 элементов
- Каждый элемент массива имеет значение в диапазоне от -30 000 до 30 000
- Каждый элемент массива встречается дважды, за исключением одного элемента

1️⃣ Пример

Входящие данные

[2, 2, 1]

Ответ

1

2️⃣ Пример

Входящие данные

[4, 1, 2, 1, 2]

Ответ

4

✅ Решение

Я знаю, что первая идея, которая может прийти вам в голову — это реализовать классический обход массива с подсчетом частоты каждого числа. Для этого для каждого числа в хеш-таблице мы будем хранить пару, в которой ключом является само число, а значением — сколько раз оно встречается в массиве. В конце нужно будет лишь просмотреть всю таблицу и выбрать то число, у которого счетчик равен 1.

В результате мы получим такое решиние.

export const singleNumberMap = (nums: number[]): number => {
    const countMap: Record<number, number> = {}

    nums.forEach((num) => {
        const curr = countMap[num] ?? 0
        countMap[num] = curr + 1
    })

    const entries = Object.entries(countMap)

    for (let i = 0; i < entries.length; i++) {
        const [num, count] = entries[i]
        if (count === 1) {
            return Number(num)
        }
    }

    return 0
}

Однако, такое решение нам не подойдет, потому что использование хеш-таблицы для хранения частот приведет к тому, что у нас будет линейная сложность по памяти.

На самом деле задача очень легкая, но надо знать хитрость, а именно — как работает операция XOR.

Посмотреть разбор решения в блоге

#array #easy #bit_manipulation

Разворот гласных в строке

Всем привет. Сегодня пятница и мы разбираем новую задачу.

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дана строка s. Напишите функцию, которая развернёт в ней все гласные и вернет новую строку в качестве результата.

В строке могут встречаться следующие гласные: a, e, i, o, и u как в верхнем, так и в нижнем регистре.

⚠️ Ограничения

— В строке может быть от 1 до 3 * 10^5 символов
— Строка состоит из печатных ASCII символов
— Символы могут быть в верхнем и нижнем регистре

1️⃣ Пример

Входящие данные

hello

Ответ

holle

2️⃣ Пример

Входящие данные

algorithmics

Ответ

ilgirothmacs

3️⃣ Пример

Входящие данные

ab

Ответ

ab

✅ Решение

В первую очередь нам нужно уметь быстро за константное время определять, является ли конкретная буква гласной. Для этого мы заведем структуру, в которой перечислим все возможные буквы в обоих регистрах.

const dict = new Set(['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'])

Мы перечисляем возможные буквы сразу в двух регистрах, чтобы каждый раз во время вычислений не приводить очередной символ из строки к нижнему регистру для сравнения. Так мы немного экономим время.

Теперь нужно реализовать разворот гласных. Для этого заведем два указателя:

— leftIdx равен нулю
— rightIdx равен индексу последнего символа встроке

Чтобы правильно реализовать разворот, мы будем поочередно двигать левый и правый индексы, пока каждый из них не будет указывать на гласную букву. Как только это произойдет, поменяем буквы местами и будем повторять этот алгоритм до тех пор, пока leftIdx < rightIdx.

Посмотреть реализацию в блоге

#strings #easy

Непересекающиеся интервалы

В эту пятницу у нас с вами очередная задача. Приготовьтесь, объяснение ее решения не самое простое.

Сложность: 🟡 Средняя

ℹ️ Описание

Дан массив интервалов intervals, где intervals[i] = [start, end]. Напишите функцию, которая возвращает минимальное количество интервалов, которое вам нужно удалить, чтобы остальные интервалы не пересекались.

⚠️ Ограничения

— Длина массива находится в диапазоне от 1 до 10^5
— Каждый элемент массива также является массивом из двух элементов
— Значения границ интервалов находятся в диапазоне от -5 * 10^4 до 5 * 10^4
— Нижняя граница интервала всегда меньше верхней

1️⃣ Пример

Входящие данные

[[1,2],[2,3],[3,4],[1,3]]

Ответ

1

2️⃣ Пример

Входящие данные

[[1,2],[1,2],[1,2]]

Ответ

2

3️⃣ Пример

Входящие данные

[[1,2],[2,3]]

Ответ

0

✅ Решение

Рассмотрим два интервала с самым ранним временем окончания. Допустим, более раннее время окончания — x, а более позднее — y, то есть х < у.

Если мы можем сохранить только один интервал, следует ли нам выбрать тот, который заканчивается на «x» или тот, который оканчивается на «y»? Чтобы избежать дублирования, мы всегда должны жадно выбирать интервал с более ранним временем окончания «x». Логику, стоящую за этим, можно описать следующим образом:

— Мы выбираем либо x, либо y. Назовем наш выбор k.
— Чтобы избежать пересечения, время начала следующего интервала, который мы выбираем, должно быть больше или равно k.
— Мы хотим максимизировать интервалы, которые мы используем (без пересечения), поэтому мы хотим максимизировать выбор для следующего интервала.
— Поскольку время начала следующего интервала должно быть больше или равно k, большее значение k никогда не сможет дать нам больше выбора, чем меньшее значение k.
— Таким образом, мы должны попытаться минимизировать k. Следовательно, нам всегда следует жадно выбирать x, поскольку x < y.

В общем, k равно времени окончания самого последнего сохраненного нами интервала.

Решение задачи мы начинаем с сортировки интервалов по времени окончания, чтобы мы могли обрабатывать их по порядку.
Поскольку мы отсортировали интервалы по времени окончания, «y» должно быть больше «k». Это дает нам два возможных варианта:

— Вариант 1, x >= k: мы можем смело использовать этот интервал, поскольку он не приведет к пересечению.
— Вариант 2, x < k: использование этого интервала приведет к пересечению. Как мы установили ранее, нам всегда следует брать интервалы с более ранним временем окончания. Поскольку y > k, мы должны удалить текущий интервал.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

Для того чтобы найти ответ, нам достаточно один раз пройтись по исходному массиву со сложностью O(n). Однако предварительно мы еще делаем сортировку массива, сложность которой скорее всего равна O(n⋅logn).

Поэтому итоговая сложность по времени равна O(n⋅logn).

По памяти

Мы не создаем переменных, зависящих от длины входных данных, однако для сортировки также требуется выделение памяти. В разных языках используются разные алгоритмы, поэтому сложность по памяти будет варьироваться от O(logn) до O(n).

#arrays #medium

Плюс один

Для решения сегодняшней задачи мы с вами вспомним школьную программу, а именно — как складывать числа столбиком.

Сложность: 🟢 Легкая

ℹ️ Описание

Дано большое целое число, представленное в виде целочисленного массива digits, где digits[i] — это i-я цифра целого числа. Цифры упорядочены от наиболее значимого к наименее значимому, слева направо. Число не содержит ведущих нулей.
Увеличьте число на единицу и верните полученный массив цифр.

⚠️ Ограничения

— В массиве цифр может быть от 1 до 100 элементов
— В массиве содержатся только цифры от 0 до 9
— Число не содержит ведущих нулей

1️⃣ Пример

Входящие данные

Ответ

2️⃣ Пример

Входящие данные

Ответ

3️⃣ Пример

Входящие данные

Ответ

✅ Решение

Чтобы решить задачу, нужно реализовать подход со сложением чисел в столбик.
Каждая цифра в массиве представляет собой один разряд числа. Сначала нужно прибавить к младшему разряду (крайнему справа) единицу согласно условиям задачи, а потом следовать простому алгоритму.

1. Если сумма меньше 10, то вместо текущего разряда нужно записать эту сумму.

2. Если сумма больше 10, то вместо текущего разряда нужно записать остаток от деления суммы на 10, а к следующему разряду прибавить единицу. Для всех последующих разрядов нужно повторить эти же действия.

3. Если мы обрабатываем старший разряд (крайний слева) и сумма больше 10, то в текущий разряд мы добавляем остаток от деления суммы на 10 и добавляем еще один разряд, в который записываем единицу.

Перебирать исходный массив будем справа налево, добавляя результат вычислений для каждого разряда в конец результирующего массива. В результате мы получим инвертированный массив, поэтому в конце остается только развернуть его относительно центра.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

O(n) — так как мы дважды итерируемся по всему массиву.

По памяти

O(n) — так как мы выделяем память для хранения результирующего массива.

#arrays #easy #math

Разворот слов в строке

Подобные задачи чаще всего попадаются на собеседованиях — на первый взгляд задача кажется очень простой, особенно если воспользоваться встроенными функциями языка - trim, split и так далее - задача решается в несколько строчек кода.
Но, обычно, в таких задачах интервьеры просят НЕ использовать эти функции и реализовать все самим. И в этот момент частенько «зависаешь» на реализации.

Сложность: 🟡 Средняя

ℹ️ Описание

Необходимо написать функцию, которая будет переставлять слова в строке в обратном направлении. Слова в строке разделены пробелами, пробелов между слов может быть несколько, а также пробелы могут стоять в начале и конце исходной строки.

В итоговой строке слова должны быть разделены одним пробелом, а также не должно быть пробелов в начале и конце строки.

⚠️ Ограничения

— Длина строки может быть в диапазоне от 1 до 10000
— Строка содержит только буквы латинского алфавита, числа и пробелы.
— В каждой строке есть как минимум одно слово


1️⃣ Пример

Входящие данные

«the sky is blue»

Ответ

«blue is sky the»

2️⃣ Пример

Входящие данные

« hello world »

Ответ

«world hello»

3️⃣ Пример

Входящие данные

«a good  example»

Ответ

«example good a»

✅ Решение

Данную задачу можно решить легким трюком: ответ мы получим, если избавимся от лишних пробелов, после перевернем каждое слово в строке и в конце перевернем полностью всю строку. Давайте рассмотрим задачу на примере

«a good  example».

1. Удаляем лишние пробелы внутри строки и получаем строку

«a good example»

2. Далее переворачиваем каждое слово внутри строки и получаем строку

«a doog elpmaxe»

3. Последним шагом переворачиваем всю строку и получаем требуемый результат

«example good a»

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

O(n) — так как мы несколько раз итерируемся по всей строке.

По памяти

O(n) — так как мы выделяем память для работы с новой строкой.

#strings #medium

Декодирование строки

Сложность: 🟡 Средняя

ℹ️ Описание

Вам дана закодированная строка, верните ее декодированную версию.

В строке используется следующее правило кодирования: k[encoded_string], означает что закодированная внутри квадратных скобок строка должна повторяться ровно k раз. Обратите внимание, что k гарантированно является положительным целым числом.

При этом входная строка всегда гарантированно валидная, то есть в ней нет лишних пробелов и квадратные скобки имеют правильную форму. Кроме того, цифры в строке предназначены только для повторяющихся чисел k. Например, не будет ввода типа 3a или 2[4].

Обратите внимание на то, что закодированные строки могут вкладываться друг в друга.

⚠️ Ограничения

— Длина входной строки находится в диапазоне от 1 до 30
— Входная строка содержит только латинские буквы в нижнем регистре, цифры и квадратные скобки
— Входная строка всегда валидная
— Значения k находятся в диапазоне от 1 до 300
— Длина результирующей строки не превышает 10^5


1️⃣ Пример

Входящие данные

"3[a]2[bc]"

Ответ

"aaabcbc"

2️⃣ Пример

Входящие данные

"3[a2[c]]"

Ответ

"accaccacc"

3️⃣ Пример

Входящие данные

"2[abc]3[cd]ef"

Ответ

 "abcabccdcdcdef"

✅ Решение

Эту задачу можно решить рекурсивным способом. Для этого определим следующий алгоритм.

1. Создаем результирующую пустую строку, которая будет использоваться для накопления декодированного результата.

2. Далее перебираем строку посимвольно и проверяем следующие условия:
- Если текущий символ является буквой (от ‘a’ до ‘z’), добавляем его в результат res и переходим к следующему символу.
- Если встречается цифра, это означает начало закодированного блока. Число перед [ (количество повторений) считывается посимвольно. Так как k может быть многозначным числом, используется накопление count в цикле, где каждая новая цифра добавляется к count с учетом ее разрядности (умножение на 10).

3. После определения count и нахождения открывающей скобки [, алгоритм ищет соответствующую закрывающую скобку ]. Это делается с помощью счетчика bracket, который увеличивается при нахождении [ и уменьшается при нахождении ], позволяя обрабатывать вложенные скобки.

4. Как только найдена соответствующая закрывающая скобка, вырезается подстрока между [ и ] и для нее рекурсивно вызывается функция decodeString. Результат этого вызова повторяется count раз и добавляется к итоговому результату res.

5. Индекс i устанавливается на позицию закрывающей скобки, чтобы продолжить обход строки после обработанного блока.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

O(maxk * n), где maxk — максимальное значение k, а n — длина данной строки s.

По памяти

O(n) — это пространство, используемое для хранения внутреннего стека вызовов для рекурсии. Поскольку мы рекурсивно декодируем каждый вложенный шаблон, максимальная глубина стека рекурсивных вызовов не будет превышать n.

#strings #medium

Dota2 Senate

Данная задача относится к моему «любимому» типу — попробуй пойми что от тебя хотят.

Первая сложность задачи не в поиске самого решения, а в попытках сократить контекст и описания с половины экрана до нескольких строчек, убирая весь лор про Dota2, сенаторов и регламенты проведения голосований.
Безусловно, в реальных условиях так часто и бывает — вам приносят бизнес задачу/проблему, которую вы должны решить, а не готовое ТЗ, где все структурировано расписано на понятном вам языке. Но для задач на собеседовании это перебор. Время сильно ограничено, вы стрессуете и вместо того, чтобы думать над задачей - пытаетесь продраться через витиеватое описание.

Сложность: 🟡 Средняя

ℹ️ Описание

В мире Dota2 существует 2 партии Radiant и Dire.
Для того чтобы внести изменение в игру Dota2 необходимо провести голосование сената, каждый член которого принадлежит одной из двух партий.

Голосование идет раундами, в каждом раунде по очереди опрашивается каждый сенатор.
Сенатор может выполнить одно из двух действий:
- лишить следующего сенатора из противоположной партии права голоса;
- объявить победу своей партии, если не осталось сенаторов с правом голоса из противоположной партии.
Раунд начинается с крайнего левого сенатора.

Напишите функцию, которая будет рассчитывать результаты голосования сената.

⚠️ Ограничения

- Количество сенаторов (длина входящей строки) находится в диапазоне от 1 до 10000
- Входящая строка состоит из символов R и D


1️⃣ Пример

Входящие данные

RD

Ответ

Radiant

2️⃣ Пример

Входящие данные

RDD

Ответ

Dire

✅ Решение

На первый взгляд задача может решиться простым сравнением количества сенаторов из каждой партии.
На самом деле такое решение будет не верно, так как не учитывает порядок голосования. Это легко понять на примере RDRDRDRDRDDD.

Правильный подход для решения этой задачи — воспользоваться структурой данных «очередь», поместив в нее сенаторов в заданом порядке.
Тогда весь процесс сведется к двум действиям:
- Забрать из начала очереди сенатора, а после того как тот совершит ход (лешит права голоса ближайшего сенатора из противоположной партии), помещать его в конец очереди.
- Удалить из очереди сенаторов без права голоса.

Итоговый ответ мы получим, когда в очереди останутся представители только одной партии.

Посмотреть реализацию и подробный разбор примера в блоге

🅾️ Оценка сложности

По времени

O(n) — так как нам придется несколько раз проитерироваться по очереди.

По памяти

O(n) — так как мы выделяем память для работы с очередью.

#queue #medium

Самый низкий общий предок двоичного дерева

Сложность: 🟡 Средняя

ℹ️ Описание

Вам дано двоичное дерево. Найдите наименьшего общего предка (LCA) двух заданных узлов в дереве.

Согласно определению LCA в Википедии: «Наименьший общий предок определяется между двумя узлами p и q как самый нижний узел в дереве T, который имеет как p, так и q в качестве потомков (где мы позволяем узлу быть потомком самого себя).»

⚠️ Ограничения

— Количество узлов в дереве находится в диапазоне от 2 до 10^5.
— Значения каждого узла в дереве находятся в диапазоне от -10^9 до 10^9.
— Значения всех узлов в дереве уникальны.
— p != q.
— p и q всегда существуют в дереве.


1️⃣ Пример

Входные параметры: дерево выше, p = 5, q = 1.

Ответ: 3

Объяснение: LCA узлов 5 и 1 равен 3.

2️⃣ Пример

Входные параметры: дерево выше, p = 5, q = 4.

Ответ: 5

Объяснение: LCA узлов 5 и 4 равен 5, поскольку узел может быть потомком самого себя согласно определению LCA.


✅ Решение

Решение этой задачи достаточно интуитивно. Сначала мы пройдем по дереву вглубь. В тот момент, когда встретится любой из узлов p или q, вернем логический флаг. Флаг помогает определить, нашли ли мы нужные узлы на каком-либо из путей. Тогда наименьшим общим предком будет узел, для которого обе рекурсии поддерева возвращают флаг true. Это также может быть узел, который сам является одним из узлов p или q и для которого одна из рекурсий поддерева возвращает флаг true.

Для реализации будем использовать рекурсивный подход с замыканием для хранения переменной lca.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

O(n) — так как в худшем случае нам нужно посетить все n узлов в дереве.

По памяти

O(n) — так как максимальный объем пространства, используемого стеком рекурсии, будет равен n.

#tries #medium

Угадай число

Сегодня мы рассмотрим вместе с вами еще одну классическую задачу из учебников.

Сложность: 🟢 Легкая

ℹ️ Описание

Мы играем в игру, где вы должны угадать загаданное число.
Игра заключается в следующем.

— Я выбираю число от 1 до n.
— Вы должны угадать, какое число я выбрал.
— Каждый раз, когда вы угадаете неправильно, я скажу вам, больше или меньше выбранное мной число, чем ваше предположение.

Вы можете использовать предоставленный метод guess для проверки догадки со следующей сигнатурой.

int guess(int num)

Метод возвращает следующие результаты:

— -1 если ваша догадка больше, чем выбранное мной число;
— 1 если ваша догадка меньше выбранного мной числа;
— 0 если ваша догадка равна выбранному мною числу.

Угадайте число, которое я загадал.

⚠️ Ограничения

Загадываемое число всегда находится в диапазоне от 1 до 2^31 - 1

1️⃣ Пример

Исходные данные: n = 10, загадано число 6

Ответ: 6

2️⃣ Пример

Исходные данные: n = 1, загадано число 1

Ответ: 1

3️⃣ Пример

Исходные данные: n = 2, загадано число 1

Ответ: 1

✅ Решение

Это классическая задача, которая решается при помощи бинарного поиска.

Нам нужно итеративно выполнять несколько шагов.

1. Найти крайнюю левую и правую границы интервала, то есть 1 и n соответственно.
2. Найти середину этого интервала и проверить полученное число:
— если полученное число больше загаданного, то правую границу нужно сместить на mid - 1;
— если полученное число меньше загаданного, то левую границу нужно сместить на mid + 1;
— если полученное число равно загаданному, то мы нашли ответ.

Этот алгоритм нужно повторять до тех пор, пока мы не найдем ответ или пока левая и правая границы не пересекутся.

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

O(log n) так как мы перебираем диапазон чисел бинарным поиском.

По памяти

0(1) так как мы не выделяем дополнительной памяти.

#binary_search