题目链接 : https://leetcode-cn.com/problems/lru-cache/
题目描述:
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
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
思路:
思路一:
使用python里的有序字典OrderedDict
注释写在代码里, 这个一定要理解, 因为思路二也是这样想的,只不过换了数据结构!
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.maxsize = capacity
self.lrucache = OrderedDict()
def get(self, key: int) -> int:
# 说明在缓存中,重新移动字典的尾部
if key in self.lrucache:
self.lrucache.move_to_end(key)
return self.lrucache.get(key, -1)
def put(self, key: int, value: int) -> None:
# 如果存在,删掉,重新赋值
if key in self.lrucache:
del self.lrucache[key]
# 在字典尾部添加
self.lrucache[key] = value
if len(self.lrucache) > self.maxsize:
# 弹出字典的头部(因为存储空间不够了)
self.lrucache.popitem(last = False)
思路二: 哈希 + 双向链表
也很好理解!
# 创建双向链表
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
# 构建首尾节点, 使之相连
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
self.lookup = dict()
self.max_len = capacity
def get(self, key: int) -> int:
if key in self.lookup:
node = self.lookup[key]
self.remove(node)
self.add(node)
return node.val
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.lookup:
self.remove(self.lookup[key])
if len(self.lookup) == self.max_len:
# 把表头位置节点删除(说明最近的数据值)
self.remove(self.head.next)
self.add(Node(key, value))
# 删除链表节点
def remove(self, node):
del self.lookup[node.key]
node.prev.next = node.next
node.next.prev = node.prev
# 加在链表尾
def add(self, node):
self.lookup[node.key] = node
pre_tail = self.tail.prev
node.next = self.tail
self.tail.prev = node
pre_tail.next = node
node.prev = pre_tail
java
class LRUCache {
Node head = new Node(0, 0), tail = new Node(0, 0);
Map<Integer, Node> map = new HashMap<>();
int max_len;
public LRUCache(int capacity) {
max_len = capacity;
// 建立双链表
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
add(node);
return node.value;
} else
return -1;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
remove(map.get(key));
}
// 把表头位置节点删除(说明最近的数据值)
if (map.size() == max_len) {
remove(head.next);
}
add(new Node(key, value));
}
// 删除链表
private void remove(Node node) {
map.remove(node.key);
// 删除节点
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 加在链表尾
private void add(Node node) {
map.put(node.key, node);
Node pre_tail = tail.prev;
node.next = tail;
tail.prev = node;
pre_tail.next = node;
node.prev = pre_tail;
}
// 创建双向链表
class Node {
Node prev, next;
int key, value;
Node(int _key, int _value) {
key = _key;
value = _value;
}
}
}