题目链接:https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84
题目描述
设计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 ≤ 10^5
0 ≤ key,val ≤ 2×10^9
1≤ n ≤ 10^5
示例 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"
解题代码
import java.util.*;
public class Solution {
private int capacity; //缓存剩余容量
private Map<Integer, Node> map; //哈希表
private Node head; //链表头
private Node tail; //链表尾
class Node { //节点类
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public Solution(int capacity) {//构造器初始化
this.capacity = capacity;//剩余量
this.map = new HashMap<>();
head = new Node(-1, -1); //创建出链表头
tail = new Node(-1, -1); //创建出一个链表尾 头和尾都是为了插入和删除方便
head.next = tail; //双向链表,头尾相连
tail.pre = head;
}
public int get(int key) {
//get方法,步骤是先到hash表里找,有的话,就拿到这个节点,然后把这个节点移动到表头, 如果没有找到,就返回-1;
int res = -1;
if (map.containsKey(key)) {
Node node = map.get(key);
res = node.value;
moveToHead(node);
}
return res;
}
public void set(int key, int value) {
//set方法,步骤是先到hash表里找这个节点,如果有,就更新value值,然后把这个节点移到表头
//如果没有找到,就新建一个节点,在插入之前判断capacity剩余量,如果没有剩余量就删除表尾节点,如果有就直接插到表头。
if (map.containsKey(key)) { //只是更新,容量不会改变
Node node = map.get(key);
node.value = value; //更新value
map.put(key, node); //哈希表里的值也要更新
moveToHead(node);
} else { //插入新节点,容量减一
Node node = new Node(key, value);
if (capacity <= 0) { //没有容量了,要先删除尾节点
removeTail(); //执行一次删尾动作,腾出空间
}
insertFirst(node); //插入节点到表头
map.put(key, node); //map也进行更新
capacity--; //容量减一
}
}
public void insertFirst(Node node) {
//插入节点到表头,单独写一个函数
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
public void moveToHead(Node node) {
//移动节点到表头,先把节点从链表断开,然后插入到表头
node.pre.next = node.next;
node.next.pre = node.pre;
insertFirst(node);
}
public void removeTail() {
//删除尾节点,不用接收参数,map里也要删除这个节点
map.remove(tail.pre.key);
tail.pre.pre.next = tail;
tail.pre = tail.pre.pre;
//删除一个节点,容量加一
capacity++;
}
}
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名,转载请标明出处。
最后编辑时间为:
2022/09/09 09:05:09