460. LFU Cache
Đề Bài
Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity)Initializes the object with thecapacityof the data structure.int get(int key)Gets the value of thekeyif thekeyexists in the cache. Otherwise, returns-1.void put(int key, int value)Update the value of thekeyif present, or inserts thekeyif not already present. When the cache reaches itscapacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently usedkeywould be invalidated.
To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.
When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
Explanation
// cnt(x) = the use counter for key x
// cache=[] will show the last used order for tiebreakers (leftmost element is most recent)
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // return 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 2 is the LFU key because cnt(2)=1 is the smallest, invalidate 2.
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // Both 1 and 3 have the same cnt, but 1 is LRU, invalidate 1.
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // return -1 (not found)
lfu.get(3); // return 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // return 4
// cache=[4,3], cnt(4)=2, cnt(3)=3
Constraints:
0 <= capacity <= 1040 <= key <= 1050 <= value <= 109- At most
2 * 105calls will be made togetandput.
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n)
💾 Không gian
O(n)
Lời Giải
C++
0460-lfu-cache.cpp
import collections
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.freq = 1
self.prev = self.next = None
class DLinkedList:
def __init__(self):
self._sentinel = Node(None, None)
self._sentinel.next = self._sentinel.prev = self._sentinel
self._size = 0
def __len__(self):
return self._size
def append(self, node):
node.next = self._sentinel.next
node.prev = self._sentinel
node.next.prev = node
self._sentinel.next = node
self._size += 1
def pop(self, node=None):
if self._size == 0:
return
if not node:
node = self._sentinel.prev
node.prev.next = node.next
node.next.prev = node.prev
self._size -= 1
return node
class LFUCache:
def __init__(self, capacity):
self._size = 0
self._capacity = capacity
self._node = dict()
self._freq = collections.defaultdict(DLinkedList)
self._minfreq = 0
def _update(self, node):
freq = node.freq
self._freq[freq].pop(node)
if self._minfreq == freq and not self._freq[freq]:
self._minfreq += 1
node.freq += 1
freq = node.freq
self._freq[freq].append(node)
def get(self, key):
if key not in self._node:
return -1
node = self._node[key]
self._update(node)
return node.val
def put(self, key, value):
if self._capacity == 0:
return
if key in self._node:
node = self._node[key]
self._update(node)
node.val = value
else:
if self._size == self._capacity:
node = self._freq[self._minfreq].pop()
del self._node[node.key]
self._size -= 1
node = Node(key, value)
self._node[key] = node
self._freq[1].append(node)
self._minfreq = 1
self._size += 1
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Python
0460-lfu-cache.py
class Node:
def __init__(self, key, val, cnt):
self.key = key
self.val = val
self.cnt = cnt
class LFUCache:
def __init__(self, capacity: int):
self.countOfLL = defaultdict(deque)
self.keyOfNode = defaultdict(Node)
self.capacity = capacity
self.minFreq = 0
def get(self, key: int) -> int:
if key not in self.keyOfNode:
return -1
node = self.keyOfNode[key]
self.countOfLL[node.cnt].remove(key)
node.cnt += 1
self.countOfLL[node.cnt].appendleft(key)
if not self.countOfLL[self.minFreq]:
self.minFreq += 1
return node.val
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
if key in self.keyOfNode:
self.keyOfNode[key].val = value
self.get(key)
else:
if len(self.keyOfNode) == self.capacity:
del self.keyOfNode[self.countOfLL[self.minFreq].pop()]
self.minFreq = 1
self.keyOfNode[key] = Node(key, value, self.minFreq)
self.countOfLL[self.minFreq].appendleft(key)
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)