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
int n = 0;
for(int i = 0;i < operators.length;i++){
if(operators[i][0] == 2)
n ++;
}
int[] res = new int[n];
LFU lfu = new LFU(k);
int l = 0;
for(int i = 0;i < operators.length;i++){
if(operators[i][0] == 1){
lfu.set(operators[i][1],operators[i][2]);
}else if(operators[i][0] == 2){
res[l++] = lfu.get(operators[i][1]);
}
}
return res;
}
}
class LFU {
private int capacity; // 缓存容量
private int size; // 缓存中当前的节点数量
private HashMap<Integer,Node> records;
// 表示节点Node在哪个桶中
private HashMap<Node,NodeList> heads;
private NodeList headList; //整个结构中位于最左边的桶
public LFU(int K){
this.capacity = K;
this.size = 0;
this.records = new HashMap<>();
this.heads = new HashMap<>();
headList = null;
}
/**
* 该函数的功能是：判断刚刚减少了一个节点的桶是否已经为空
* 1、如果不为空，则什么也不做
*
* 2、如果为空，且removeNodeList是整个缓存结构中最左边的桶，则删除这个桶，同时让缓存结构
* 中最左边的桶变为removeNodeList的下一个桶
*
* 3、如果为空，且removeNodeList不是整个缓存结构中最左边的桶，则删除这个桶，将removeNodeList前后的桶修改为
* 直接双向连接
* @param removeNodeList 表示刚刚减少了一个Node节点的桶
* @return 返回值表示removeNodeList是否已经为空，空则返回true，否则返回false
*/
private boolean modifyHeadList(NodeList removeNodeList){
if (removeNodeList.isEmpty()){
if (headList == removeNodeList){
headList = removeNodeList.next;
// 避免此时只有一个removeNodeList一个桶，而造成空指针异常
if (headList != null){
headList.prev = null;
}
}else {
removeNodeList.prev.next = removeNodeList.next;
// 避免removeNodeList是最右边的桶，然后造成removeNodeList.next.prev产生空指针异常
if (removeNodeList.next != null){
removeNodeList.next.prev = removeNodeList.prev;
}
}
return true;
}
return false;
}
/**
* 函数功能：当node节点的操作次数加1了，将这个节点从原来的桶中放入操作次数+1的桶中
* 整个过程要保证桶之间仍然是双向链表，也要保证节点之间仍然是双向链表
* @param node
*/
private void move(Node node,NodeList oldNodeList){
oldNodeList.deleteNode(node);
// preList表示操作次数加1的后对应的那个桶的前一个桶
// 如果oldNodeList删除node之后，空了，此时需要将oldNodeList删掉，那么次数加1后对应的那个桶的前一个桶就是oldNodeList.prev
// 如果oldNodeList删除node之后，不空，那么oldNodeList依然是次数加1后对应的那个桶的前一个桶
NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.prev : oldNodeList;
NodeList nextList = oldNodeList.next;
if (nextList == null){
NodeList newList = new NodeList(node);
if (preList != null){
preList.next = newList;
}
newList.prev = preList;
if (headList == null){
headList = newList;
}
heads.put(node,newList);
}else {
if (nextList.head.times == node.times){
nextList.addNodeToHead(node);
heads.put(node,nextList);
}else {
NodeList newList = new NodeList(node);
if (preList != null){
preList.next = newList;
}
newList.prev = preList;
newList.next = nextList;
nextList.prev = newList;
if (headList == nextList){
headList = newList;
}
heads.put(node,newList);
}
}
}
public void set(int key,int value){
if (records.containsKey(key)){
Node node = records.get(key);
node.value = value;
node.times ++;
NodeList curNodeList = heads.get(node);
move(node,curNodeList);
}else {
if (size == capacity){
Node node = headList.tail;
headList.deleteNode(node);
modifyHeadList(headList);
records.remove(node.key);
heads.remove(node);
size --;
}
Node node = new Node(key, value, 1);
if (headList == null){
headList = new NodeList(node);
}else {
if (headList.head.times == node.times){
headList.addNodeToHead(node);
}else {
NodeList newList = new NodeList(node);
newList.next = headList;
headList.prev = newList;
headList = newList;
}
}
records.put(key,node);
heads.put(node,headList);
size ++;
}
}
public int get(int key){
if (!records.containsKey(key)){
return -1;
}
Node node = records.get(key);
node.times ++;
NodeList curNodeList = heads.get(node);
move(node,curNodeList);
return node.value;
}
/**
* 节点的数据结构
*/
class Node{
public int key;
public int value;
public int times; // 该节点发生set和get的次数总和
public Node next;
public Node prev;
public Node(int key,int value,int times){
this.key = key;
this.value = value;
this.times = times;
}
}
/**
* 桶的数据结构
*/
class NodeList{
public Node head; // 指向桶的头节点的指针
public Node tail; // 指向桶的尾节点的指针
public NodeList next;
public NodeList prev;
// 初始化
public NodeList(Node node){
head = node;
tail = node;
}
/**
* 将一个新的节点加入桶中，新的节点作为桶中新的头节点
* @param newNode
*/
public void addNodeToHead(Node newNode){
newNode.next = head;
head.prev = newNode;
head = newNode;
}
/**
* 删除Node节点并保证node的上下文环境重新连接
* @param node
*/
public void deleteNode(Node node){
if (head == tail){
head = null;
tail = null;
}else {
if (head == node){
head = node.next;
head.prev = null;
}else if (node == tail){
tail = node.prev;
tail.next = null;
}else {
node.next.prev = node.prev;
node.prev.next = node.next;
}
}
node.next = null;
node.prev = null;
}
public boolean isEmpty(){
return head == null;
}
}
}
京公网安备 11010502036488号