Кэш LRU

Спроектируйте структуру данных, которая реализует ограничения Least Recently Used (LRU) кэша.

Реализуйте класс LRUCache:

• LRUCache(int capacity) инициализирует LRU-кэш с положительным размером capacity (вместимость).
• int get(int key) возвращает значение по ключу key, если ключ существует в кэше. В противном случае возвращает -1.
• void put(int key, int value) обновляет значение ключа key, если он уже есть в кэше. В противном случае добавляет пару ключ-значение в кэш. Если после этой операции количество ключей превысит capacity, необходимо вытеснить (удалить) ключ, который использовался давнее всех остальных.

Пример 1:

Ограничения:

• 1 <= capacity <= 3000
• 0 <= key <= 104
• 0 <= value <= 105
• Будет выполнено не более 2 * 105 вызовов методов get и put.