LRU Cache

Средняя№146фиктивная голова

Нужно сделать кэш не больше чем на capacity ключей. get(key) возвращает значение ключа или -1, если его нет. put(key, value) добавляет ключ или меняет его значение; если ключей стало слишком много, выбрасывается тот, которым пользовались давнее всех. Обе операции должны работать за O(1). Наши вызовы, capacity 2: put(4, 40), put(7, 70), put(4, 45), put(9, 90), get(7), get(4) — get(7) вернёт -1, get(4) вернёт 45.

146 LRU CacheРазбор · 1×

Пример: capacity 2; put(4, 40), put(7, 70), put(4, 45), put(9, 90), get(7), get(4). Узел показан как ключ:значение.

map—capacity 2
в спискеnodeпока вне спискавыброшен

LRUCache(2): кэш не больше чем на 2 ключа

01/56
сначала · назад · пуск · шаг
Скорость
1class LRUCache:
2 function init(capacity):
3 map = empty map // key → node
4 head = new node; tail = new node
5 head.next = tail; tail.prev = head
6 function get(key):
7 if key not in map:
8 return -1
9 node = map[key]
10 unlink(node)
11 addFront(node)
12 return node.val
13 function put(key, val):
14 if key in map: unlink(map[key])
15 node = new node(key, val)
16 map[key] = node
17 addFront(node)
18 if len(map) > capacity:
19 node = tail.prev
20 unlink(node)
21 remove node.key from map
22 function unlink(node):
23 node.prev.next = node.next
24 node.next.prev = node.prev
25 function addFront(node):
26 node.prev = head; node.next = head.next
27 head.next.prev = node; head.next = node
состояние
key
–
node
–
map
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Список держится в порядке использования: каждый get и put переносит свой узел сразу за head, поэтому узел прямо перед tail — всегда тот, которым пользовались давнее всех.
  2. Словарь даёт узел ключа за один шаг, а ссылки prev позволяют вынуть узел из середины двумя присваиваниями. Ничего не ищем, поэтому get и put — O(1).
  3. head и tail — фиктивные узлы: у узла всегда есть соседи с обеих сторон, поэтому вынуть единственный узел или вставить в пустой список можно без отдельного случая.

Сложность

Время O(1) на get и put: одно обращение к словарю и несколько ссылок. Память O(capacity): узел и запись в словаре на каждый ключ.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.