lru-缓存机制

题目

设计和实现一个 LRU (最近最少使用) 缓存机制:

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存

• int get(int key) 如果关键字 key 存在于缓存中, 则返回关键字的值, 否则返回 -1.

• void put(int key, int value) 如果关键字已经存在, 则变更其数据值; 如果关键字不存在, 则插入该组关键字-值. 当缓存容量达到上限时, 它应该在写入新数据之前删除最久未使用的数据值, 从而为新的数据值留出空间.

示例

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

题解

var ListNode = function (key, value) {
  this.key = key
  this.value = value
  this.prev = null
  this.next = null
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity
  this.map = new Map()
  this.head = new ListNode() // 虚拟头节点
  this.tail = new ListNode() // 虚拟尾节点
  this.head.next = this.tail
  this.tail.prev = this.head
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.map.has(key)) {
    return -1
  }
  const node = this.map.get(key)
  this.moveToHead(node)
  return node.value
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.map.has(key)) {
    const node = this.map.get(key)
    node.value = value
    this.moveToHead(node)
  } else {
    const newNode = new ListNode(key, value)
    this.map.set(key, newNode)
    this.addToHead(newNode)
    if (this.map.size > this.capacity) {
      const removedNode = this.removeTail()
      this.map.delete(removedNode.key)
    }
  }
}

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

LRUCache.prototype.addToHead = function (node) {
  node.next = this.head.next
  node.prev = this.head
  this.head.next.prev = node
  this.head.next = node
}

LRUCache.prototype.removeNode = function (node) {
  node.prev.next = node.next
  node.next.prev = node.prev
}

LRUCache.prototype.removeTail = function () {
  const removedNode = this.tail.prev
  this.removeNode(removedNode)
  return removedNode
}

/**
 * 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)
 */