Posted on 2023-01-29 20:34
Uriel 閱讀(47)
評論(0) 編輯 收藏 引用 所屬分類:
模擬 、
閑來無事重切Leet Code
模擬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)