LeetCode 146. LRU缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
  • void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例

输入

text
12
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出

text
1
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释

js
12345678910
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示

  • 1 <= capacity <= 3000
  • 0 <= key <= 10000
  • 0 <= value <= 10^5
  • 最多调用 2 * 10^5 次 get 和 put

解题思路

此题需要对容器中的元素进行频繁地取出和插入操作，并且需要拿到链表首尾的元素，所以可以使用双向链表的数据结构进行存储。

为了能够快速地找到对应的元素，则需要维护一个哈希表来对元素进行存储。

  • get 方法实现：先查询当前所需要的元素是否在哈希表中，如果不存在则返回 -1；存在则返回当前元素的值，并且将该节点放到链表首部。
  • put 方法实现：先查询当前所需要的元素是否在哈希表中。
    • 如果存在，则直接将该节点的值修改为新值，并且将该节点放到链表首部；
    • 如果不存在，则需要判断当前链表是否还有空间存入新元素：如果有空间，则直接将新节点存入链表首部并将长度加一；如果没有空间了，就将链表尾部的节点删除，并在首部存入新元素。

由于这两个方法的实现都需要将节点从链表中删除、以及将节点添加到链表首部，所以可以直接封装成两个方法用来单独处理这两件事。

代码实现

js
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394
/**
 * LeetCode 146. LRU缓存
 *
 * 请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 */

// 定义节点结构
class nodeList {
    constructor(key, val) {
        this.key = key
        this.value = val
        this.prev = null
        this.next = null
    }
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {   // 链表的构造函数
    this.capacity = capacity    // 链表的最大长度
    this.num = 0                // 当前链表的长度
    this.first = new nodeList() // 首尾节点
    this.last = new nodeList()
    this.hash = []              // 哈希表
    this.first.next = this.last // 将首尾节点相连
    this.last.prev = this.first
};

// 从链表上删除节点方法
LRUCache.prototype.removeNode = function (node) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

// 将节点添加到链表首部
LRUCache.prototype.addToHead = function (node) {
    node.prev = this.first
    node.next = this.first.next
    this.first.next.prev = node
    this.first.next = node
}

LRUCache.prototype.moveToHead = function (node) {
    this.removeNode(node)
    this.addToHead(node)
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (this.hash[key] != null) {
        this.moveToHead(this.hash[key])
        return this.hash[key].value
    } else return -1
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.hash[key] != null) {
        this.moveToHead(this.hash[key])
        this.hash[key].value = value
    } else {
        const newNode = new nodeList(key, value)
        if (this.capacity > this.num) {
            this.addToHead(newNode)
            this.hash[key] = newNode
            this.num++
        } else {
            this.hash[this.last.prev.key] = null
            this.removeNode(this.last.prev)
            this.addToHead(newNode)
            this.hash[key] = newNode
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */