题目描述：
    运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
    实现 LRUCache 类：
        LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
        int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
        void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。
                当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
示例：
    输入：["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
            [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
    输出：[null, null, null, 1, null, -1, null, -1, 3, 4]
    解释：
        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
var Node = function (key = null, val = null, next = null, pre = null) {
    //TODO
}
var LRUCache = function (capacity = 0) {
    //TODO
        this.capacity = capacity
      this.lru = {}
      this.sort = []
};
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    //TODO
  if (this.lru[key] !== null) {
    let index = this.sort.findIndex(key)
    this.sort.splice(index, 1)
    this.sort.push(key)
    return this.lru[key]
  }
  return -1
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    //TODO
  if (this.sort.length >= this.capacity) {
    this.sort.unshift()
    this.sort.push(key)
    this.lru[key] =value
  } else {
      this.lru[key] = value
    this.sort.push(key)
  }
};

我的回答

var Node = function (key = null, val = null, next = null, pre = null) {
    //TODO
}
var LRUCache = function (capacity = 0) {
    //TODO
        this.capacity = capacity
      this.lru = {}
      this.sort = []
};
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    //TODO
  if (this.lru[key] !== null) {
    let index = this.sort.findIndex(key)
    this.sort.splice(index, 1)
    this.sort.push(key)
    return this.lru[key]
  }
  return -1
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    //TODO
  if (this.sort.length >= this.capacity) {
    this.sort.unshift()
    this.sort.push(key)
    this.lru[key] =value
  } else {
      this.lru[key] = value
    this.sort.push(key)
  }
};

参考回答

//思路：用ES6提供的Map（hash表结构）来存储映射关系实现查询O(1)，为了实现put操作O（1），用双向链表实现按访问顺序组织数据，然后通过尾指针获取最早的节点来当数据超过时进行删除。然后将链表节点作为Map的value存入 
// 关键点：边缘情况，特别是涉及头指针和尾指针移动的时候移动到的位置是否可能为空 
var Node = function (key = null, val = null, next = null, pre = null) { 
  this.key = key 
  this.val = val 
  this.next = next 
  this.pre = pre 
} 
var LRUCache = function (capacity = 0) { 
  this.capacity = capacity 
  this.map = new Map() 
  this.head = null 
  this.last = null 
};
/**
@param {number} key
@return {number} 
*/
LRUCache.prototype.get = function (key) { 
  if (this.map.has(key)) { 
    let node = this.map.get(key)
    if (node !== this.head) {
        if (node === this.last) {
            this.last = node.pre
        }
        let preNode = node.pre
        let nextNode = node.next
        if (preNode)
            preNode.next = nextNode
        if (nextNode)
            nextNode.pre = preNode
            node.pre = null
            node.next = this.head
            this.head.pre = node
            this.head = node
        }
        return node.val
    } 
  return -1 
};
/**
@param {number} key
@param {number} value
@return {void} */ 
LRUCache.prototype.put = function (key, value) { 
  if (this.map.has(key)) { 
    let node = this.map.get(key) 
    node.val = value
    if (node !== this.head) {
        if (node === this.last) {
            this.last = node.pre
        }
        let preNode = node.pre
        let nextNode = node.next
        if (preNode) preNode.next = nextNode
        if (nextNode) nextNode.pre = preNode
        node.pre = null
        node.next = this.head
        this.head.pre = node
        this.head = node
    }
    } else { 
    if (this.capacity === 0) { 
      this.map.delete(this.last.key) 
      if (this.last.pre) { this.last.pre.next = null } 
      this.last = this.last.pre 
    } 
    let newNode = new Node(key, value) 
    this.map.set(key, newNode) 
    if (this.head) { 
      this.head.pre = newNode 
      newNode.next = this.head 
    } else { 
      this.last = newNode 
    } 
    this.head = newNode 
    if (this.capacity > 0) this.capacity-- 
  } 
};

前端面试题

232. LRU缓存机制

我的回答

参考回答