/
Krisp
/
FBPreposit
Обзор
Документация
Войти
/
Krisp
/
FBPreposit
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
LRU_cache_update
86 строк
2 KB
Krisp
create LRU_cache_update
07 июн 2025, 13:24
07 июн 2025, 13:24
025edcf
Код
Авторство
О чём код?
class Node: def __init__(self, key: int, value: int): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.capacity = capacity self.cache = {} self.head = Node(0, 0) self.tail = Node(0, 0) self.head.next = self.tail self.tail.prev = self.head def _detach(self, node: Node): node.prev.next = node.next node.next.prev = node.prev def _insert_after_head(self, node: Node): node.next = self.head.next node.prev = self.head self.head.next.prev = node self.head.next = node def get(self, key: int) -> int: if key in self.cache: node = self.cache[key] self._detach(node) self._insert_after_head(node) return node.value return -1 def put(self, key: int, value: int) -> None: if key in self.cache: node = self.cache[key] node.value = value self._detach(node) self._insert_after_head(node) else: if len(self.cache) == self.capacity: old = self.tail.prev self._detach(old) del self.cache[old.key] node = Node(key, value) self.cache[key] = node self._insert_after_head(node) lru = LRUCache(3) lru.put(1, 10) lru.put(2, 20) lru.put(3, 30) print("get(1):", lru.get(1)) print("get(2):", lru.get(2)) print("get(3):", lru.get(3)) lru.put(4, 40) print("get(1):", lru.get(1)) print("get(4):", lru.get(4)) lru.put(2, 200) print("get(2):", lru.get(2)) lru.put(5, 50) print("get(3):", lru.get(3)) print("get(2):", lru.get(2)) print("get(4):", lru.get(4)) print("get(5):", lru.get(5))