Description
https://leetcode.com/problems/lru-cache/
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.put(key, value) – Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
The cache is initialized with a positive capacity.
Follow up:
Could you do both operations in O(1) time complexity?
Example:
LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4
Explanation
We can use a doubly linked list and hashmap together. Everytime we save a new key value pair, we put the key into the map and create a linked list node as its value. Globally, the linked list shows the order of keys. The list node next to the head is the most recently used key, the list node next to the tail is the least recently used key.
Python Solution
class ListNode:
def __init__(self, key, value):
self.key = key
self.value = value
self.next = None
self.prev = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.head = ListNode(-1, -1)
self.tail = ListNode(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.remove_node(node)
self.insert_to_head(node)
return node.value
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.value = value
self.remove_node(node)
self.cache[key] = node
self.insert_to_head(node)
else:
new_node = ListNode(key, value)
self.insert_to_head(new_node)
self.cache[key] = new_node
if len(self.cache) > self.capacity:
last_node = self.tail.prev
self.tail.prev = last_node.prev
last_node.prev.next = self.tail
del self.cache[last_node.key]
self.remove_node(last_node)
def remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def insert_to_head(self, node):
temp = self.head.next
node.next = temp
node.prev = self.head
self.head.next = node
temp.prev = node
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)- Time complexity: O(N).
- Space complexity: O(N).