完整题目描述

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 示例代码

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 来简化实现。

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 和数组来实现类似的功能。

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 ===