实现 LRU 缓存机制

[ChuChencheng]

题目

LeetCode 146

思路

本题主要是要解决 put 时如果容量满了，要删除最少使用的缓存 这个问题，因此只要在 put 的时候能知道最少使用的缓存是哪个就行。

解1

使用哈希 Map + 双向链表

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.capacity = capacity
  this.map = new Map()
  // 指向排名开头的指针
  this.pStart = null
  // 指向排名结尾的指针
  this.pEnd = null
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  const result = this.map.get(key)
  // 找不到则返回 -1
  if (!result) return -1
  // 如果 get 的是末尾，则不操作
  if (this.pEnd !== result) {
    if (result.prev) {
      // 如果 get 的不是开头
      // 上一个链表元素的 next 指向 get 的 next
      result.prev.next = result.next
      // 下一个链表元素的 prev 指向 get 的 prev
      result.next.prev = result.prev
    } else {
      // 如果 get 的是开头，则重新赋值 pStart
      this.pStart = result.next
      this.pStart.prev = null
    }
    // get 的元素放到链表末尾
    result.next = null
    this.pEnd.next = result
    result.prev = this.pEnd
    this.pEnd = result
  }
  return result.value
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  if (!this.map.has(key)) {
    if (this.map.size === this.capacity) {
      // 容量达到上限，先删除最近最少使用的缓存，直接把 pStart 指向的链表元素删除
      this.map.delete(this.pStart.key)
      this.pStart = this.pStart.next
      if (this.pStart) {
        this.pStart.prev = null
      }
    }
    // put 操作插入的 rank 一定是最高的，因此 next 指向空
    const element = {
      key,
      value,
      prev: this.pEnd,
      next: null,
    }
    if (this.map.size === 0) {
      this.pStart = element
    } else {
      this.pEnd.next = element
    }
    this.pEnd = element
    this.map.set(key, element)
  } else {
    this.map.get(key).value = value
    this.get(key)
  }
};

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

解2

利用 JavaScript Map 中的 keys() 等遍历方法的遍历顺序是插入顺序这个特性，每次 get 时，如果存在 key ，则先在 Map 里删除这个 key ，再插入这个 key ，插入的 key 就是迭代器遍历的最后一个元素。

在 put 时，通过 map.keys().next() 即可获取第一个插入的元素

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.capacity = capacity
  this.map = new Map()
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  const result = this.map.get(key)
  // 找不到则返回 -1
  if (!result) return -1
  this.map.delete(key)
  this.map.set(key, result)
  return result
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  if (!this.map.has(key)) {
    if (this.map.size === this.capacity) {
      this.map.delete(this.map.keys().next().value)
    }
    this.map.set(key, value)
  } else {
    this.map.delete(key)
    this.map.set(key, value)
  }
};

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