当前位置: 面试刷题>> LRU 缓存(经典算法150题)


LRU 缓存机制

题目描述: 设计并实现一个 LRU(最近最少使用)缓存机制。该机制将允许你获取和设置键值对,并且会在每次访问(无论是获取还是设置)后更新键的顺序,使得最近使用的键总是排在最前面。如果缓存容量已满,则应当移除最久未使用的键(即最末尾的键)。

示例

  • 缓存容量 capacity = 2
  • 操作序列:
    1. cache.put(1, 1)
    2. cache.put(2, 2)
    3. cache.get(1) // 返回 1
    4. cache.put(3, 3) // 该操作会使键 2 作废
    5. cache.get(2) // 返回 -1 (未找到)
    6. cache.get(3) // 返回 3
    7. cache.put(4, 4) // 该操作会使键 1 作废
    8. cache.get(1) // 返回 -1 (未找到)
    9. cache.get(3) // 返回 3
    10. cache.get(4) // 返回 4

要求

  • get(key) 方法应返回键对应的值,如果键不存在则返回 -1。
  • put(key, value) 方法应插入或更新键的值。如果缓存达到其容量,则应该在插入新项之前使最近最少使用的项无效。

PHP 实现

class LRUCache {
    private $capacity;
    private $cache;
    private $keys;

    function __construct($capacity) {
        $this->capacity = $capacity;
        $this->cache = [];
        $this->keys = new SplDoublyLinkedList();
    }

    function get($key) {
        if (!$this->keys->contains($key)) {
            return -1;
        }

        // 移除旧的节点
        $this->keys->offsetUnset($key);
        // 添加到头部(最近使用)
        $this->keys->offsetSet(0, $key);

        return $this->cache[$key];
    }

    function put($key, $value) {
        if ($this->keys->contains($key)) {
            // 如果键已存在,先移除旧的
            $this->keys->offsetUnset($key);
        }

        // 添加新值
        $this->cache[$key] = $value;

        // 添加到头部(最近使用)
        if ($this->keys->count() >= $this->capacity) {
            // 移除最久未使用的项
            $oldestKey = $this->keys->bottom();
            $this->keys->offsetUnset($oldestKey);
            unset($this->cache[$oldestKey]);
        }
        $this->keys->offsetSet(0, $key);
    }
}

注意:PHP 标准库中并没有直接支持双向链表的类,这里为了演示方便,使用了 SplDoublyLinkedList 类来模拟键的顺序,但请注意,它并不直接支持通过值来快速移除节点,因此这里的 containsoffsetUnset 方法仅用于示意,实际实现中可能需要额外的数据结构或逻辑来优化。

Python 实现

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            # 将访问的键值对移动到最前面
            self.cache.move_to_end(key)
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 如果键已存在,先移除旧的
            del self.cache[key]
        elif len(self.cache) >= self.capacity:
            # 移除最久未使用的项
            self.cache.popitem(last=False)
        # 插入新键值对到最前面
        self.cache[key] = value

JavaScript 实现

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.cache = new Map();
    }

    get(key) {
        if (!this.cache.has(key)) {
            return -1;
        }
        // 移除旧的节点
        const value = this.cache.get(key);
        this.cache.delete(key);
        // 添加到头部(最近使用)
        this.cache.set(key, value);
        return value;
    }

    put(key, value) {
        if (this.cache.has(key)) {
            // 如果键已存在,先移除旧的
            this.cache.delete(key);
        } else if (this.cache.size >= this.capacity) {
            // 移除最久未使用的项
            const firstKey = this.cache.keys().next().value;
            this.cache.delete(firstKey);
        }
        // 插入新键值对
        this.cache.set(key, value);
    }
}

以上代码分别用 PHP、Python 和 JavaScript 实现了 LRU 缓存机制,每种语言都利用了其内置的数据结构来优化操作效率。

推荐面试题