题目大意：
LRU缓存机制
运用你所掌握的数据结构，设计和实现一个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
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=146
解题思路：
刚看完这题时有点蒙，并不是因为太难，而是太简单了。该题在leetcode总难易榜上位列14名，一度怀疑是否是自己对题目理解有误。题目要求写一个LRU缓存机制，难道不是一个Map就能解决的问题吗？还是简单分析一下吧。
首先说说什么是LRU，这个名词是不leetcode创造的，它是一种缓存机制，英文是 Least recently used，直译过来是最近最少使用。也就是说最近最少被使用的元素在缓存不足时要被优先删除掉。那么什么是最近最少？白话说就是距离当前时间最久未被使用过的元素。另外，put，get都视为被使用过。
与LRU相关的概念还包括LFU和FIFO，由于与本题无关，就不展开讨论了。给出定义，大家有兴趣可以自己学习下。
- LRU (Least recently used) 最近最少使用，如果数据最近被访问过，那么将来被访问的几率也更高。
- LFU (Least frequently used) 最不经常使用，如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小。
- FIFO (Fist in first out) 先进先出， 如果一个数据最先进入缓存中，则应该最早淘汰掉。
回到本题，题目要求使用 O(1) 时间复杂度内完成get和put两种操作。说白了就是不能用到循环。因此，我们知道List类没有key，所以循环是必须的，而Map类存在key，可以直接取得相应value。不过java中Map类是没有顺序的，所以我们可以考虑使用其子类LinkedHashMap。这样，先加入Map中的元素会排在前面，后加入的会排在末尾，如果get了其中的某个元素，那么我们可以删除Map中的此元素，并将其重新插入Map中，这就能保证Map中最前面的那个元素一定是最久没被访问过的。
大致思路如下：
初始化一个LinkedHashMap<Integer, Integer>对象mCache用于存放所有的缓存数据。
先说get方法。如果mCache中存在该key对应的value，则返回。否则返回-1。不过前文说过了，get一个key就说明此key被使用过，所以应该先删除此元素，再将其重新加入Map中。
再说put方法，先看mCache中是否已经存在该key，如果存在，我们需要更新该key对应的value，也就是将其删除后重新插入到Map中。如果不存在的话，就要考虑直接插入，这样缓存数量会发生改变，我们要先看当前缓存是否达到上限，如果达到，需要先删除一个最古老的数据，然后再执行插入操作。
下面是完整的实现代码。代码很简单，而且上面都已经分析过了，所以就不写注释了。
LinkedHashMap<Integer, Integer> mCache;
int mCapacity = 0;
public LRUCache(int capacity) {
mCache = new LinkedHashMap<>();
mCapacity = capacity;
}
public int get(int key) {
if (mCache.containsKey(key)) {
int value = mCache.get(key);
mCache.remove(key);
mCache.put(key, value);
return mCache.get(key);
}
return -1;
}
public void put(int key, int value) {
if (mCapacity == 0) {
return;
}
if (mCache.containsKey(key)) {
mCache.remove(key);
} else {
if (mCache.size() >= mCapacity) {
Entry<Integer, Integer> entry = mCache.entrySet().iterator().next();
mCache.remove(entry.getKey());
}
}
mCache.put(key, value);
} 本解法用时为87毫秒。
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-146-lru-cache-解题思路分享/