目录
一.设计LRU（最近最少未使用）缓存结构
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。
这里set和get要求的时间复杂度为O(1)。
2.思路步骤
（1）首先自己维护一个双向链表，其中包含自定义的Node类，Node中包含该节点的value,和前后指针，还有key(方便之后将结点存储在map中get的时间复杂度为O（1）).
（2）初始化一个头结点和尾结点，将两个结点连接起来，之后set或get时对该双向链表维护的结点进行操作
（3）对于get操作时，直接将map中维护的结点返回，然后将该结点设置为最近使用。
（4）对于set操作时，首先判断容量是否足够，如果够，就添加到map和链表中；否则就删除掉链表和map中最久未使用的元素，再将该元素设置为最近使用，并添加到map中。
（5）接下来是用双向链表来维护一个最近最久未使用的规则。首先尾结点存放的是最久未使用的结点，头结点存放最新使用的结点。对于最久未使用结点进行删除转化为删除尾结点和map中存放的结点；对于新结点直接插入到头结点，然后再将结点保存到map中即可；对于老节点的访问，首先需要删除链表中该节点，然后再将该节点插入到链表头（相当于是将结点移动到最新访问的位置）。
3.代码
import java.util.*;
public class Solution {
private static class Node{
int val;
int key;
Node pre;
Node next;
public Node(int key, int val) {
this.key = key;
this.val = val;
}
}
int capacity = 0;
//设置一个头结点
Node head = new Node(-1,-1);
//设置一个尾结点
Node tail = new Node(-1,-1);
Map<Integer, Node> map = new HashMap<>();
public Solution(int capacity) {
// write code here
this.capacity = capacity;
//初始化链表，将头尾连接起来
head.next = tail;
tail.pre = head;
}
public int get(int key) {
// write code here
int res = -1;
if(map.containsKey(key)) {
Node node = map.get(key);
res = node.val;
moveHead(node);
}
return res;
}
public void set(int key, int value) {
// write code here
if(!map.containsKey(key)) {
//说明当前元素部存在，添加并判断是否超过容量
Node node = new Node(key, value);
map.put(key, node);
if(map.size()>capacity) {
//超过删除
removeTail();
}
addHead(node);
}else {
//说明已经存在，覆盖并移动到表头
map.get(key).val = value;
moveHead(map.get(key));
}
}
//将节点移动到表头
public void moveHead(Node node){
//如果当前结点已经是表头，结束，否则就删除并添加到表头
if(node.pre==head) return;
node.pre.next = node.next;
node.next.pre = node.pre;
addHead(node);
}
//向头结点插入元素
public void addHead(Node node){
node.next = head.next;
node.pre = head;
head.next.pre = node;
head.next = node;
}
//删除尾结点
public void removeTail(){
//删除hash表中的值
map.remove(tail.pre.key);
//删除结点
tail.pre.pre.next = tail;
tail.pre = tail.pre.pre;
}
}
二.设计LFU缓存结构
1.要求
一个缓存结构需要实现如下功能。
- set(key, value)：将记录(key, value)插入该结构
- get(key)：返回key对应的value值
但是缓存结构中最多放K条记录，如果新的第K+1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构，K作为参数给出
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
示例：
输入：[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3
返回值：[4,-1]
说明：在执行"1 4 4"后，"1 1 1"被删除。因此第二次询问的答案为-1
2.思路图解
（1）首先通过map来保存每一个元素的key和value，方便之后进行查找
（2）自定义一个节点类，其中包含key，value,和访问次数和使用时间（用变化的数值代替），之后对该类设置比较规则，如果访问次数不同，默认以访问次数；如果访问次数相同，就以使用时间的早晚进行排序。
（3）使用一个优先级队列，默认以小堆的方式对结点进行排序，堆顶存放的是能够删除的节点。
（4）对于get操作，需要先将原来的元素访问次数和时间进行修改，然后再在小堆中进行重新排序（以删除添加来实现）。
对于set操作，首先判断key是否已经存在，如果存在，就修改存在元素的值，访问次数和时间，然后再放入到小堆中重新排序；如果不存在，且容量已经满了，需要删除符合规则的元素，删除堆顶，然后设置新节点的访问次数和时间并插入到堆和map中；如果容量没满，设置节点后插入到堆和map中即可。
3.代码
import java.util.*;
public class Solution {
//通过小堆的形式，堆顶存放的是需要删除的结点
Queue<Node> q = new PriorityQueue<>();
Map<Integer, Node> map = new HashMap<>();
int time;//模拟当前时间
//这里k代表容量大小，超过k就需要删除符合规则的key
public int[] LFU (int[][] operators, int k) {
// write code here
ArrayList<Integer> list = new ArrayList<>();
for(int i=0; i<operators.length; i++) {
int opt = operators[i][0];
//判断是set还是get操作
if(opt==1) {
int key = operators[i][1];
int val = operators[i][2];
set(key, val, k);
}else if(opt==2) {
int key = operators[i][1];
list.add(get(key));
}
}
int[] res = new int[list.size()];
for(int i=0; i<res.length; i++) res[i] = list.get(i);
return res;
}
public void set(int key, int val,int k){
//判断该元素是否存在
Node cur = map.get(key);
if(cur==null) {
if(q.size()==k) {
//说明需要删除符合规则的元素,还要删除掉map中该元素
map.remove(q.poll().key);
}
//再将新元素存放到小堆和map中
Node node = new Node(key, val,time++);
q.offer(node);
map.put(key, node);
}else {
//说明该元素已经存在，直接修改元素状态即可
cur.time = time++;
cur.fre++;
cur.val = val;
map.put(key,cur);
q.remove(cur);
q.offer(cur);
}
}
public int get(int key){
Node node = map.get(key);
if(node!=null) {
//需要修改访问时间
node.fre++;
node.time=time++;
//说明元素存在,先删除堆中该元素，然后再插入让其重新排序
q.remove(node);
q.offer(node);
return node.val;
}
//元素不存在
return -1;
}
public class Node implements Comparable<Node>{
int fre;//表示操作次数
int time;//结点创建的时间
int key;
int val;
public Node(int key, int val, int time){
this.key = key;
this.fre++;//第一次创建节点，访问次数为1
this.val = val;
this.time = time;
}
//设置结点的比较规则
public int compareTo(Node node) {
if(this.fre!=node.fre) {
return this.fre-node.fre;
}
return this.time-node.time;
}
}
}