1.题目描述
设计LRU(最近最少使用)缓存结构,该结构在构造时确定大小,假设大小为 capacity ,操作次数是 n ,并有如下功能:
1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. get(key):如果关键字 key 存在于缓存中,则返回key对应的value值,否则返回 -1 。
3. set(key, value):将记录(key, value)插入该结构,如果关键字 key 已经存在,则变更其数据值 value,如果不存在,则向缓存中插入该组 key-value ,如果key-value的数量超过capacity,弹出最久未使用的key-value提示:
1.某个key的set或get操作一旦发生,则认为这个key的记录成了最常使用的,然后都会刷新缓存。
2.当缓存的大小超过capacity时,移除最不经常使用的记录。
3.返回的value都以字符串形式表达,如果是set,则会输出"null"来表示(不需要用户返回,系统会自动输出),方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value,下面说明的缓存里key用""号包裹数据范围:
1≤capacity<=1051≤capacity<=105
0≤key,val≤2×109 0≤key,val≤2×109
1≤n≤1051≤n≤105
示例1
输入:
["set","set","get","set","get","set","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2返回值:
["null","null","1","null","-1","null","-1","3","4"]说明:
我们将缓存看成一个队列,最后一个参数为2代表capacity,所以 Solution s = new Solution(2); s.set(1,1); //将(1,1)插入缓存,缓存是{"1"=1},set操作返回"null" s.set(2,2); //将(2,2)插入缓存,缓存是{"2"=2,"1"=1},set操作返回"null" output=s.get(1);// 因为get(1)操作,缓存更新,缓存是{"1"=1,"2"=2},get操作返回"1" s.set(3,3); //将(3,3)插入缓存,缓存容量是2,故去掉某尾的key-value,缓存是{"3"=3,"1"=1},set操作返回"null" output=s.get(2);// 因为get(2)操作,不存在对应的key,故get操作返回"-1" s.set(4,4); //将(4,4)插入缓存,缓存容量是2,故去掉某尾的key-value,缓存是{"4"=4,"3"=3},set操作返回"null" output=s.get(1);// 因为get(1)操作,不存在对应的key,故get操作返回"-1" output=s.get(3);//因为get(3)操作,缓存更新,缓存是{"3"=3,"4"=4},get操作返回"3" output=s.get(4);//因为get(4)操作,缓存更新,缓存是{"4"=4,"3"=3},get操作返回"4"
2.解题思路
本题最关键的是我们需要一个数据结构,能让本次get/set的元素调整到最新访问的位置,并且以O(1)的时间复杂度找到最近最少使用的结点。
可以通过hashMap+双向链表的数据结构实现这个功能,例如当前get(key)已经存在,我们就现在双向链表和map中都删除掉这个 结点,然后再把这个结点加入到双向链表的表尾,表示最新访问过;如果put(key,val)中的key已经存在,也是需要先删除再重新加入,保证此次访问过后,这个结点就在最新访问的位置,如果Map中元素个数已经等于capacity,那就先删除最久未使用的那个结点,再加入新结点。
注:使用双向链表,只需要我们把要删除的结点当作形参传入,我们就可以以O(1)的复杂度找到它的前驱结点和后序结点,完成对该点的删除;同理,插入操作都是将结点插入到表尾,表示当前结点是最新被访问过的结点,也可以以O(1)的时间复杂度完成。
3.代码实现
import java.util.*;
class Node {
public int key;
public int val;
public Node pre;
public Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
public class Solution {
private Map<Integer, Node> map = new HashMap();
private Node left = null;
private Node right = null;
private int capacity;
public Solution(int capacity) {
// write code here
this.capacity = capacity;
//left指向最久未使用的结点 right指向最新的结点
left = new Node(-1, -1);
right = new Node(-1, -1);
left.next = right;
right.pre = left;
}
public int get(int key) {
// write code here
if (map.containsKey(key)) {
Node node = map.get(key);
//删除链表中的该结点node
remove(node);
//在最新位置加入该结点
insert(key, node.val);
return node.val;
} else {
return -1;
}
}
public void set(int key, int value) {
// write code here
if (map.containsKey(key)) {
Node node = map.get(key);
remove(node);
insert(key, value);
} else {
if (map.size() == capacity) {
//置换出最近最久未使用的结点
Node del = left.next;
remove(del);
insert(key, value);
} else {
insert(key, value);
}
}
}
private void insert(int key, int val) {
Node cur = new Node(key, val);
Node pre = right.pre;
cur.pre = pre;
cur.next = right;
pre.next = cur;
right.pre = cur;
map.put(key, cur);
}
private void remove(Node node) {
Node pre = node.pre;
Node next = node.next;
pre.next = next;
next.pre = pre;
map.remove(node.key, node);
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution solution = new Solution(capacity);
* int output = solution.get(key);
* solution.set(key,value);
*/
标签:Node,set,get,value,缓存,LRU,BM100,key
From: https://blog.csdn.net/cqjnovo/article/details/141228276