146. LRU Cache
Design, Hash Table, Linked List, Double Linked List, AMateList ·Problem Statement
link: LeetCode.cn LeetCode 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. The functions get and put must each run in O(1) average time complexity.
Example:
Input: ["LRUCache", "put", "put", "get", "put", "get"，"put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output: [null, null, null, 1, null, -1, null, -1, 3, 4]
Constraints: 1 <= capacity <= 3000 0 <= key <= 10^4 0 <= value <= 10^5 At most 2 * 105 calls will be made to get and put.
Solution Approach
Solution 1 Utilizes an OrderedDict to efficiently manage cache entries and maintain the order of usage, ensuring O(1) time complexity for both get and put operations.
Solution 2 Employs a doubly linked list and a hash map to maintain O(1) time complexity for both operations, by keeping track of the order of nodes and enabling quick removal and insertion.
Algorithm
Solution 1 (Using OrderedDict) Maintain Order: Use an OrderedDict to preserve the order of access, with the most recently accessed items moved to the end. Handle Cache Hits: On get, move the accessed item to the end to mark it as recently used, and return its value. Evict Least Recently Used: On put, if the cache exceeds capacity, remove the oldest item (the first item in the OrderedDict) before adding the new item.
Solution 2 (Using Doubly Linked List and Hash Map) Manage Nodes: Use a doubly linked list to keep track of the order of cache entries, with the head and tail nodes representing the least and most recently used items, respectively. Update Order: On get or put, remove the node from its current position and reinsert it at the end of the list to mark it as most recently used. Evict Oldest: If the cache exceeds capacity on put, remove the node immediately following the head (the least recently used item) from both the linked list and the hash map.
Implement
class LRUCache:
def __init__(self, capacity: int):
self.dic = OrderedDict()
self.capacity = capacity
self.size = 0
def get(self, key: int) -> int:
if key in self.dic:
self.dic.move_to_end(key)
return self.dic[key]
else:
return - 1
def put(self, key: int, value: int) -> None:
if key in self.dic:
self.dic.move_to_end(key)
self.dic[key] = value
else:
if self.size >= self.capacity:
self.dic.popitem(False)
self.dic[key] = value
else:
self.dic[key] = value
self.size += 1
#solution 2 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)
del self.cache[lru.key]