Open qappleh opened 3 years ago
解题思路
代码
var LRUCache = function(capacity) {
this.h = new Map(), this.capacity = capacity
};
LRUCache.prototype.get = function(key, v) {
return (v = this.h.get(key)) && (this.h.delete(key), this.h.set(key, v)) && v || -1
};
LRUCache.prototype.put = function(key, value) {
this.h.delete(key), this.h.set(key, value), this.h.size > this.capacity && this.h.delete(this.h.keys().next().value)
};
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和写入数据 put 。
获取数据 get(key) - 如果密钥 ( key ) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1 。 写入数据 put(key, value) - 如果密钥不存在,则写入数据。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据,从而为新数据留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
附leetcode地址:leetcode