牛客题霸每日一题LRU缓存结构设计，关联LFU缓存结构设计
LRU: Map + 自定义双向链表
import java.util.*;
public class Solution {
/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LRU (int[][] operators, int k) {
// write code here
LRU lru = new LRU(k);
List<Integer> res = new ArrayList<>(operators.length);
for(int[] oper: operators){
int op = oper[0];
if(oper[0] == 2){
res.add(lru.get(oper[1]));
}
else{
lru.set(oper[1], oper[2]);
}
}
int[] result = new int[res.size()];
for(int i = 0; i < res.size(); ++i){
result[i] = res.get(i);
}
return result;
}
private class LRU{
private class Node{
int key, val;
Node prev, next;
public Node(int k, int v, Node p, Node n){
key = k;
val = v;
prev = p;
next = n;
}
}
private int MAXSIZE;
private Node head;
private Node tail;
private Map<Integer, Node> map;
public LRU(int k){
MAXSIZE = k;
head = new Node(0, 0, null, null);
tail = new Node(0, 0, head, null);
head.next = tail;
map = new HashMap<>();
}
public int get(Integer key){
Node curr = map.getOrDefault(key, null);
if(curr == null){return -1;}
remove(curr);
insert(curr);
return curr.val;
}
public void set(Integer key, Integer val){
Node curr = map.getOrDefault(key, null);
Node newNode = new Node(key, val, null, null);
map.put(key, newNode);
insert(newNode);
if(curr != null){
remove(curr);
}else{
if(map.size() > MAXSIZE){
Node oldest = tail.prev;
map.remove(oldest.key);
remove(oldest);
}
}
}
private void remove(Node curr){
curr.prev.next = curr.next;
curr.next.prev = curr.prev;
}
private void insert(Node curr){
curr.next = head.next;
curr.next.prev = curr;
curr.prev = head;
head.next = curr;
}
}
} LFU第一种实现: Map+单个双向链表
import java.util.*;
public class Solution {
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LFU (int[][] operators, int k) {
// write code here
if(operators == null || operators.length == 0){return new int[0];}
List<Integer> res = new ArrayList<>(10);
MyLFU lfu = new MyLFU(k);
for(int[] oper : operators){
if(oper.length == 3){
lfu.set(oper[1], oper[2]);
}else{
res.add(lfu.get(oper[1]));
}
}
int len = res.size();
int[] arr = new int[len];
for(int i = 0; i < len; ++i){
arr[i] = res.get(i);
}
return arr;
}
private class MyLFU{
private class Node{
public int key;
public int val;
public int count;
public Node next;
public Node prev;
public Node(int k, int v){
this.key = k;
this.val = v;
this.count = 1;
}
}
private Node head = new Node(0, 0); // next指向删除概率最小的元素
private Node tail = new Node(0, 0); // prev指向删除该旅最大的元素
private int size = 0;
private int capacity;
private Map<Integer, Node> nodes = new HashMap<>(16);
public MyLFU(int k){
this.head.next = tail;
this.tail.prev = head;
this.capacity = k;
}
public int get(int key){
if(this.nodes.containsKey(key)){
Node node = this.nodes.get(key);
++node.count;
this.adjustToHead(node);
return node.val;
}
return -1;
}
public void set(int key, int val){
if(this.nodes.containsKey(key)){
Node node = this.nodes.get(key);
node.val = val;
++node.count;
this.adjustToHead(node);
}else{
Node node = new Node(key, val);
Node curr = this.head;
while(curr.next != tail && curr.next.count > 1){
curr = curr.next;
}
node.next = curr.next;
curr.next.prev = node;
curr.next = node;
node.prev = curr;
this.nodes.put(key, node);
if(++this.size > this.capacity){
this.remove();
}
}
}
private void adjustToHead(Node node){
Node prev = node.prev;
while(prev != head && node.count >= prev.count){
prev.next = node.next;
node.next.prev = prev;
node.next = prev;
node.prev = prev.prev;
prev.prev.next = node;
prev.prev = node;
prev = node.prev;
}
}
private void remove(){
this.nodes.remove(this.tail.prev.key);
this.tail.prev.prev.next = this.tail;
this.tail.prev = this.tail.prev.prev;;
}
}
} LFU第二种实现：Map1存key->Node，Map2存频数->双向链表，同一双向链表里的节点的频数相同。该方法时间复杂度略优于第一种实现。
import java.util.*;
public class Solution {
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LFU (int[][] operators, int k) {
// write code here
if(operators == null || operators.length == 0){return new int[0];}
List<Integer> res = new ArrayList<>(10);
MyLFU lfu = new MyLFU(k);
for(int[] oper : operators){
if(oper.length == 3){
lfu.set(oper[1], oper[2]);
}else{
res.add(lfu.get(oper[1]));
}
}
int len = res.size();
int[] arr = new int[len];
for(int i = 0; i < len; ++i){
arr[i] = res.get(i);
}
return arr;
}
private class MyLFU{
private class Node{
public int key;
public int val;
public int count;
public Node next;
public Node prev;
public Node(int k, int v){
this.key = k;
this.val = v;
this.count = 0;
}
}
private class MyLinkedList{
private Map<Integer, Node> map = new HashMap<>(16);
private Node head = new Node(0, 0); // head.next为最后删除的元素
private Node tail = new Node(0, 0); // tail.prev为优先删除的元素
private int size = 0;
public MyLinkedList(){
this.head.next = this.tail;
this.tail.prev = this.head;
}
public int size(){return this.size;}
public Node pop(){
Node node = this.tail.prev;
if(node == this.head){return null;}
node.prev.next = this.tail;
this.tail.prev = node.prev;
map.remove(node.key);
--size;
return node;
}
public void add(Node node){
node.next = this.head.next;
node.next.prev = node;
this.head.next = node;
node.prev = this.head;
map.put(node.key, node);
++size;
}
public void removByKey(int key){
if(!this.map.containsKey(key)){return;}
Node node = map.get(key);
node.prev.next = node.next;
node.next.prev = node.prev;
map.remove(key);
--size;
}
}
private int size = 0;
private int minCount = 1;
private int capacity;
private Map<Integer, Node> nodes = new HashMap<>(16); // key->Node
private Map<Integer, MyLinkedList> freqs = new HashMap<>(16); // count->MyLinkedList
public MyLFU(int k){
this.capacity = k;
}
public int get(int key){
if(this.nodes.containsKey(key)){
Node node = this.nodes.get(key);
this.move(node);
return node.val;
}
return -1;
}
public void set(int key, int val){
Node node;
if(!this.nodes.containsKey(key)){
node = new Node(key, val);
this.nodes.put(key, node);
++this.size;
}else{
node = this.nodes.get(key);
node.val = val;
}
this.move(node);
if(this.size > this.capacity){
MyLinkedList list = this.freqs.get(this.minCount);
Node poped = list.pop();
this.nodes.remove(poped.key);
if(list != null || list.size() == 0){
this.minCount = 0;
do{
list = this.freqs.getOrDefault(++this.minCount, null);
}while(list == null || list.size() == 0);
}
--this.size;
}
}
private void move(Node node){
MyLinkedList list = this.freqs.getOrDefault(node.count, null);
if(list != null){ list.removByKey(node.key); }
int newCount = ++node.count;
if(!this.freqs.containsKey(newCount)){
list = new MyLinkedList();
this.freqs.put(newCount, list);
}else{
list = this.freqs.get(newCount);
}
list.add(node);
}
}
} 
