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

import java.util.*;


class LRUCache {

    // 双向链表的Node，定义key/value以及prev/next指针
    public static class DoubleNode {
        DoubleNode prev;
        DoubleNode next;
        int key;
        int value;

        public DoubleNode(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public DoubleNode() {

        }
    }

    // 缓存的Map，key-key，value-Node<key,value>
    private HashMap<Integer, DoubleNode> cache = new HashMap<>();

    // 双向链表的head
    private DoubleNode head = new DoubleNode();
    // 双向链表的tail
    private DoubleNode tail = new DoubleNode();

    // cache的容量，超过容量直接不允许放入元素了
    int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DoubleNode node = cache.get(key);
        // 如果缓存中没有的话
        if (node == null) {
            return -1;
        }
        // 如果缓存中有的话，那么移动到head地方去(先从链表中删除再移动)
        removeNode(node);
        addToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        // 对方法的容量进行判断，筛掉传递非法容量的情况
        if (capacity <= 0) {
            return;
        }
        // 从缓存中根据key拿到node
        DoubleNode node = cache.get(key);
        if (node == null) {
            // 如果缓存的容量已经满了，需要移除掉尾部的节点
            if (cache.size() == capacity) {
                cache.remove(tail.prev.key); // 必须先进行操作，不然tail.prev从链表中移除了，引用找不到了
                removeNode(tail.prev); // 必须后进行操作
            }
            // 到达这里缓存一定没满，需要新创建一个node加入到缓存和双向链表中去
            node = new DoubleNode(key, value);
            cache.put(key, node);
            addToHead(node);
            return;
        }
        // 这部分的逻辑和get是一样的，将node从链表中移除掉，并且加到链表头部去
        removeNode(node);
        addToHead(node);
        // 修改node的value为指定的value
        node.value = value;
    }

    // 将node从双向链表中移除掉，普通的双向链表的删除罢了
    private void removeNode(DoubleNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将node添加到最前面去(因为head是傀儡节点，所以应该添加到head之后)
    private void addToHead(DoubleNode node) {
        node.next = head.next;
        node.next.prev = node;
        head.next = node;
        node.prev = head;
    }
}

public class Solution {
    /**
     * lru design
     *
     * @param operators int整型二维数组 the ops
     * @param k         int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU(int[][] operators, int k) {
        LRUCache cache = new LRUCache(k);
        List<Integer> ret = new ArrayList<>();
        for (int[] operator : operators) {
            int length = operator.length;
            // 如果是get操作
            switch (length) {
                case 2:
                    int get = cache.get(operator[1]);
                    ret.add(get);
                    break;
                case 3:
                    cache.put(operator[1], operator[2]);
                    break;
            }
        }
        int[] array = new int[ret.size()];
        for (int i = 0; i < array.length; i++) {
            array[i] = ret.get(i);
        }
        return array;
    }
}