题目:
难度: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)
。
- 使用
js
的map
。
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)
*/
- 使用
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)
*/