LRU
unknown
python
6 months ago
3.1 kB
12
Indexable
class Node: def __init__(self, key=0, val=0, previous=None, next=None): self.key = key self.val = val self.previous = previous self.next = next class LRUCache: def __init__(self, capacity: int): self.n = 0 self.capacity = capacity self.mapa = {} self.left = Node() self.right = Node() self.left.next = self.right self.right.previous = self.left def get(self, key: int) -> int: if key in self.mapa: node = self.mapa[key] if node.previous != self.right.previous: previous = node.previous next = node.next previous.next = next next.previous = previous last = self.right.previous last.next = node node.next = self.right node.previous = last self.right.previous = node return self.mapa[key].val else: return -1 def put(self, key: int, value: int) -> None: new_node = Node(key, value) if self.n == self.capacity and key not in self.mapa: node = self.left.next if self.left.next == node and self.right.previous == node: self.left.next = new_node self.right.previous = new_node new_node.previous = self.left new_node.next = self.right else: left.next = node.next node.next.previous = self.left self.mapa[key] = new_node del self.mapa[node.key] else: if key not in self.mapa: self.n += 1 self.mapa[key] = new_node if self.left.next == self.right.previous: self.left.next = new_node self.right.previous = new_node new_node.previous = self.left new_node.next = self.right else: last = self.right.previous last.next = new_node new_node.next = self.right new_node.previous = last self.right.previous = new_node else: node = self.mapa[key] if self.left.next != node and self.right.previous != node: previous = node.previous next = node.next previous.next = next next.previous = previous last = self.right.previous last.next = node node.next = self.right node.previous = last self.right.previous = node elif self.left.next == node: self.left.next = node.next node.next.previous = self.left last = self.right.previous last.next = node node.next = self.right self.right.previous = node
Editor is loading...
Leave a Comment