Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
模拟Least Frequently Used (LFU) cache的初始化、插入、读取操作
参考了Discussion->https://leetcode.com/problems/lfu-cache/solutions/2844415/python-is-easy/
学习到了python的OrderedDict,用在这里很适合!


 1 #460
 2 #Runtime: 1065 ms (Beats 44.83%)
 3 #Memory: 88.8 MB (Beats 13.79%)
 4 
 5 class Obj:
 6     def __init__(self, key, val, cnt):
 7         self.key = key
 8         self.val = val
 9         self.cnt = cnt
10 
11 
12 class LFUCache(object):
13     def __init__(self, capacity):
14         """
15         :type capacity: int
16         """
17         self.cap = capacity
18         self.obj_keys = {}
19         self.obj_cnt = defaultdict(OrderedDict)
20         self.min_cnt = None
21 
22 
23     def get(self, key):
24         """
25         :type key: int
26         :rtype: int
27         """
28         if key not in self.obj_keys:
29             return -1
30         obj = self.obj_keys[key]
31         del self.obj_cnt[obj.cnt][key]
32         if not self.obj_cnt[obj.cnt]:
33             del self.obj_cnt[obj.cnt]
34         obj.cnt += 1
35         self.obj_cnt[obj.cnt][key] = obj
36         if not self.obj_cnt[self.min_cnt]:
37             self.min_cnt += 1
38         return obj.val
39 
40 
41     def put(self, key, value):
42         """
43         :type key: int
44         :type value: int
45         :rtype: None
46         """
47         if not self.cap:
48             return
49         if key in self.obj_keys:
50             self.obj_keys[key].val = value
51             self.get(key)
52             return
53         if len(self.obj_keys) == self.cap:
54             k, n = self.obj_cnt[self.min_cnt].popitem(last=False) 
55             del self.obj_keys[k]
56         self.obj_cnt[1][key] = self.obj_keys[key] = Obj(key, value, 1)
57         self.min_cnt = 1
58         return
59 
60 
61 # Your LFUCache object will be instantiated and called as such:
62 # obj = LFUCache(capacity)
63 # param_1 = obj.get(key)
64 # obj.put(key,value)

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理