Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Node:
- def __init__(self, key, val):
- self.key, self.val = key, val
- self.prev = self.next = None
- class LRUCache:
- def __init__(self, capacity: int):
- self.cap = capacity
- self.cache = {} # map key to node
- self.left, self.right = Node(0, 0), Node(0, 0)
- self.left.next, self.right.prev = self.right, self.left
- # remove node from list
- def remove(self, node):
- prev, nxt = node.prev, node.next
- prev.next, nxt.prev = nxt, prev
- # insert node at right
- def insert(self, node):
- prev, nxt = self.right.prev, self.right
- prev.next = nxt.prev = node
- node.next, node.prev = nxt, prev
- 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] = Node(key, value)
- self.insert(self.cache[key])
- if len(self.cache) > self.cap:
- # remove from the list and delete the LRU from hashmap
- lru = self.left.next
- self.remove(lru)
- print(lru in self.cache)
- del self.cache[lru.key]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement