题目地址：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
试题分析：
这道题考察的是链表的一个综合应用，LRU算法大家都知道，核心思想就是当LRUCache中命中的时候返回该值，并将该值移到LRU链表的头节点，如果没有命中返回异常值；在向LRUCache中put值时需要判断Cache中有没有该值，如果已经有了则返回该值并将该值放到链表头，如果没有该值则要判断链表有没有满，如果链表已满则删除链表尾的节点再将新节点插入链表头，如果链表未满则直接插入到链表头。
整个过程听起来不难，不过在实现过程中，光有一个LRU链表的话实现起来没法做到O(1)，我们都知道在链表中查找值是O(n)的时间复杂度，无法做到O(1),这里就需要借助于一个HashMap，将链表中所有的cache节点都放在HashMap中，在每次对LRUCache进行操作的时候都需要先通过HashMap进行判断在cache中是否已经包含该值，HashMap的随机读时间复杂度是O(1)。具体代码逻辑可以直接看下面代码实现，逻辑就是上面提到的算法思路。
代码：
public class LRUCache_146 {
private List<CacheNode> cacheList;
private Map<Integer, CacheNode> cacheMap;
private int capacity;
public LRUCache_146(int capacity) {
cacheList = new LinkedList<CacheNode>();
cacheMap = new HashMap<Integer, CacheNode>(capacity);
this.capacity = capacity;
}
public int get(int key) {
if(cacheMap.containsKey(key)){
cacheList.remove(cacheMap.get(key));
cacheList.add(0, cacheMap.get(key));
return cacheMap.get(key).value;
}else{
return -1;
}
}
public void put(int key, int value) {
if(cacheMap.containsKey(key)){
cacheList.remove(cacheMap.get(key));
cacheList.add(0, cacheMap.get(key));
}else{
//如果cache中没有该值则插入
if(cacheMap.size()==capacity){
//cache已满则需要先删除末尾节点再将新值插入队头
cacheMap.remove(cacheList.get(cacheList.size()-1).key);
cacheList.remove(cacheList.size()-1);
CacheNode node = new CacheNode(key,value);
cacheMap.put(key, node);
cacheList.add(0, node);
}else{
CacheNode node = new CacheNode(key,value);
cacheMap.put(key, node);
cacheList.add(0, node);
}
}
}
private class CacheNode{
int key;
int value;
public CacheNode(int key, int value){
this.key = key;
this.value = value;
}
}
}
源码路径：com.monkey01.linkedlist.LRUCache_146
配套测试代码路径：test目录com.monkey01.linkedlist.LRUCache_146Test
