leetcode 146. LRU缓存机制

[xxleyi]

题：运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

 要求 O(1) 时间复杂度内完成这两种操作。

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

解：这是一道 ADT 设计题，通用解法是双向链表加哈希表实现有序哈希。面试时，最好手写实现，而不是直接使用自带的有序字典。

既然要求两种操作的复杂度均为 O(1)，那还有「循环不变式」吗？

单次操作没有，但考虑实际应用场景，其实隐含着一个 while true 循环，循环体的操作是 get 或 put。不变式就是 ADT 的要求：「保持缓存按照使用顺序排序，且达到缓存上限时，新增之前要先剔除掉最末尾的缓存」。

function DoubleLinkedNode(data) {
  this.data = data
  this.pre = null
  this.next = null
}

function DoubleLinkedList() {
  this.head = new DoubleLinkedNode(null)
  this.tail = new DoubleLinkedNode(null)
  this.head.next = this.tail
  this.tail.pre = this.head
  this.size = 0
}

DoubleLinkedList.prototype.add = function(node) {
  // insert between this.head and this.head.next
  node.next = this.head.next
  node.pre = this.head
  this.head.next.pre = node
  this.head.next = node
  this.size++
}

DoubleLinkedList.prototype.remove = function(node) {
  // remove node from its pre and next
  const [pre, next] = [node.pre, node.next]
  pre.next = next
  next.pre = pre
  node.pre = node.next = null
  this.size--
}

DoubleLinkedList.prototype.pop = function() {
  // remove this.tail.pre
  const node = this.tail.pre
  this.remove(node)
  return node
}

var LRUCache = function(capacity) {
  this.capacity = capacity
  this.size = 0
  this._cache = {}
  this._list = new DoubleLinkedList()
}

LRUCache.prototype.get = function(key) {
  if (!(key in this._cache)) return -1

  // if reuse some node
  // then must remove it from list
  // and readd it
  const node = this._cache[key]
  this._list.remove(node)
  this._list.add(node)

  // return value at last
  return node.data.value
}

LRUCache.prototype.put = function(key, value) {
  // if key already existed
  // then remove the node from list
  if (key in this._cache) this._list.remove(this._cache[key])
  // if full
  // then must pop the tail.pre from list
  // and delete it from cache
  else if (this.size === this.capacity) {
    const node = this._list.pop()
    delete this._cache[node.data.key]
  }
  // if not full, size++
  else this.size++

  // at last, add the new node into list and cache
  const node = new DoubleLinkedNode({key, value})
  this._list.add(node)
  this._cache[key] = node
}

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