官方链接
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解法一
class LRUCache {
class Entry {
int key;
int value;
Entry pre;
Entry next;
Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
private final int capacity;
private HashMap<Integer, Entry> m;
Entry head;
Entry tail;
public LRUCache(int capacity) {
this.capacity = capacity;
m = new HashMap<Integer, Entry>((int)(capacity / 0.75 + 1), 0.75f);
head = new Entry(0, 0);
tail = new Entry(0, 0);
head.next = tail;
tail.pre = head;
}
public int get(int key) {
if(!m.containsKey(key)) return -1;
Entry entry = m.get(key);
popToTail(entry);
return entry.value;
}
public void put(int key, int value) {
if(m.containsKey(key)) {
Entry entry = m.get(key);
entry.value = value;
popToTail(entry);
return;
}
Entry entry = new Entry(key, value);
if(m.size() >= capacity) {
Entry first = removeFirst();
m.remove(first.key);
}
addToTail(entry);
m.put(key, entry);
}
private void popToTail(Entry entry) {
Entry pre = entry.pre;
Entry next = entry.next;
pre.next = next;
next.pre = pre;
Entry last = tail.pre;
last.next = entry;
entry.pre = last;
entry.next = tail;
tail.pre = entry;
}
private void addToTail(Entry entry) {
Entry last = tail.pre;
last.next = entry;
entry.pre = last;
entry.next = tail;
tail.pre = entry;
}
private Entry removeFirst() {
Entry first = head.next;
Entry second = first.next;
head.next = second;
second.pre = head;
return first;
}
}
/**
* 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);
*/
python3.6+ 实现了 pep-0468:
from collections import OrderedDict
class LRUCache(OrderedDict):
def __init__(self, capacity: int):
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self:
return -1
self.move_to_end(key)
return self[key]
def put(self, key: int, value: int) -> None:
if key in self:
self.move_to_end(key)
self[key] = value
if len(self) > self.capacity:
self.popitem(last=False)
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
class LRUCache:
def __init__(self, capacity: int):
self.dic = collections.OrderedDict()
self.remain = capacity
def get(self, key: int) -> int:
if key not in self.dic:
return -1
v = self.dic.pop(key)
self.dic[key] = v # key as the newest one
return v
def put(self, key: int, value: int) -> None:
if key in self.dic:
self.dic.pop(key)
else:
if self.remain > 0:
self.remain -= 1
else: # self.dic is full
self.dic.popitem(last = False)
self.dic[key] = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
解法二 LinkedHashMap
class LRUCache {
private LinkedHashMap<Integer, Integer> map;
private final int capacity;
public LRUCache(final int capacity) {
this.capacity = capacity;
map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return this.size() > capacity;
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
}
}
/**
* 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);
*/