设计 LRU 缓存结构
LRU（Least Recently Use）最近最少使用，实现要求：
- set和get方法的时间复杂度为O(1)
- 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
- 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
思路：
Q：为什么需要双向链表？
因为我需要O(1)完成set操作（其中可能存在删除x结点的操作，假如我使用的是单链表，在删除完链表后，需要O(n)时间遍历到x结点的上一个结点才能实现删除）
class Node {
int k,v;
Node prev,next;
Node() {}
Node(int k,int v) {this.k=k; this.v=v;}
}
class LRUCache {
int cap;
Map<Integer, Node> map;
Node head,tail; //不动的头结点与尾节点
public LRUCache(int capacity) {
cap=capacity;
map=new HashMap<>();
head=new Node(); tail=new Node();
head.next=tail; tail.prev=head;
}
/**
* 两种情况：
* 1. 访问的key存在：返回对应的val，且将该结点设置为链表新头部
* 2. 访问的key不存在：返回-1
*/
public int get(int key) {
Node node=map.get(key);
if (node==null)
return -1;
setFirst(node);
return node.v;
}
/**
* 两种情况：
* 1. 访问的key存在：覆盖对应的val，且在链表中删除对应的结点之后在设置为新头部
* 2. 访问的key不存在：判断容量是否达到超过：(1)超过k，则移除最不经常使用的结点；(2)
*/
public void put(int key, int val) {
Node node=map.get(key);
if (node!=null) { //重复key
node.v=val;
setFirst(node); //将该结点设置为第一个结点
} else { //不存在该key
if (map.size()==cap) { //放不下
Node del=tail.prev;
map.remove(del.k);
remove(del);
}
node=new Node(key,val);
map.put(key,node);
moveToFirst(node);
}
}
private void setFirst(Node node) {
remove(node);
moveToFirst(node);
}
private void moveToFirst(Node node) { //注这里建议不要取head.next的方式来插入结点
node.prev=head;
node.next=head.next;
head.next.prev=node;
head.next=node;
}
private void remove(Node node) {
Node prev=node.prev, next=node.next;
prev.next=next; next.prev=prev;
}
}
设计 LFU 缓存结构
LFU（Least Frequency Use）最近最频繁使用，实现要求：
- int get(int key) - 不存在key，返回-1。
- void put(int key, int value)
- 如果键已存在，则变更其值；如果键不存在，请插入键值对。- 当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。当多个键具有相同使用频率时，应该去除 最久未使用 的键。
思路：