LEETCODE 146. LRU Cache 解题思路分享

题目大意：

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-解题思路分享/