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

思路:
https://blog.csdn.net/luzhensmart/article/details/120219540

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {

        int[] result = new int[k];

        if (operators == null || operators.length == 0 || k < 1) {
            return result;
        }

        LRUCache lruCache = new LRUCache(k);
        List<Integer> resultList = new LinkedList<>();

        for (int i = 0; i < operators.length; i++) {

            int[] data = operators[i];

            int key = data[1];

            if (data[0] == 1) {
                int value = data[2];
                lruCache.put(key, value);
            } else if (data[0] == 2) {
                int val = lruCache.get(key);
                resultList.add(val);
            }
        }

        int[] resultArray = resultList.stream().mapToInt(Integer::intValue).toArray();
        return resultArray;
    }


    class LRUCache {

        //头节点
        Entry head;

        //尾节点
        Entry tail;

        //map的容量
        int capacity;

        //map中真实的数据数量
        int size;

        Map<Integer, Entry> cacheMap;

        public LRUCache (int capacity) {

            this.capacity = capacity;

            initLinkedList();

            this.size = 0;

            //lrc cacheMap的容量 + 头尾节点数量2
            cacheMap = new HashMap<>(capacity + 2);
        }

        public void initLinkedList () {
            head = new Entry();
            tail = new Entry();
            head.next = tail;
            tail.pre = head;
        }

        public int get (int key) {

            Entry node = cacheMap.get(key);

            if (node == null) {
                return -1;
            }

            moveToHead(node);

            return node.value;
        }

        public void put (int key, int value) {

            Entry node = cacheMap.get(key);

            if (node != null) {

                //覆盖value
                node.value = value;
                moveToHead(node);
                return;

            } else {

                // 不存在。先加进去，再移除尾结点
                // 此时容量已满 删除尾结点
                if (size == capacity) {

                    Entry lastNode = tail.pre;
                    deleteNode(lastNode);
                    cacheMap.remove(lastNode.key);
                    size--;
                }

                Entry entry = new Entry(key, value);
                addNode(entry);
                cacheMap.put(key, entry);
                size++;

            }
        }

        public void moveToHead (Entry node) {

            deleteNode(node);

            addNode(node);
        }

        //移除双向链表中该节点的pre next指针
        public void deleteNode (Entry node) {
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }

        //向头节点之后 插入该节点 即头插法
        public void addNode (Entry node) {
            node.next = head.next;
            head.next.pre = node;

            head.next = node;
            node.pre = head;
        }
    }

    class Entry {

        Entry pre;

        Entry next;

        int key;

        int value;

        public Entry () {}

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