LRU-кэш ---ПИСЕП--- Подробное руководство и реализация __PYTERM_0__ для решения проблемы «LRU Cache». ---ПИСЕП--- Спроектируйте структуру данных, которая соответствует ограничениям кэша «наименее недавно использованного» (LRU). Реализуйте класс LRUCache: - LRUCache(capacity: int) - Инициализировать кэш LRU с емкостью положительного размера. - get(key: int) -> int - Возвращает значение ключа, если ключ существует, в противном случае возвращает -1. — put(key: int, value: int) -> None — обновить значение ключа, если ключ существует. В противном случае добавьте пару ключ-значение в кеш. Если количество ключей превышает емкость, удалите ключ, который использовался реже всего. Каждая из функций get и put должна выполняться со средней временной сложностью O(1). Входные данные — это список операций и список аргументов. Реализуйте функцию __PYCODE_0__, которая возвращает список результатов (нет для конструктора и put). ---ПИСЕП--- 150 лучших интервью ---ПИСЕП--- Связанный список ---ПИСЕП--- Проблема «Кэша LRU» является ключевой проблемой в разделе «Связанный список». ---ПИСЕП--- Эта реализация фокусируется на логике простого уровня в __PYTERM_0__. ---ПИСЕП--- В предоставляемых нами решениях мы уделяем приоритетное внимание технической точности и читаемости кода. ---ПИСЕП--- Алгоритмическая инженерия ---ПИСЕП--- Соревновательное программирование ---ПИСЕП--- Технические оценки ---ПИСЕП--- Визуализация логического потока для LRU Cache. ---ПИСЕП--- Внимательно прочтите формулировку проблемы для LRU Cache. ---ПИСЕП--- Нарисуйте простое итеративное решение. ---ПИСЕП--- Ищите лишние вычисления. ---ПИСЕП--- Используйте хеширование или сортировку, чтобы ускорить процесс. ---ПИСЕП--- Очистите код для производственных стандартов. ---ПИСЕП--- Пустые входные структуры ---ПИСЕП--- Одноэлементные входы ---ПИСЕП--- Большие числовые границы ---ПИСЕП--- Объясните логику вашего подхода со связанным списком. ---ПИСЕП--- Обсудите крайние случаи, такие как нулевые или пустые входные данные. ---ПИСЕП--- Применяются стандартные свойства проблемы связанного списка. ---ПИСЕП--- Рассмотрите возможность использования структур данных, специфичных для связанных списков, таких как наборы или кучи. ---ПИСЕП--- Объединить K отсортированных списков ---ПИСЕП--- Подробное руководство и реализация __PYTERM_0__ для задачи «Объединить отсортированные списки K». ---ПИСЕП--- Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его. Связанные списки представлены в виде списков __PYTERM_1__. Реализуйте функцию __PYCODE_0__, которая возвращает объединенный отсортированный список. ---ПИСЕП--- 150 лучших интервью ---ПИСЕП--- Связанный список ---ПИСЕП--- Проблема «Объединить K отсортированных списков» — ключевая задача в разделе «Связанный список». ---ПИСЕП--- Эта реализация фокусируется на логике простого уровня в __PYTERM_0__. ---ПИСЕП--- В предоставляемых нами решениях мы уделяем приоритетное внимание технической точности и читаемости кода. ---ПИСЕП--- Алгоритмическая инженерия ---ПИСЕП--- Соревновательное программирование ---ПИСЕП--- Технические оценки ---ПИСЕП--- Визуализация логического потока для слияния отсортированных списков K. ---ПИСЕП--- Внимательно прочитайте постановку задачи для слияния отсортированных списков K. ---ПИСЕП--- Нарисуйте простое итеративное решение. ---ПИСЕП--- Ищите лишние вычисления. ---ПИСЕП--- Используйте хеширование или сортировку, чтобы ускорить процесс.
Detailed guide and Python implementation for the 'LRU Cache' problem.
1. Узнать
The 'LRU Cache' problem is a key challenge in the Linked List section.
This implementation focuses on easy-level logic in Python.
We prioritize technical accuracy and code readability in our provided solutions.
2. Real-World Applications
3. Visual Intuition
Visualizing the logic flow for LRU Cache.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Read the problem statement for LRU Cache carefully.
2. Formulate brute force
Draft a simple iterative solution.
3. Identify inefficiency
Look for redundant calculations.
4. Optimize search path
Use hashing or sorting to speed up the process.
5. Final Implementation
Clean up the code for production standards.
Постановка задачи
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
- LRUCache(capacity: int) - Initialize the LRU cache with positive size capacity.
- get(key: int) -> int - Return the value of the key if the key exists, otherwise return -1.
- put(key: int, value: int) -> None - Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity, evict the least recently used key.
The get and put functions must each run in O(1) average time complexity.
Input is a list of operations and a list of arguments. Implement a function lruCache(operations: list, arguments: list) -> list that returns a list of results (None for constructor and put).
- •1 <= capacity <= 3000
- •0 <= key <= 10000
- •0 <= value <= 100000
- •At most 200000 calls will be made to get and put
Примеры
["LRUCache","put","put","get","put","get","put","get","get","get"], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
[None,None,None,1,None,-1,None,-1,3,4]
Cache capacity is 2. put(1,1), put(2,2), get(1) returns 1. put(3,3) evicts key 2. get(2) returns -1 (evicted). put(4,4) evicts key 1. get(1) returns -1, get(3) returns 3, get(4) returns 4.
Need a Hint?
Edge Cases to Watch
- Empty input structures
- Single element inputs
- Large numerical bounds
Готовы решить?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Интервью: идеи и вариации
Разбивка анализа сложности
Почему время: Directly evaluates all possibilities.
Почему космос: Uses standard local memory.
Почему время: Optimized paths reduce total operations.
Почему космос: May trade memory for speed.
Оптимизированный код Python для решения
Оптимизированный код Python для решения
class DNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCacheOpt:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.left = DNode(0, 0)
self.right = DNode(0, 0)
self.left.next = self.right
self.right.prev = self.left
def _remove(self, node):
prev, nxt = node.prev, node.next
prev.next = nxt
nxt.prev = prev
def _insert(self, node):
prev, nxt = self.right.prev, self.right
prev.next = node
nxt.prev = node
node.prev = prev
node.next = nxt
def get(self, key: int) -> int:
if key in self.cache:
self._remove(self.cache[key])
self._insert(self.cache[key])
return self.cache[key].val
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
self.cache[key] = DNode(key, value)
self._insert(self.cache[key])
if len(self.cache) > self.cap:
lru = self.left.next
self._remove(lru)
del self.cache[lru.key]Код грубой силы (спойлер защищен)
Код грубой силы (спойлер защищен)
class LRUCacheBrute:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.usage = []
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.usage.remove(key)
self.usage.append(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.usage.remove(key)
elif len(self.cache) >= self.cap:
lru = self.usage.pop(0)
del self.cache[lru]
self.cache[key] = value
self.usage.append(key)Algorithm Pattern Checklist
When dealing with Linked List data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
Key Revision Notes
Standard Linked List problem properties apply.
Связанные вопросы
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Рекомендуемые ресурсы Python
Расширьте свои знания с помощью соответствующих интерактивных руководств, шпаргалок и сравнений кода.
Циклы Python
Узнайте, как использовать циклы Python для перебора данных. Освойте циклы for, while, прерывание, продолжение и лучшие практики работы с циклами с помощью интерактивных примеров.
Как отсортировать список в Python
Узнайте, как сортировать список в Python с помощью метода sort() и функции sorted(). Ознакомьтесь с примерами пользовательской сортировки ключей и обратного порядка.
Шпаргалка по строковым методам Python
Полное справочное руководство по манипулированию строками в Python. Мастер форматирования, поиска, разделения, замены и проверки свойств строк.
Python против JavaScript: какой язык программирования лучше?
Всестороннее сравнение Python и JavaScript. Изучите синтаксические различия, производительность, варианты использования (серверная и клиентская части) и примеры кодирования.