146.LRU(Least Recently Used)缓存-编程思维

146.LRU(Least Recently Used)缓存

题目

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:

  • LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
    函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例:

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示:

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

这个结构需要满足什么?

  1. 首先需要有顺序区分,当capacity满了之后,最近最少使用需要被踢出去,最近使用的元素应该排在最后面。
    首先想到了队列,没有使用的在最前面。但是本次使用过的需要在最后面,使用队列如果该元素在中间不好出队。
    然后想到了链表,当capacity满了之后,尾节点先出去。如果使用的元素是链表中的元素,修改该节点的位置到首节点,这个是很容易的。

  2. 该结构可以存储key-value,put 和 get 方法的时间复杂度为 O(1)
    这个一下想到了Map结构,Map的查询速度很快。链表删除快,但查找慢。综合来说,该结构类似LinkedHashMap:在原有的HashMap底层结构基础上添加了一对指针,指向前一个和后一个元素。
    LinkedHashMap的实现

这里就想到了两个问题

  1. LinkedHashMap是双向指针,可以只使用单个指针吗?
    因为我们需要删除节点/修改节点位置,那么删除节点需要知道它的前驱节点。而双向链表才能支持直接查找前驱,保证操作的时间复杂度 O(1)。
  2. 哈希表已经记录了key,链表不可以只记录val吗?
    在删除最后一个节点的时候,还需要把哈希表中的key一起删除,所以要利用链表的节点的key找到哈希表中的key,这样在可以把哈希表中的key一起删除。

创建一个双向链表的操作

//先创建一个双向链表的节点类
class Node {
    public int key, val;
    public Node next, prev;
    public Node(int k, int v) {
        this.key = k;
        this.val = v;
    }
}
class DoubleList {

private int size;
private Node dummy = new Node(0,0);
private Node tail = new Node(0,0);

//构造器,初始化双向链表
private DoubleList() {
     dummy.next = tail;
     tail.prev = dummy;
     size = 0;
}

//在链表的头部添加节点,O(1)
//节点被访问就需要调用
public void addFirst(Node node){
	Node tmp = dummy.next;
	dummy.next = node;
	node.prev = dummy;
	node.next = tmp;
	tmp.prev = node;
	++size;
}

// 删除链表中的 x 节点(x 一定存在)
//put操作修改节点值时,需要把该节点移到头节点
// 由于是双链表且给的是目标 Node 节点,时间 O(1)
public void remove(Node node){
	node.prev.next = node.next;
	node.next.prev = node.prev;
	--size;
}

// 删除链表中最后一个节点,并返回该节点,时间 O(1)
public Node removeLast(){
	//当链表为空时不可以删除
	if(size==0)return;
	Node last = tail.prev;
	remove(last); //这里自带了size--
	return last;
}

// 返回链表长度,时间 O(1)
public int size(){
	return size;
}
}

双向链表的操作写完了,接下来需要实现这个LRUCache

get(int key):如果哈希表中没有key返回-1,如果有返回值,并修改节点位置到链表头。
void put(int key, int value)
先判断这个key是否已经存在

  • 不存在,判断LRUCache是否满了,没满创建Node加入链表与创建哈希映射。LRUCache满了,则先删除最后一个元素,再创建Node加入链表与创建哈希映射。
  • 如果已经存在了,修改val值,并修改节点位置。
class LRUCache {

	HashMap<Integer,Node> map;	//创建哈希表
	DoubleList doubleList; //创建双向链表
	private int capacity;	//代表LRU容量
    public LRUCache(int capacity) {
		this.capacity = capacity;
		doubleList = new DoubleList();
		map = new HashMap<>();
    }

    public int get(int key) {
		//如果哈希表中没有这个key返回null
		if(!map.containsKey(key)) return -1;
		//如果存在,则返回该节点的val,并修改节点位置
		Node cur = map.get(key);
		//这里访问了节点,需要把节点放在头节点
		doubleList.remove(cur);//先删除
		doubleList.addFirst(cur);//再修改位置
		return cur.val;
    }
    public void put(int key, int value) {
		Node cur = map.getOrDefault(key,null);
		if(cur!=null){
			cur.val = value;
			doubleList.remove(n);//先删除
			doubleList.addFirst(n);//再修改位置
			 map.put(key, n); //修改映射位置
		}else{ //节点不存在
			if(doubleList.size()==capacity){
				//满了则先删除最后一个元素,再修改映射
				Node last = doubleList.removeLast();
				map.remove(last.key);
			}//创建Node加入链表与创建哈希映射。
				Node n = new Node(key,value);
				doubleList.addFirst(n);
				map.put(key,n);
		}
    }
}

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/rananie/p/15759063.html