原文:146. LRU缓存机制(leetcode 解题) - 每天一个JavaScript小知识@Js中文网 · 码农进阶题库

原文地址:https://www.javascriptc.com/interview-tips/zh_cn/leetcode/leetcode-javascript-solution-0146/

题目:

难度:Hard

相关话题:设计

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

思路:

2种方法可以实现,但只是工具不同,思想基本一致。

put内部,先查找当前是否存在key,如果存在,则更新,这时候长度不会发生变化,只是需要将刚刚更新的key-val,放到最新的位置;

如果不存在,也不能立刻添加,先要查看当前是否满了,如果满了,需要将最早的那个删除。

最后再添加新的键值对。

get内部,首先查找当前key是否存在,不存在返回-1,存在除了返回对应的val,还要更新位置,将当前get的键值对放到最新的位置。

这里要求查找增加删除都要是O(1)

  1. 使用jsmap

map本身是按照加入的顺序排序的,并且查找和增加删除都是O(1)

put,只需要找到对应的删除是O(1),如果发现满了,需要删除最早的,那么需要用到map.entries.next().value,就是map的第一个键值对(最早加入的)。

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

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  if(!this.map.has(key))return -1
  let val=this.map.get(key)
  this.map.delete(key)
  this.map.set(key,val)
  return val
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  if(this.map.has(key)){
    this.map.delete(key)
  }else if(this.capacity===this.map.size){
    let firstKey=this.map.entries().next().value[0]
    this.map.delete(firstKey)
  }
  this.map.set(key,value)
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = Object.create(LRUCache).createNew(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */
  1. 使用DoubleLink,双向链表。

双向链表的查找可以使用hash保存每一截链表的引用,键值就是key

另外双向链表的增加删除都是O(1)

/**
 * @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
 * @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
 * @param {number} capacity
 */
// 另:直接使用Map(),默认最新加入会在最后,每次冲突只需删除第一个即可

var DLink = function(key,val){
  this.val=val
  this.key=key
  this.pre=null
  this.next=null
}
var LRUCache = function(capacity) {
  let mockHead=new DLink(null,null),
      mockTail=new DLink(null,null)

  mockHead.next=mockTail
  mockTail.pre=mockHead

  this.removeSelf=function(node){
    node.pre.next=node.next
    node.next.pre=node.pre
    return node
  }
  this.addToHead=function(node){
    node.next=mockHead.next
    mockHead.next.pre=node

    mockHead.next=node
    node.pre=mockHead
    return node
  }
  this.moveToHead=function(node){
    return this.addToHead(this.removeSelf(node))
  }
  this.removeTail=function(){
    return this.removeSelf(mockTail.pre)
  }

  this.map=new Map()
  this.capacity=capacity
  this.curLen=0
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  if(!this.map.has(key))return -1
  let node=this.moveToHead(this.map.get(key))
  this.map.set(key,node)
  return node.val
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  if(this.map.has(key)){
    let oldN=this.map.get(key)
    let newN=this.moveToHead(oldN)
    newN.val=value
    this.map.set(key,newN)
  }else{
    if(this.curLen>=this.capacity){
      let delNode=this.removeTail()
      this.map.delete(delNode.key)
    }
    let newNode=this.addToHead(new DLink(key,value))
    this.map.set(key,newNode)
    this.curLen++
  }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = Object.create(LRUCache).createNew(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */