package arithmetic;
import java.util.HashMap;
public class FaceTest81 {
//LRUcache缓存策略map+双向链表
//get、update、put需要时间复杂度达到O1
//map+双向链表结构
public FaceTest81(int capacity) {
cache = new MyCache(capacity);
}
private MyCache<Integer,Integer> cache;
public int get(int key) {//复用get
Integer ans = cache.get(key);
return ans == null ? -1 : ans;
}
//没有就是新增，有就是修改
public void put(int key,int value) {
cache.set(key,value);
}
//节点类型，包含键值，上一个节点和下一个节点
public static class Node<K,V> {
public K key;
public V value;
public Node <K,V> last;//上一个节点
public Node <K,V> next;//下一个节点
public Node(K key,V value) {
this.key = key;
this.value=value;
}
}
//双向链表
public static class NodeDoubleLinkedList<K,V>{
private Node<K,V> head;
private Node<K, V> tail;
public NodeDoubleLinkedList() {
head = null;
tail = null;
}
//构建双向链表的增删改查的方法
public void addNode(Node<K, V> newNode) {
if (newNode == null) {
return;
}
if (head == null) {
head = newNode;
tail = newNode;
}else {
tail.next = newNode;
newNode.last=tail;
tail = newNode;
}
}
//将节点放入尾部
public void moveNodeToTail(Node<K, V> node) {//每次操作都会调用
if (this.tail == node) {//本来就是尾部，直接返回
return;
}
//先将节点拿出来
if (this.head == node) {//如果他是头部，直接让下一个当头
this.head = node.next;
this.head.last = null;
} else {//
node.last.next = node.next;
node.next.last = node.last;
}
//将拿出来的节点节点放入尾部
node.last = this.tail;
node.next = null;
this.head.last = null;
}
public Node<K, V> removeHead(){//超出容量的时候使用
if (this.head == null) {
return null;
}
//先将节点拿出来
Node<K, V> res = this.head;
//直接处理
if (this.head == this.tail) {
this.head = null;
this.tail = null;
}else {
this.head = res.next;
res.next = null;
this.head.last = null;
}
return res;
}
}
//建立缓存策略
public static class MyCache<K,V>{
private HashMap<K, Node<K,V>> keyNodeMap;
private NodeDoubleLinkedList<K,V> nodeList;
private final int capacity;
public MyCache(int cap) {
keyNodeMap = new HashMap<K, Node<K,V>>();
nodeList = new NodeDoubleLinkedList<K, V>();
capacity = cap;
}
public V get(K key) {
if (keyNodeMap.containsKey(key)) {
Node<K, V> res = keyNodeMap.get(key);
nodeList.moveNodeToTail(res);//取出来放入尾部
return res.value;
}
return null;
}
//没有就是新增，有就是修改
public void set(K key, V value) {
//有就是修改
if (keyNodeMap.containsKey(key)) {
Node<K, V> node = keyNodeMap.get(key);
node.value = value;
nodeList.moveNodeToTail(node);
}else {//新增
Node<K, V> newNode = new Node<K, V>(key, value);
keyNodeMap.put(key, newNode);
nodeList.addNode(newNode);
if (keyNodeMap.size() == capacity + 1) {
remoceMostUnusedCache();
}
}
}
private void remoceMostUnusedCache() {//超出容量，移除不常用的头部
Node<K, V> removenoNode = nodeList.removeHead();
keyNodeMap.remove(removenoNode.key);
}
}
}