题目地址: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
网友评论