https://leetcode-cn.com/problems/lru-cache/
运用你所掌握的数据结构，设计和实现一个 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
先来看个非计算机的例子理解下题意，假设我们有一个玩具摊位，可以向顾客展示小玩具。玩具很多，但摊位大小有限，不能一次性展示所有玩具，于是我们就把大部分的玩具都放在了仓库里。
如果有顾客来询问某个玩具，我们就去仓库把那个玩具拿出来，摆在摊位上。
因为摊位最上面的位置最显眼，所以我们总是把最新拿出来的玩具放在那。
不过由于摊位大小有限，很快就摆满了，这时如果又来了顾客想看新玩具。
我们只能把摊位最下面的玩具拿回仓库(因为最下面的位置相对没那么受欢迎)，然后其他玩具往下移，腾出最上面的位置来放新玩具。
如果顾客想看的玩具就摆在摊位上，我们就可以把这个玩具直接移到摊位最上面的位置，其他的玩具就要往下挪挪位置了。还记得我们的规则吧，最近有人询问的玩具要摆在最上面显眼的位置。
回到计算机问题上面来，玩具摊位代表的就是缓存空间，我们需要考虑的问题是使用哪种数据结构来表示玩具摊位。
选择1: 数组
如果选择数组，因为玩具在摊位上的位置会挪来挪去，时间复杂度是
选择2: 链表
- 如果选择链表，我们知道在已知位置上新增节点，或者移除一个已知节点的时间复杂度是
$O(1)$ 。不过，链表查找节点的时间复杂度是$O(N)$ ，同样不符合题意，但这还有办法补救。 - 在玩具摊位的例子中，我们手动移动玩具的时候，只需要看一眼就知道要找的玩具在哪个位置上，但计算机没那么聪明，因此还需要给它一个脑子(哈希表)来记录什么玩具在什么位置上，也就是要用一个哈希表来记录每个 key 对应的链表节点引用。这样查找链表节点的时间复杂度就降到了
$O(1)$ ，不过代价是空间复杂度增加到了$O(N)$ 。 - 另外，由于移除链表节点后还需要把该节点前后的两个节点连起来，因此我们需要的是双向链表而不是单向链表。
- 时间复杂度：$O(1)$。
- 空间复杂度：链表
$O(N)$ ，哈希表$O(N)$ ，结果还是$O(N)$ ，N 为容量大小。
// put
if key 存在:
更新节点值
把节点移到链表头部
else:
if 缓存满了:
移除最后一个节点
删除它在哈希表中的映射
新建一个节点
把节点加到链表头部
在哈希表中增加映射
// get
if key 存在:
返回节点值
把节点移到链表头部
else:
返回 -1
JavaScript Code
class DoubleLinkedListNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
// Mappings of key->node.
this.hashmap = {};
// Use two dummy nodes so that we don't have to deal with the head/tail seperately.
this.dummyHead = new DoubleLinkedListNode(null, null);
this.dummyTail = new DoubleLinkedListNode(null, null);
this.dummyHead.next = this.dummyTail;
this.dummyTail.prev = this.dummyHead;
}
_isFull() {
return Object.keys(this.hashmap).length === this.capacity;
}
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.prev = null;
node.next = null;
return node;
}
_addToHead(node) {
const head = this.dummyHead.next;
node.next = head;
head.prev = node;
node.prev = this.dummyHead;
this.dummyHead.next = node;
}
get(key) {
if (key in this.hashmap) {
const node = this.hashmap[key];
this._addToHead(this._removeNode(node));
return node.value;
} else {
return -1;
}
}
put(key, value) {
if (key in this.hashmap) {
// If key exists, update the corresponding node and move it to the head.
const node = this.hashmap[key];
node.value = value;
this._addToHead(this._removeNode(node));
} else {
// If it's a new key.
if (this._isFull()) {
// If the cache is full, remove the tail node.
const node = this.dummyTail.prev;
delete this.hashmap[node.key];
this._removeNode(node);
}
// Create a new node and add it to the head.
const node = new DoubleLinkedListNode(key, value);
this.hashmap[key] = node;
this._addToHead(node);
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* var obj = new LRUCache(capacity)
* var param_1 = obj.get(key)
* obj.put(key,value)
*/C++ Code
class DLinkedListNode {
public:
int key;
int value;
DLinkedListNode *prev;
DLinkedListNode *next;
DLinkedListNode() : key(0), value(0), prev(NULL), next(NULL) {};
DLinkedListNode(int k, int val) : key(k), value(val), prev(NULL), next(NULL) {};
};
class LRUCache {
public:
LRUCache(int capacity) : capacity_(capacity) {
// 创建两个 dummy 节点来简化操作，这样就不用特殊对待头尾节点了
dummy_head_ = new DLinkedListNode();
dummy_tail_ = new DLinkedListNode();
dummy_head_->next = dummy_tail_;
dummy_tail_->prev = dummy_head_;
}
int get(int key) {
if (!key_exists_(key)) {
return -1;
}
// 1. 通过哈希表找到 key 对应的节点
// 2. 将节点移到链表头部
// 3. 返回节点值
DLinkedListNode *node = key_node_map_[key];
move_to_head_(node);
return node->value;
}
void put(int key, int value) {
if (key_exists_(key)) {
// key 存在的情况
DLinkedListNode *node = key_node_map_[key];
node->value = value;
move_to_head_(node);
} else {
// key 不存在的情况：
// 1. 如果缓存空间满了，先删除尾节点，再新建节点
// 2. 否则直接新建节点
if (is_full_()) {
DLinkedListNode *tail = dummy_tail_->prev;
remove_node_(tail);
key_node_map_.erase(tail->key);
}
DLinkedListNode *new_node = new DLinkedListNode(key, value);
add_to_head_(new_node);
key_node_map_[key] = new_node;
}
}
private:
unordered_map<int, DLinkedListNode*> key_node_map_;
DLinkedListNode *dummy_head_;
DLinkedListNode *dummy_tail_;
int capacity_;
void move_to_head_(DLinkedListNode *node) {
remove_node_(node);
add_to_head_(node);
};
void add_to_head_(DLinkedListNode *node) {
DLinkedListNode *prev_head = dummy_head_->next;
dummy_head_->next = node;
node->prev = dummy_head_;
node->next = prev_head;
prev_head->prev = node;
};
void remove_node_(DLinkedListNode *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
node->prev = node->next = NULL;
};
bool key_exists_(int key) {
return key_node_map_.count(key) > 0;
};
bool is_full_() {
return key_node_map_.size() == capacity_;
};
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/