leetcode 146. 实现LRU缓存机制
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果** (key) 存在于缓存中,则获取**的值(总是正数),否则返回 -1。
写入数据 put(key, value) - 如果**已经存在,则变更其数据值;如果**不存在,则插入该组「**/数据值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作?
题解:
1.实现一个 LRU (最近最少使用) 缓存机制
2.包括两个功能get和put
3.get通过key获取值;不存在该key返回 -1
4.put放入key, value;key存在更新value;不存在插入key, value
5.缓存容量达到上限,删除最久未使用的key, value放入新key, value
示例:
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
解题思路:双链表+哈希表
-
双链表存储key, value对,哈希表存储key->(key, value)的映射
-
使用get时先访问哈希表有无相应映射关系,不存在返回-1
-
若存在,则把key, value移到双链表头部作为最近使用的。然后再返回key对应的value
-
使用put时,判断是否存在key?不存在,判断存放key, value的双链表容量是否满了?满了删除链表尾部的key, value注意映射也要删除
-
双链表容量不满直接把key, value添加到头部,同时哈希表添加映射
-
如果查询映射key存在,则把存放key, value的双链表对应调到头部,更新key对应的值,同时更改映射关系
C/C++题解:
class LRUCache {
private:
int cap;
list<pair<int, int>> cache;// 双链表:装着 (key, value) 元组
// 哈希表:key 映射到 (key, value) 在 cache 中的位置
unordered_map<int, list<pair<int, int>>::iterator> map;
public:
LRUCache(int capacity) { this->cap = capacity; }
int get(int key) {
auto it = map.find(key);
// 访问的 key 不存在
if (it == map.end()) return -1;
// key 存在,把 (k, v) 换到队头
pair<int, int> kv = *map[key];
cache.erase(map[key]);
cache.push_front(kv);
// 更新 (key, value) 在 cache 中的位置
map[key] = cache.begin();
return kv.second; }// value
void put(int key, int value) {
/* 要先判断 key 是否已经存在 */
auto it = map.find(key);
if (it == map.end()) {
/* key 不存在,判断 cache 是否已满 */
if (cache.size() == cap) {
// cache 已满,删除尾部的键值对腾位置
// cache 和 map 中的数据都要删除
auto lastPair = cache.back();
int lastKey = lastPair.first;
map.erase(lastKey);
cache.pop_back();}
cache.push_front(make_pair(key, value));// cache 没满,可以直接添加
map[key] = cache.begin();
} else {
/* key 存在,更改 value 并换到队头 */
cache.erase(map[key]);
cache.push_front(make_pair(key, value));
map[key] = cache.begin();}}};
Debug结果:
Java题解:
class LRUCache {
class Node {
public int key, val;
public Node next, prev;
public Node(int k, int v) {
this.key = k;
this.val = v;}}
// Node(k1, v1) <-> Node(k2, v2)...
private DoubleList cache;
// key -> Node(key, val)
private HashMap<Integer, Node> map;
// 最大容量
private int cap;
public LRUCache(int capacity) {
this.cap = capacity;
map = new HashMap<>();
cache = new DoubleList();}
public int get(int key) {
if (!map.containsKey(key))
return -1;
int val = map.get(key).val;
// 利用 put 方法把该数据提前
put(key, val);
return val;}
public void put(int key, int val) {
// 先把新节点 x 做出来
Node x = new Node(key, val);
if (map.containsKey(key)) {
// 删除旧的节点,新的插到头部
cache.remove(map.get(key));
cache.addFirst(x);
// 更新 map 中对应的数据
map.put(key, x);
} else {
if (cap == cache.size()) {
// 删除链表最后一个数据
Node last = cache.removeLast();
map.remove(last.key);}
// 直接添加到头部
cache.addFirst(x);
map.put(key, x);}}
public class DoubleList {
private Node head, tail; // 头尾虚节点
private int size; // 链表元素数
public DoubleList() {
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
size = 0;}
// 在链表头部添加节点 x
public void addFirst(Node x) {
x.next = head.next;
x.prev = head;
head.next.prev = x;
head.next = x;
size++;}
// 删除链表中的 x 节点(x 一定存在)
public void remove(Node x) {
x.prev.next = x.next;
x.next.prev = x.prev;
size--;}
// 删除链表中最后一个节点,并返回该节点
public Node removeLast() {
if (tail.prev == head)
return null;
Node last = tail.prev;
remove(last);
return last;}
// 返回链表长度
public int size() { return size; }}}
Debug结果:
Python题解:
class DLinkedNode:#双链表节点:装着 (key, value) 元组
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.cache = dict() #双链表存放(key, value)
# 使用伪头部和伪尾部节点
self.head = DLinkedNode()#初始化头尾节点
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.size = 0
def get(self, key):
if key not in self.cache:
return -1 #访问的 key 不存在
# key 存在,把 (k, v) 换到队头
node = self.cache[key]
self.moveToHead(node)
return node.value
def put(self, key, value):
if key not in self.cache:
# 如果 key 不存在,创建一个新的节点
node = DLinkedNode(key, value)
# 哈希表记录下映射
self.cache[key] = node
# 添加至双向链表的头部
self.addToHead(node)
self.size += 1 #双链表大小增加
if self.size > self.capacity:
# 如果超出容量,删除双向链表的尾部节点
removed = self.removeTail()
# 删除哈希表中映射
self.cache.pop(removed.key)
self.size -= 1 #双链表长度减1
else:
# key 存在,更改 value 并换到队头
node = self.cache[key]
node.value = value
self.moveToHead(node)
def addToHead(self, node): #节点加到头部
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def removeNode(self, node):#删除节点
node.prev.next = node.next
node.next.prev = node.prev
def moveToHead(self, node):#已有节点移到头部
self.removeNode(node)
self.addToHead(node)
def removeTail(self): #从尾部删除(k,v)
node = self.tail.prev
self.removeNode(node)
return node
Debug结果:
更多题解移步公众号免费获取