题目：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
链接： http://leetcode.com/problems/lru-cache/
题解：
设计LRU Cache。从题意理解，基本就是设计一个数据结构，要有capacity，get(key)和set(key)。其中每次get(key)之后，被访问的数据要被更新为最新访问，而set(key)主要就是增加或者更新key指向的数据，还要考虑一下容量。 首先想到用Queue和HashMap来存储数据，结果超时了，因为在Queen里的查找使用了O(n)。 应该用Doubly LinkedList，这样可以在O(1)的时间完成get(key)。 另外看Discuss里，Java本身就提供了LinkedHashMap这种API，虽然算是cheating但可以大大简化代码。有关Java的API还是要仔细读一读。还有就是OO Design，Design Patterns，多线程，都要开始学习了。
想一想，这种题，主要就是如何用合适数据结构来存储数据。下面是一些分析：
- Cache hit/miss: 我们要使用一个HashMap来达到O(1)的查找效果
- Get: 我们需要使用一个Doubly Linked List，保存一个自定义结构Node，Node包含key, value, prevNode以及nextNode，主要使用remove以及addLast。最好再使用两个Node - head和tail，用来保存表头和表尾两个节点。
- 假如miss，返回 -1
- 假如hit
- 记录当前结点的value
- 在LinkdedList中remove当前的这个Node(连接前后节点)
- 在LinkedList尾部重新加入这个节点，并且更新这个结点的prev节点为LinkedList的前队尾，更新前队尾的next为当前节点，更新当前节点的next为null
- Set: 跟Get很像，不过要加入一些额外的判断。
- Cache hit: 和get的hit几乎一样，只不过要增加一个步骤，update节点的value值，其余都要做
- Cache miss:
- List.size() < Capacity:
- 增加新节点到队尾
- 更新前后连接
- 增加新节点到map
- List.size() = Capacity
- 移除队首节点，更新前后连接
- 按照List.size() < Capacity的做法来一套
- List.size() < Capacity:
主要就是基本操作都要O(1)才行。 接下来根据逻辑写代码。 写是写完了，也AC了，不过又臭又长，很多重复，还有很多不必要的头尾节点判断。二刷时还要多看discuss，以及好好refactor精简一下，也要好好看看韦斯和塞奇威克的LinkedList实现。
Time Complexity - O(1)， Space Complexity- O(n)。
public class LRUCache {
private Map<Integer, Node> map;
public int capacity;
private Node head;
private Node tail;
public int size;
public LRUCache(int capacity) {
this.map = new HashMap<>();
this.capacity = capacity;
this.size = 0;
}
public int get(int key) {
if(!map.containsKey(key)) {
return -1;
} else {
Node node = map.get(key);
if(head.key == tail.key)
return node.val;
if(node.prev == null && node.next == null)
return node.val;
if(key == tail.key) {
return node.val;
}
if(key == head.key) {
if(head.next != null) {
head = head.next;
head.prev = null;
}
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}
tail.next = node;
node.prev = tail;
node.next = null;
tail = node;
return node.val;
}
}
public void set(int key, int value) {
if(map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
if(head.key == tail.key)
return;
if(node.prev == null && node.next == null)
return;
if(key == tail.key) {
return;
}
if(key == head.key) {
if(head.next != null) {
head = head.next;
head.prev = null;
}
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}
tail.next = node;
node.prev = tail;
node.next = null;
tail = node;
} else { //need to add new node
if(this.size == this.capacity) {
int headKey = head.key;;
if(head.key == tail.key) {
head = null;
tail = null;
} else {
if(head.next != null) {
head = head.next;
head.prev = null;
}
}
map.remove(headKey);
size--;
}
Node newNode = new Node(key, value);
map.put(key, newNode);
if(head == null || tail == null) {
head = newNode;
tail = newNode;
size++;
return;
}
tail.next = newNode;
newNode.prev = tail;
newNode.next = null;
tail = newNode;
size++;
}
}
private class Node {
public Node prev;
public Node next;
public int key;
public int val;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
}
题外话：
11/1/2015 - 这几天朋友推荐了琅琊榜看。一看就不可收拾了，下班回家就是三四集，周末也是整天看。也好，赶紧看完了好好继续做题。
11/2/2015 - Node到底是结点还是节点??? 昨天又忙了一天，5点不到就去JFK接老朋友，晚上11点半才到家，累屎了。不过拿到了很多好吃的和一些购买的资料，多谢老友。不过可惜都是在双11前购买的，否则可以打个半折。
二刷
又做到这题，已经过了很久很久了... 方法还是跟上面一样，稍微简写了一点。
- 主要思路仍然是使用HashMap和Doubly LinkedList。这个Doubly LinkedList我们可以另写一个private class Node。在Node class里面记录前面和后面两个节点，以及key和value。
- 我们要保存一个global的map，以及这个双链表的head和tail。
- Get操作:
- 当key不在HashMap中返回-1
- 当key在HashMap中，我们取得这个node，将node移动到双链表尾部，返回node.val
- Set操作:
- 当key在HashMap中，我们取得这个node，更新node.val，将node移动到双链表尾部
- 否则我们用map.size()和capacity来检查是否cache容量已满
- 假如已满，我们从map和双链表中移除首节点，再从尾部添加新节点。
- 从双链表中移除使用了head = head.next，然后新的head非空时head.prev = null。
- 当新的head为空时，说明之前的head = tail，这时我们也设tail = null。
- 否则我们直接从尾部添加新节点
- 将新节点加入到map中
- 假如已满，我们从map和双链表中移除首节点，再从尾部添加新节点。
- 我们可以另写一个moveToTail()方法来将node移动到尾部，或是从尾部添加新节点。这里需要注意的点如下
- head和tail均为空，我们直接设置head = node, tail = node并且返回
- 当map中包含node.key时，说明这不是一个新节点。我们要先处理其在双链表中的前节点和后节点，再将其加入到双链表尾部并更新tail。要注意如下：
- node = tail，我们并不用做改变，直接return
- node = head，我们更新head，并且设置新head.prev = null
- 否则node既又前节点，又有后节点，我们将node.prev和node.next连接
- 执行下一步 (将node加入到双链表尾部并且更新tail)
- 否则，这是一个新节点，我们将其加入到双链表尾部，并且更新tail
Java:
Time Complexity - O(1)， Space Complexity- O(n)。 n = capacity
public class LRUCache {
private Map<Integer, Node> map;
private Node head, tail;
private int capacity = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>();
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
moveToTail(node);
return node.val;
}
public void set(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
moveToTail(node);
} else {
if (map.size() == capacity) {
map.remove(head.key);
head = head.next;
if (head != null) head.prev = null;
else tail = null;
}
Node node = new Node(key, value);
moveToTail(node);
map.put(key, node);
}
}
private void moveToTail(Node node) {
if (head == null && tail == null) {
head = node;
tail = node;
return;
}
if (map.containsKey(node.key)) {
if (node == tail) return; // node is tail
if (node == head) { // node is head;
head = head.next;
head.prev = null;
} else {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}
node.prev = tail;
tail.next = node;
node.next = null;
tail = node;
}
private class Node {
int key;
int val;
Node prev;
Node next;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
}
三刷:
简化了一下对head和tail的处理，建立固定的双链表头尾head和node
class LRUCache {
private Map<Integer, Node> map;
private Node head, tail;
private int capacity = 0;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new HashMap<>(capacity);
this.head = new Node(-1, 1);
this.tail = new Node(-1, 1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!map.containsKey(key)) return -1;
Node node = map.get(key);
moveNodeToTail(node);
return node.val;
}
public void put(int key, int value) {
if (map.containsKey(key)) {
Node node = map.get(key);
node.val = value;
moveNodeToTail(node);
} else {
if (map.size() == capacity) removeNode(head.next);
Node node = new Node(key, value);
addNodeAtTail(node);
}
}
private void removeNode(Node node) {
map.remove(node.key);
node.next.prev = node.prev;
node.prev.next = node.next;
}
private void addNodeAtTail(Node node) {
map.put(node.key, node);
tail.prev.next = node;
node.prev = tail.prev;
node.next = tail;
tail.prev = node;
}
private void moveNodeToTail(Node node) {
removeNode(node);
addNodeAtTail(node);
}
private class Node {
int key;
int val;
Node prev;
Node next;
public Node(int k, int v) {
this.key = k;
this.val = v;
}
}
}
Reference：
http://www.cnblogs.com/springfor/p/3869393.html
http://algorithmsandme.in/2014/02/least-recently-used-cache/
https://leetcode.com/discuss/26560/java-solution-with-doubly-linked-list-hash-map
https://leetcode.com/discuss/16010/o-1-java-solution
https://leetcode.com/discuss/20139/java-hashtable-double-linked-list-with-touch-of-pseudo-nodes
https://leetcode.com/discuss/13964/accepted-c-solution-296-ms
https://leetcode.com/discuss/8645/my-o-1-solution-in-java
https://leetcode.com/discuss/42891/probably-the-best-java-solution-extend-linkedhashmap
https://leetcode.com/discuss/1188/java-is-linkedhashmap-considered-cheating
https://en.wikipedia.org/wiki/Cache_algorithms