Leetcode 146. LRU Cache

Seawolf

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"]
[[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]

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.

1. class Node:
   
2.     def __init__(self, key, val):
   
3.         self.key = key
   
4.         self.val = val
   
5.         self.prev = None
   
6.         self.next = None
   
7. 
   
8. class LRUCache:
   
9.     def __init__(self, capacity: int):
   
10.         self.capacity = capacity
    
11.         self.head = Node(-1, -1)
    
12.         self.tail = Node(-1, -1)
    
13.         self.head.next = self.tail
    
14.         self.tail.prev = self.head
    
15.         self.hashmap = collections.defaultdict(Node)
    
16. 
    
17.     def get(self, key: int) -> int:
    
18.         if key not in self.hashmap:
    
19.             return -1
    
20.         node = self.hashmap[key]
    
21.         self.remove(node)
    
22.         self.add(node)
    
23.         return self.hashmap[key].val
    
24. 
    
25.     def put(self, key: int, value: int) -> None:
    
26.         if key in self.hashmap:
    
27.             self.hashmap[key].val = value
    
28.             node = self.hashmap[key]
    
29.             self.remove(node)
    
30.             self.add(node)
    
31.             return
    
32.         
    
33.         if len(self.hashmap) >= self.capacity:
    
34.             last = self.tail.prev
    
35.             self.hashmap.pop(last.key)
    
36.             self.remove(last)
    
37.         new_node = Node(key, value)
    
38.         self.hashmap[key] = new_node
    
39.         self.add(new_node)
    
40.         
    
41.     def remove(self, node: Node) -> None:
    
42.         prev = node.prev
    
43.         next = node.next
    
44.         prev.next = next
    
45.         next.prev = prev
    
46.         
    
47.     def add(self, node: Node) -> None:
    
48.         next = self.head.next
    
49.         self.head.next = node
    
50.         node.prev = self.head
    
51.         node.next = next
    
52.         next.prev = node
    
53. # Your LRUCache object will be instantiated and called as such:
    
54. # obj = LRUCache(capacity)
    
55. # param_1 = obj.get(key)
    
56. # obj.put(key,value)

复制代码