least frequently used (LFU) 算法
我们使用双链表和Hash表构造LFU，可以做到O(1)的时间复杂度。
Leetcode 460
题目书名
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
实现 LFUCache 类：
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键存在于缓存中，则获取键的值，否则返回 -1。
void put(int key, int value) - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。
注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。
进阶：
你是否可以在 O(1) 时间复杂度内执行两项操作？
示例：
输入：
["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]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释：
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1);
lFUCache.put(2, 2);
lFUCache.get(1); // 返回 1
lFUCache.put(3, 3); // 去除键 2
lFUCache.get(2); // 返回 -1（未找到）
lFUCache.get(3); // 返回 3
lFUCache.put(4, 4); // 去除键 1
lFUCache.get(1); // 返回 -1（未找到）
lFUCache.get(3); // 返回 3
lFUCache.get(4); // 返回 4
提示：
0 <= capacity, key, value <= 104
最多调用 105 次 get 和 put 方法
class Node:
def __init__(self, k, v):
self.k = k
self.val = v
self.count = 0
self.prev = None
self.next = None
# 双链表结构
class DoubleLinkList:
def __init__(self):
self.size = 0
self._head = Node(-1, -1)
self._tail = Node(-1, -1)
self._head.next = self._tail
self._tail.prev = self._head
def push(self, node):
node.prev = self._head
node.next = self._head.next
self._head.next.prev = node
self._head.next = node
self.size += 1
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
self.size -= 1
def head(self):
return self._head.next
def tail(self):
return self._tail.prev
def __len__(self):
return self.size
def __str__(self):
node = []
nxt = self._head.next
for _ in range(self.size):
node.append(str(nxt.val))
nxt = nxt.next
return '->'.join(node)
class LFUCache:
def __init__(self, capacity: int):
self.min_freq = 0
self.data = {}
self.freqs = {}
self.cap = capacity
def put(self, key: int, value: int) -> int:
if self.cap <= 0:
return -1
if key in self.data:
self.data[key].val = value
self.increase_freq(self.data[key])
return
# 容量已满，删除
if self.cap <= len(self.data):
last = self.remove()
del self.data[last.k]
# key不存在
node = Node(key, value)
node.count = 1
self.data[key] = node
if node.count not in self.freqs:
self.freqs[node.count] = DoubleLinkList()
self.freqs[node.count].push(node)
self.min_freq = 1
def get(self, key: int) -> int:
if key not in self.data:
return -1
node = self.data[key]
self.increase_freq(node)
return node.val
def increase_freq(self, node):
# 增加频率
freq = node.count
self.freqs[freq].remove(node)
if (node.count + 1) not in self.freqs:
self.freqs[node.count + 1] = DoubleLinkList()
node.count += 1
self.freqs[node.count].push(node)
# 增加前的freq已经没有元素了，将min_freq++
if len(self.freqs[freq]) == 0 and freq == self.min_freq:
self.min_freq += 1
def remove(self) -> Node:
nodes = self.freqs[self.min_freq]
# 删除尾结点（最早添加）
tailNode = nodes.tail()
nodes.remove(tailNode)
return tailNode