forked from mdmzfzl/NeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
0146-lru-cache.py
150 lines (117 loc) · 4.57 KB
/
0146-lru-cache.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
"""
Problem: LeetCode 146 - LRU Cache
Key Idea:
To implement an LRU (Least Recently Used) cache, we can use a combination of a dictionary (to store key-value pairs) and a doubly linked list (to maintain the order of usage). The dictionary allows for quick access to values, and the doubly linked list helps in efficient removal and addition of elements. When a key is accessed or a new key is added, we update its position in the linked list. When the cache is full, we remove the least recently used item from the tail of the linked list.
Time Complexity:
1. The 'get' operation takes O(1) time, as dictionary access is constant time.
2. The 'put' operation takes O(1) time, as dictionary insertion and removal are constant time.
Space Complexity:
The space complexity is O(capacity), as we store key-value pairs in the dictionary and maintain a doubly linked list for the same number of elements.
"""
class Node: #create node for doubly linked list
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
def remove(self, node):
prev, nxt = node.prev, node.next
prev.next, nxt.prev = nxt, prev
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:
lru = self.left.next
self.remove(lru)
del self.cache[lru.key]
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
self.order = DoublyLinkedList()
def get(self, key: int) -> int:
if key in self.cache:
self.order.move_to_front(key)
return self.cache[key]
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache[key] = value
self.order.move_to_front(key)
else:
if len(self.cache) >= self.capacity:
removed_key = self.order.remove_last()
del self.cache[removed_key]
self.cache[key] = value
self.order.add_to_front(key)
class DoublyLinkedList:
def __init__(self):
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
self.nodes = {}
def add_to_front(self, key):
node = ListNode(key)
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
self.nodes[key] = node
def move_to_front(self, key):
node = self.nodes[key]
node.prev.next = node.next
node.next.prev = node.prev
self.add_to_front(key)
def remove_last(self):
node = self.tail.prev
node.prev.next = self.tail
self.tail.prev = node.prev
del self.nodes[node.key]
return node.key
class ListNode:
def __init__(self, key=None):
self.key = key
self.prev = None
self.next = None
"""
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key in self.cache:
self.cache.move_to_end(key)
return self.cache[key]
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
elif self.capacity <= 0:
_ = self.cache.popitem(False)
else:
self.capacity = max(0, self.capacity - 1)
self.cache[key] = value
"""
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)