【Day 12】 LRU 缓存机制

题目描述

运用你所掌握的数据结构，设计和实现一个 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
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的回答

解法一

时空复杂度

参考回答

确定需要使用的数据结构

根据题目要求,存储的数据需要保证顺序关系(逻辑层面) =⇒ 可以使用数组,链表等
同时需要对数据进行频繁的增删, 时间复杂度 O(1) =⇒ 只能使用链表存储数据
对数据进行读取时, 时间复杂度 O(1) =⇒ 使用哈希表
最终采取双向链表 + 哈希表
双向链表

按最后一次访问的时间的顺序进行排列, 链表头部为最近访问的节点

哈希表

以关键字为键,以链表节点的地址为值

put 操作
通过哈希表, 查看 put 操作传入的关键字对应的链表节点, 是否已经存在
如果已经存在,将该节点的值进行覆盖,同时将该节点位置调整至链表头部
如果不存在,查看当前链表容量是否已满

如果链表容量未满, 新生成节点, 同时将该节点位置调整至链表头部
如果链表容量已满, 删除尾部节点,新生成节点, 同时将该节点位置调整至链表头部

get 操作
通过哈希表, 查看 get 操作传入的关键字对应的链表节点, 是否已经存在
存在, 返回该节点的值, 同时将该节点位置调整至链表头部
不存在, 返回-1

function ListNode(key, val) {
this.key = key
this.val = val;
this.pre = this.next = null;
}

var LRUCache = function(capacity) {
this.capacity = capacity
this.size = 0
this.data = {}
this.head = new ListNode()
this.tail = new ListNode()
this.head.next = this.tail
this.tail.pre = this.head
};

function get (key) {
if(this.data[key] !== undefined){
let node = this.data[key]
this.removeNode(node)
this.appendHead(node)
return node.val
} else {
return -1
}
};

function put (key, value) {
let node
if(this.data[key] !== undefined){
node = this.data[key]
this.removeNode(node)
node.val = value
} else {
node = new ListNode(key, value)
this.data[key] = node
if(this.size < this.capacity){
this.size++
} else {
key = this.removeTail()
delete this.data[key]
}
}
this.appendHead(node)
};

function removeNode (node) {
let preNode = node.pre,
nextNode = node.next
preNode.next = nextNode
nextNode.pre = preNode
};

function appendHead (node) {
let firstNode = this.head.next
this.head.next = node
node.pre = this.head
node.next = firstNode
firstNode.pre = node
};

function removeTail () {
let key = this.tail.pre.key
this.removeNode(this.tail.pre)
return key
};

作者：ZStar01
链接：https://leetcode-cn.com/problems/lru-cache/solution/shuang-lian-biao-ha-xi-biao-by-zstar01/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。