Leetcode 146. LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
Follow up:
Could you do get and put in O(1) time complexity?
Example 1:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[, , , , , , , , , ]
Output
Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
At most 3 * 104 calls will be made to get and put.
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.head = Node(-1, -1)
self.tail = Node(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
self.hashmap = collections.defaultdict(Node)
def get(self, key: int) -> int:
if key not in self.hashmap:
return -1
node = self.hashmap
self.remove(node)
self.add(node)
return self.hashmap.val
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
self.hashmap.val = value
node = self.hashmap
self.remove(node)
self.add(node)
return
if len(self.hashmap) >= self.capacity:
last = self.tail.prev
self.hashmap.pop(last.key)
self.remove(last)
new_node = Node(key, value)
self.hashmap = new_node
self.add(new_node)
def remove(self, node: Node) -> None:
prev = node.prev
next = node.next
prev.next = next
next.prev = prev
def add(self, node: Node) -> None:
next = self.head.next
self.head.next = node
node.prev = self.head
node.next = next
next.prev = node
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
页:
[1]