146J. LRU Cache
https://leetcode.com/problems/lru-cache/
LRU Cache 是一道很高频的题目，非常重要。
它本身的意义就是为了学习 LinkedHashMap/OrderedDict
这个数据结构。而这个数据结构的存在最典型的应用就是LRU Cache，
所以真的是非常重要。
LRU的意思是Least Recently Used Cache.
相关的题目还有 460 LFU Cache Least Frequently Used Cache
这是介绍各种Cache的Wikipedia。
https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU
可以暂时不太学习 LinkedHashMap在Java中是怎么实现的，但是此题
的解决方案实际上是差不多的。
以下是两个中文讲解LinkedHashMap的文章
https://juejin.im/post/5a4b433b6fb9a0451705916f
https://blog.csdn.net/justloveyou_/article/details/71713781Method 1 Double LinkedList + HashMap
如果不考虑时间复杂度O(1)的要求，仅仅实现LRU，
思路是这样的，先创建一个DoubleLinkedList，因此我们需要
定义DoubleLinkedList，和传统的不同的是，我们需要给每个Node两个值，
一个Key, 一个Val. 定不定义Constructor不重要。
我们看这个双向链表是怎么实现LRU的呢？
我们先建立一个dummyHead和一个dummyTail。由于是双向链表，所以不可能只
创建一个dummyHead。如果新加入了节点，就加在头部之后。那么最靠近尾部的
就是Least Recent Used的Node。
因此我们首先需要写一个函数addNode，用来在dummyHead之后加节点。
然后如果一个已经存在的节点重新被使用了怎么办呢？我们应该找到这个节点
并把它移动到头部之后。因此我们需要写两个空返回类型函数，一个是removeNode,
用来删掉该节点。一个是moveToHead来实现这个过程，其实现方式是，先
用removeHead删掉它，再用addNode把它加到dummyHead之后。
所以针对双向链表我们需要实现三个空返回类型的函数：
addNode, removeNode, moveToHead. 这三个都是对链表做一些修改的函数。
如果我们加入了新的本来不存在的值，导致我们的双向链表现在有了N+1个Node，
这就意味着我们的Cache需要删掉一些东西，即删掉LRU。
那么我们就直接删掉最靠近尾部的Node即可. 需要一个函数popTail.
为什么是PopTail并返回该节点？
因为为了实现O(1)的时间复杂度从链表删去节点的同时，还要照顾我们的HashMap。
为了实现O(1),自然而然的会想到使用HashMap。我们用HashMap的Key直接取到
双向链表的对应的Node，自然可以从Node中读取Val。这就可以实现get的O(1).
当然，get这件事本身就相当于用了一次对应Node，还要用moveToHead
把这个Node给提到最前面去。
那么put如何O(1)呢？其实put本来就是O(1)的，这是链表实现保证的。只需要处理
一下添加了Node之后的一些情况。这部分是最为平庸的。
因此我们的LRU除了双向链表之外，
类变量还需要有size,capacity,链表头尾，和一个HashMap。以下的代码基本上就是上面叙述的部分了。
class LRUCache {
// Doublely Linked List
// Define Doubly Linked List
class DLListNode{
public int key; // for LRU
// Standard
public int val;
public DLListNode next;
public DLListNode prev;
}
public void addNode(DLListNode node){
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
public void remove(DLListNode node){
node.next.prev = node.prev;
node.prev.next = node.next;
// 为什么不必要以下两句呢？因为没必要让node被回收，
// remove只在moveToHead中使用，一会儿还要addnode呢。
// 当然加上以下两句也不会报错
// node.next = null;
// node.prev = null;
}
public void moveToHead(DLListNode node){
remove(node);
addNode(node);
}
//为何popTail要返回节点？因为还要从HashMap里删掉该节点的信息
public DLListNode popTail(){
DLListNode poped = tail.prev;
remove(poped);
return poped;
}
// For LRU Cache
private int size;
private int capacity;
private DLListNode head;
private DLListNode tail;
private Map<Integer, DLListNode> cache;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLListNode();
tail = new DLListNode();
head.next = tail;
tail.prev = head;
cache = new HashMap<Integer, DLListNode>();
}
public int get(int key) {
DLListNode node = cache.get(key);
if(node == null) return -1;
moveToHead(node);
return node.val;
}
public void put(int key, int value) {
DLListNode node = cache.get(key);
if(node!=null){
node.val = value;
moveToHead(node);
} else{
node = new DLListNode();
node.key = key;
node.val = value;
addNode(node);
size++;
cache.put(key,node);
if(size > capacity){
DLListNode poped = popTail();
cache.remove(poped.key);
size--;
}
}
}
}以下是答案
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
}
private void addNode(DLinkedNode node) {
/**
* Always add the new node right after head.
*/
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node){
/**
* Remove an existing node from the linked list.
*/
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(DLinkedNode node){
/**
* Move certain node in between to the head.
*/
removeNode(node);
addNode(node);
}
private DLinkedNode popTail() {
/**
* Pop the current tail.
*/
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
// head.prev = null;
tail = new DLinkedNode();
// tail.next = null;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) return -1;
// move the accessed node to the head;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
++size;
if(size > capacity) {
// pop the tail
DLinkedNode tail = popTail();
cache.remove(tail.key);
--size;
}
} else {
// update the value.
node.value = value;
moveToHead(node);
}
}
}这是我最新写的，感觉不错的。比上面的标准答案好多了。 对于 DLList 我们只实际上实现 addToHead 和 remove 两个方法就可以。
class LRUCache {
class Node {
int key;
int val;
Node prev;
Node next;
public Node() {};
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
class DLList{
Node head;
Node tail;
int size;
public DLList(){
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
this.head.next = this.tail;
this.tail.prev = this.head;
this.size = 0;
};
public Node remove(Node node) {
Node prev = node.prev;
Node next = node.next;
prev.next = next;
next.prev = prev;
this.size -= 1;
return node;
}
public void add(Node node) {
Node next = head.next;
node.prev = head;
node.next = next;
head.next = node;
next.prev = node;
this.size += 1;
}
public Node getLast() {
return this.tail.prev;
}
}
private int capacity;
private Map<Integer, Node> map;
private DLList list;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
this.list = new DLList();
}
public int get(int key) {
if( !map.containsKey(key) ) {
return -1;
}
Node node = map.get(key);
update(node);
return node.val;
}
public void put(int key, int value) {
if( map.containsKey(key) ) {
map.get(key).val = value;
update(map.get(key));
return;
}
Node node = new Node(key, value);
map.put(key, node);
list.add(node);
while(map.size() > capacity) {
Node last = list.remove( list.getLast() );
map.remove( last.key );
}
}
public void update(Node node) {
list.add( list.remove(node) );
}
}
/**
* 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);
*/Last updated
Was this helpful?