Всем привет!
Мы решили попробовать разбавить легкие и средние задачи — сложными 🙂
На самом деле эта задача лежала у меня в черновиках довольно долго. Настолько, что я успел несколько раз забыть как работает куча, а также за это время мы успели завести этот канал и несколько раз обновить блог (кстати, зацените новый формат. Кажется, стало немного симпатичнее).
Итак, задача по реализации модифицированного стека: который позволяет сперва доставать наиболее частотные элементы, а в случае наличия групп элементов с одинаковой частотой - работать как классический стек между этими группами.
На самом деле, наиболее приближенная задача из практических — Priority queue. Только в нашем случае вместо приоритетов — частоты, а вместо алгоритма FIFO - LIFO.
И несмотря на то, что в описании стек, одной из наиболее оптимальных структур данных для реализации будет куча (хотя, буду честен, по началу я достаточно много времени потратил на попытки модифицировать классический стек).
Сложность: 🤬 Сложная
ℹ️ Описание
Необходимо реализовать структуру данных, которая позволит сохранять и доставать целочисленные элементы. Для этого необходимо реализовать 3 функции:
1.
Constructor() FreqStack конструктор, инициализирующий структуры данных.2.
FreqStack.Push(val int) метод структуры данных, позволяющий сохранить целочисленный элемент внутрь структуры данных FreqStack3.
FreqStack.Pop() int метод структуры данных, удаляющий и возвращающий элемент из структуры данных. Сперва извлекаются наиболее частотные элементы. При наличии групп эллементов, имеющих одинаковую частоту, извлекать элементы из групп с одинаковой частотой по принципу стека (LIFO)⚠️ Ограничения
— Добавляемые/извлекаемые элементы лежат в диапазоне от 0 до 1 000 000 000
— Максимальное количество вызовов функций Push и Pop - 20 000
— Гарантируется, что перед вызовом функции Pop в FreqStack будет как минимум один элемент
1️⃣ Пример
stack := Constructor()
stack.Push(5)
stack.Push(7)
stack.Push(5)
stack.Push(7)
stack.Push(4)
stack.Push(5)
Out:
stack.Pop() // 5
stack.Pop() // 7
stack.Pop() // 5
stack.Pop() // 4
Пояснение
— Первым извлекается элемент 5, так как он самый частотный в стеке. При этом извлекается та 5, которая была добавлена последней (по принципу стека)
— Вторым извлекается элемент 7, так как в стеке оба элемента 5 и 7 встречаются по 2 раза, но последняя 7 была добавлена позже, чем последняя 5 (5, которую мы добавили последним Push'ом мы извлекли первым вызовом Pop)
— Третьим элементом извлекается элемент 5, так как теперь это самый частотный элемент в стеке
— Четвертым извлекается элемент 4, так как теперь в стеке все элементы имеют одинаковую частоту (каждый элемент встречается один раз), а элемент 4 был добавлен в стек последним
✅ Решение
Как я говорил ранее, для решения задачи нам придется вспомнить как работает куча. Так как куча по своей сути древовидная структура — мы можем реализовать ее через обычный массив.
Посмотреть реализацию и объяснения в блоге.
#heap #hard