题解 | #设计LRU缓存结构#注释型题解

import java.util.*;


public class Solution {

    //定义一个双向链表
    class DListNode{
        int key;
        int value;
        DListNode prev;
        DListNode next;
        DListNode(){};
        DListNode(int key, int value){
            this.key = key ;
            this.value = value;
        };
    }

    //用于存放当前的数据 使用hashMap存储去重  双向链表存储过期信息
    private HashMap<Integer,DListNode> cache = new HashMap<>();
    //当前的一个大小
    private int size = 0;
    //最大的容量
    private int capacity = 0;
    // 伪头部 伪尾部
    private DListNode head,tail;

    Solution()
    {

    }
    Solution(int capacity){
        this.size = 0;
        this.capacity = capacity;
        head = new DListNode();
        tail = new DListNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key)
    {
        DListNode node = cache.get(key);
        //没有该键对应的元素
        if(node == null)
        {
            return -1;
        }
        //移动到头部
        moveToHead(node);
        return node.value;
    }

    public void set(int key, int  value)
    {
        DListNode node = cache.get(key);
        //如果没有该键对应的元素
        if(node == null)
        {
            DListNode newNode = new DListNode(key,value);
            //添加进hash
            cache.put(key,newNode);
            //添加到头部
            addToHead(newNode);
            size++;
            //如果大于最大容量了 就要删除尾部元素
            if(size > capacity)
            {
                //删除尾部元素
                DListNode curTail = removeTail();
                //从Hash表中也要删除该元素
                cache.remove(curTail.key);
                size--;
            }
        }else
        {
                //改变为最新的值并移动到头部
              node.value = value;
              moveToHead(node);
        }
    }

    //移动到头部
    private void moveToHead(DListNode node)
    {
        removeNode(node);
        addToHead(node);
    }
     //添加到头部
    private void addToHead(DListNode node)
    {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    //移除尾部元素
    private DListNode removeTail()
    {
        DListNode node = tail.prev;
        removeNode(node);
        return node;
    }
    //移除元素
    private void removeNode(DListNode node)
    {
           node.prev.next = node.next;
           node.next.prev = node.prev;
    }
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        Solution solution = new Solution(k);
        ArrayList<Integer> resList = new ArrayList<>();

        for(int i=0;i<operators.length;i++)
        {
            if(operators[i][0] == 1)
            {
                solution.set(operators[i][1],operators[i][2]);
            }else
            {
                int value = solution.get(operators[i][1]);
                resList.add(value);
            }
        }
        int[] res = new int[resList.size()];
        for(int i=0;i<res.length;i++)
        {
            res[i] = resList.get(i);
        }

        return res;
    }

}