当前位置： 面试刷题>> LFU缓存 (经典算法题500道)
### 完整题目描述
**LFU（Least Frequently Used）缓存** 是一种缓存淘汰策略，它会跟踪每个数据项被访问的频率，并淘汰访问频率最低的数据项。当缓存达到其容量限制时，且需要添加新的数据项到缓存中时，LFU缓存会移除访问频率最低的数据项（如果有多个数据项具有相同的最低频率，则通常选择最久未被访问的那个）。
**题目要求**：
实现一个LFU缓存，该缓存应支持以下操作：
1. `get(key)`: 获取键 `key` 对应的值，如果键不存在则返回 -1。
2. `put(key, value)`: 插入或更新键 `key` 的值 `value`。如果缓存达到其容量限制，则应该在使用 `put` 方法之前，移除最不常用的数据项。
缓存的容量由构造函数的参数给定。
**示例**：
```
LFUCache cache = new LFUCache(2); // 缓存容量为 2
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 淘汰键 2
cache.get(2); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.put(4, 4); // 淘汰键 1
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
```
### PHP 示例代码
```php
class Node {
public $key;
public $value;
public $freq;
public $prev;
public $next;
function __construct($key, $value, $freq = 1) {
$this->key = $key;
$this->value = $value;
$this->freq = $freq;
$this->prev = null;
$this->next = null;
}
}
class LFUCache {
private $capacity;
private $minFreq;
private $freqMap;
private $keyMap;
function __construct($capacity) {
$this->capacity = $capacity;
$this->minFreq = 0;
$this->freqMap = [];
$this->keyMap = [];
}
// 辅助函数：增加节点频率
private function increaseFreq($node) {
$freq = $node->freq;
$node->freq++;
$this->removeNodeFromDLL($node, $this->freqMap[$freq]);
if (!isset($this->freqMap[$node->freq])) {
$this->freqMap[$node->freq] = new DoublyLinkedList();
if ($this->minFreq == $freq) {
$this->minFreq++;
}
}
$this->freqMap[$node->freq]->addToHead($node);
}
// 辅助函数：从双向链表中移除节点
private function removeNodeFromDLL($node, $dll) {
if ($dll->head == $node) {
$dll->head = $node->next;
}
if ($dll->tail == $node) {
$dll->tail = $node->prev;
}
if ($node->prev !== null) {
$node->prev->next = $node->next;
}
if ($node->next !== null) {
$node->next->prev = $node->prev;
}
}
// 其他函数如 get, put, DoublyLinkedList 定义略
}
// 注意：这里省略了 DoublyLinkedList 的定义和 put, get 方法的具体实现，
// 因为它们需要更详细的逻辑来处理双向链表和哈希表的结合使用。
```
### Python 示例代码
Python 示例将更为简洁，使用标准库 `collections` 中的 `OrderedDict` 来简化实现。
```python
from collections import OrderedDict
class LFUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
self.freq_map = {}
def get(self, key: int) -> int:
if key not in self.cache:
return -1
freq = self.cache[key][1]
self.cache.move_to_end(key) # 将访问的键移动到有序字典的末尾
# 更新频率
if freq in self.freq_map:
self.freq_map[freq].remove(key)
if not self.freq_map[freq]:
del self.freq_map[freq]
freq += 1
if freq not in self.freq_map:
self.freq_map[freq] = []
self.freq_map[freq].append(key)
self.cache[key] = (self.cache[key][0], freq)
return self.cache[key][0]
def put(self, key: int, value: int) -> None:
if self.capacity <= 0:
return
if key in self.cache:
self.cache.move_to_end(key)
_, freq = self.cache[key]
self.freq_map[freq].remove(key)
if not self.freq_map[freq]:
del self.freq_map[freq]
freq += 1
else:
if len(self.cache) >= self.capacity:
min_freq = min(self.freq_map.keys())
evict_key = self.freq_map[min_freq].pop(0)
del self.cache[evict_key]
if not self.freq_map[min_freq]:
del self.freq_map[min_freq]
freq = 1
if freq not in self.freq_map:
self.freq_map[freq] = []
self.freq_map[freq].append(key)
self.cache[key] = (value, freq)
# 示例用法略
```
### JavaScript 示例代码
JavaScript 示例将使用 Map 和数组来实现类似的功能。
```javascript
class LFUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
this.freqMap = new Map();
this.minFreq = 0;
}
get(key) {
if (!this.cache.has(key)) return -1;
const [value, freq] = this.cache.get(key);
this.cache.delete(key);
if (this.freqMap.has(freq)) {
const list = this.freqMap.get(freq);
const index = list.indexOf(key);
list.splice(index, 1);
if (list.length === 0) this.freqMap.delete(freq);
if (freq === this.minFreq && this.freqMap.get(freq) === undefined) {
this.minFreq++;
}
}
const newFreq = freq + 1;
if (!this.freqMap.has(newFreq)) {
this.freqMap.set(newFreq, []);
}
this.freqMap.get(newFreq).push(key);
this.cache.set(key, [value, newFreq]);
return value;
}
put(key, value) {
if (this.capacity <= 0) return;
if (this.cache.has(key)) {
this.cache.delete(key);
} else if (this.cache.size === this.capacity) {
const minFreqKeys = this.freqMap.get(this.minFreq);
const evictKey = minFreqKeys.shift();
this.cache.delete(evictKey);
if (minFreqKeys.length === 0) {
this.freqMap.delete(this.minFreq);
this.minFreq = 0;
for (let [freq, keys] of this.freqMap) {
this.minFreq = freq;
break;
}
}
}
const freq = this.cache.has(key) ? this.cache.get(key)[1] + 1 : 1;
if (!this.freqMap.has(freq)) {
this.freqMap.set(freq, []);
}
this.freqMap.get(freq).push(key);
if (freq ===