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-解题思路分享/
此条目发表在leetcode分类目录,贴了, , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。