-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path146_LRUCache.py
More file actions
47 lines (41 loc) · 1.18 KB
/
146_LRUCache.py
File metadata and controls
47 lines (41 loc) · 1.18 KB
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
"""
146 LRU 缓存机制
数据结构
进阶：O(1)时间复杂度的操作函数
"""
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity):
# capacity: int
self.capacity = capacity
self.dict = OrderedDict()
def get(self, key):
if key in self.dict:
self.dict.move_to_end(key, last=True)
return self.dict[key]
else:
return -1
def put(self, key, value):
if key in self.dict:
self.dict.move_to_end(key, last=True)
self.dict[key] = value
if len(self.dict) > self.capacity:
self.dict.popitem(last=False)
class LRUCache_v2:
def __init__(self, capacity):
# capacity: int
self.capacity = capacity
self.dict = {}
def get(self, key):
if key not in self.dict:
return -1
value = self.dict.pop(key)
self.dict[key] = value
return value
def put(self, key, value):
if key in self.dict:
self.dict.pop(key)
self.dict[key] = value
if len(self.dict) > self.capacity:
head = list(self.dict)[0]
self.dict.pop(head)