LintCode 134. LRU Cache 原创Java参考解答
问题描述
http://www.lintcode.com/en/problem/lru-cache/
Implement a stack with min() function, which will return the smallest number in the stack.
It should support push, pop and min operation all in O(1) cost.
Notice
min operation will never be called if there is no number in the stack.
解题思路
经典的算法问题：LRU Cache，设计最近最少使用缓存。
最近最少使用缓存（LRU）需要两个操作：获取数据（get）和写入数据（set）。
- 获取数据get(key)：如果缓存中存在key，则获取其数据值，否则返回-1。
- 写入数据set(key, value)：如果key还没有在缓存中，则写入其数据值。当缓存达到容量上限，它应该在写入新数据之前，删除最近最少使用的过往数据来腾出空闲位置。
常见的LRU Cache实现方法：双向链表(Doubly Linked List) + HashMap。
LRU的实质是按照节点访问时间顺序排列的双向链表。每个双向链表节点有prev和next指向其一前一后的节点。最近被访问的节点放置在链表头部。一旦链表达到容量，需要剔除元素的时候，踢出链表尾部的最老时间被访问过的元素。
HashMap则是用来根据key来找对应的链表节点。
HashMap则是用来根据key来找对应的链表节点。
参考代码
public class Solution {
private class Node {
int key;
int value;
Node prev;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
private int capacity;
private HashMap<Integer, Node> map;
private Node head = new Node(-1, -1);
private Node tail = new Node(-1, -1);
// @param capacity, an integer
public Solution(int capacity) {
this.capacity = capacity;
this.map = new HashMap<Integer, Node>();
tail.prev = head;
head.next = tail;
}
// @return an integer
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
} else {
Node current = map.get(key);
remove(current);
setHead(current);
return map.get(key).value;
}
}
// @param key, an integer
// @param value, an integer
// @return nothing
public void set(int key, int value) {
if (get(key) != -1) {
map.get(key).value = value;
return;
}
// if reaches capacity, remove oldest cache
if (map.size() == capacity) {
map.remove(tail.prev.key);
remove(tail.prev);
}
// insert
Node insert = new Node(key, value);
map.put(key, insert);
setHead(insert);
}
private void remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void setHead(Node node) {
node.next = head.next;
head.next.prev = node;
head.next = node;
node.prev = head;
}
}