题解 | #设计LRU缓存结构#

class Node{
    private int key;
    private int value;
    public Node pre;
    public Node next;
    public Node(){
        this.pre=null;
        this.next=null;
    }
    public Node(int k,int v){
        this.key=k;
        this.value=v;
        this.pre=null;
        this.next=null;
    }
    public int getKey(){
        return key;
    }
    public int getValue(){
        return value;
    }
}
class DLinkedList{
    public Node front;
    public Node rear;
    private int maxNum;
    private int num;
    public DLinkedList(int max){
        this.front=null;
        this.rear=null;
        this.maxNum=max;
        this.num=0;
    }
    public int getMaxNum(){
        return maxNum;
    }
    public int getNum(){
        return num;
    }
    public void setNum(int num){
        this.num=num;
    }
    public void addFront(int k,int v){
        if(front==null){
            Node newNode=new Node(k,v);
            front=rear=newNode;
        }else{
            Node newNode=new Node(k,v);
            newNode.next=front;
            front.pre=newNode;
            front=newNode;
        }
    }
    public void delRear(){
        if(rear==null){
            return;
        }else if(front==rear){
            front=rear=null;
        }else{
            Node temp=rear.pre;
            rear.pre=null;
            temp.next=null;
            rear=temp;
        }
    }
    public void delByNode(Node node){
        if(node==front&&node==rear){
            this.front=this.rear=null;
        }else if(node==rear){
            Node temp=node.pre;
            node.pre=null;
            temp.next=null;
            rear=temp;
        }else if(node==front){
            Node temp=node.next;
            node.next=null;
            temp.pre=null;
            front=temp;
        }else{
            node.next.pre=node.pre;
            node.pre.next=node.next;
        }
    }
    public Node getByKey(int k){
        Node temp=front;
        while(temp!=null&&temp.getKey()!=k){
            temp=temp.next;
        }
        if(temp!=null){
            return temp;
        }else{
            return null;
        }
    }
}
public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    private DLinkedList dlink;
    public int[] LRU (int[][] operators, int k) {
        // write code here
        dlink=new DLinkedList(k);
        int resNum=0;
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==2){
               resNum++;
            }
        }
        int res[]=new int[resNum];
        int resIndex=0;
        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==1){
                set(operators[i][1],operators[i][2]);
            }else{
               res[resIndex]=this.get(operators[i][1]);
                resIndex++;
            }
        }
        return res;
    }
    public  void set(int key,int value){
        if(dlink.getNum()<dlink.getMaxNum()){
            dlink.addFront(key,value);
            dlink.setNum(dlink.getNum()+1);
        }else{
            dlink.delRear();
            dlink.addFront(key,value);
        }
    }
    public int get(int key){
        Node res=dlink.getByKey(key);
        if(res==null){
            return -1;
        }else{
            //删除双向链表中的temp，并将其插到首部
            dlink.delByNode(res);
            dlink.addFront(res.getKey(),res.getValue());
            return res.getValue();
        }
    }
}