LRU 缓存机制-146

[sl1673495]

146.LRU 缓存机制 https://leetcode-cn.com/problems/lru-cache

运用你所掌握的数据结构，设计和实现一个 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

参考

这篇小姐姐的算法文章，很优雅的代码思路。 https://juejin.im/post/5ec1c3a76fb9a0435749da1d

思路

维护一个「双向链表」node ：

class DoubleNode {
  constructor(key, val) {
    this.key = key
    this.val = val

    this.prev = null
    this.next = null
  }
}

和一个「哈希表」map，map 的目的是通过 key 去查找对应的 node：

// key -> DoubleNode
this.map = new Map()

并且维护 LRUCache 实例中的 head 头结点和 tail 尾结点。

get 操作

从 map 中获取节点，并且把节点的头部更新为本次获取的节点。

put 操作

分为几种情况：

1. 原本就有这个 key 值，那么更新对应 node 的值，并且删掉旧节点，移动新节点头部。
2. 原本没有这个 key 值：
   1. 容量没超过上限：那么就直接放到头部节点即可。
   2. 容量超过了上限：那么就删除尾部节点，把新的节点放到放到头部节点即可。

remove 操作

1. 删除头部节点，需要重新维护 head 的值，以及 next 节点的 prev 值。
2. 删除尾部节点，需要重新维护 tail 的值，以及 prev 节点的 next 值。
3. 删除中间节点，需要维护节点以及它的相邻节点的 prev、next 值。

class DoubleNode {
  constructor(key, val) {
    this.key = key
    this.val = val

    this.prev = null
    this.next = null
  }
}

class LRUCache {
  constructor(max) {
    this.max = max
    this.map = new Map()

    this.head = null
    this.tail = null
  }

  get(key) {
    const node = this.map.get(key)
    if (!node) {
      return -1
    } else {
      const res = node.val
      this.remove(node)
      this.appendHead(node)
      return res
    }
  }

  put(key, value) {
    let node = this.map.get(key)
    // 有这个缓存
    if (node) {
      node.val = value
      // 新加入的 放在最前面
      this.remove(node)
      this.appendHead(node)
    } else {
      // 没有这个缓存
      node = new DoubleNode(key, value)
      // 如果超出容量了 删除最后一个 再放到头部
      if (this.map.size >= this.max) {
        this.map.delete(this.tail.key)
        this.remove(this.tail)
        this.appendHead(node)
        this.map.set(key, node)
      } else {
        // 未超出容量 就直接放到头部
        this.appendHead(node)
        this.map.set(key, node)
      }
    }
  }

  /**
   * 把头部指针的改变成新的node
   * @param {DoubleNode} node
   */
  appendHead(node) {
    if (this.head === null) {
      this.head = this.tail = node
    } else {
      node.next = this.head
      this.head.prev = node
      this.head = node
    }
  }

  /**
   * 删除某个节点
   * @param {DoubleNode} node
   */
  remove(node) {
    if (this.head === this.tail) {
      this.head = this.tail = null
    } else {
      // 删除头部
      if (this.head === node) {
        this.head = this.head.next
        node.next = null
      } else if (this.tail === node) {
        this.tail = this.tail.prev
        this.tail.next = null
        node.prev = null
      } else {
        node.prev.next = node.next
        node.next.prev = node.prev
        node.prev = node.next = null
      }
    }
  }
}