Java
package leetcode.template;
import java.util.HashMap;
import java.util.Map;
class LRUCache {
/**
* 缓存映射表
*/
private Map<Integer, DLinkNode> cache = new HashMap<>();
/**
* 缓存大小
*/
private int size;
/**
* 缓存容量
*/
private int capacity;
/**
* 链表头部和尾部
*/
private DLinkNode head, tail;
public LRUCache(int capacity) {
//初始化缓存大小,容量和头尾节点
this.size = 0;
this.capacity = capacity;
head = new DLinkNode();
tail = new DLinkNode();
head.next = tail;
tail.prev = head;
}
/**
* 获取节点
* @param key 节点的键
* @return 返回节点的值
*/
public int get(int key) {
DLinkNode node = cache.get(key);
if (node == null) {
return -1;
} //移动到链表头部 (node);
return node.value;
}
/**
* 添加节点
* @param key 节点的键
* @param value 节点的值
*/
public void put(int key, int value) {
DLinkNode node = cache.get(key);
if (node == null) {
DLinkNode newNode = new DLinkNode(key, value);
cache.put(key, newNode); //添加到链表头部
addToHead(newNode);
++size; //如果缓存已满,需要清理尾部节点
if (size > capacity) {
DLinkNode tail = removeTail();
cache.remove(tail.key);
--size;
}
} else {
node.value = value; //移动到链表头部
moveToHead(node);
}
}
/**
* 删除尾结点 *
* @return 返回删除的节点
*/
private DLinkNode removeTail() {
DLinkNode node = tail.prev;
removeNode(node);
return node;
}
/**
* 删除节点
* @param node 需要删除的节点
*/
private void removeNode(DLinkNode node) {
node.next.prev = node.prev;
node.prev.next = node.next;
}
/**
* 把节点添加到链表头部 *
* @param node 要添加的节点
*/
private void addToHead(DLinkNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
/**
* 把节点移动到头部
* @param node 需要移动的节点
*/
private void moveToHead(DLinkNode node) {
removeNode(node);
addToHead(node);
}
/**
* 链表节点类
*/
private static class DLinkNode {
Integer key;
Integer value;
DLinkNode prev;
DLinkNode next;
DLinkNode() {
}
DLinkNode(Integer key, Integer value) {
this.key = key;
this.value = value;
}
}
}
Python
class LRUCache(object):
def __init__(self, capacity):
self.dic = collections.OrderedDict()
self.remain = capacity
def get(self, key):
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, value):
if key in self.dic:
self.dic.pop(key)
else:
if self.remain > 0:
self.remain -= 1
else:
self.dic.popitem(last=False)
self.dic[key] = value
评论区