• LRU：Least Recently Used 最近最少使用
• 題目要求：
  ? ? 設(shè)計(jì)和構(gòu)建一個(gè)“最近最少使用”緩存穷躁，該緩存會(huì)刪除最近最少使用的項(xiàng)目墅垮。緩存應(yīng)該從鍵映射到值(允許你插入和檢索特定鍵對(duì)應(yīng)的值)齿梁，并在初始化時(shí)指定最大容量痹扇。當(dāng)緩存被填滿時(shí)橡羞，它應(yīng)該刪除最近最少使用的項(xiàng)目患整。
  ? ? 它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 拜效。
  ? ? 獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)）各谚，否則返回 -1紧憾。寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值昌渤。當(dāng)緩存容量達(dá)到上限時(shí)赴穗，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間膀息。

思路1：

• KV操作一般想到的就是Map般眉。
• LRU應(yīng)該有排序功能，最熱數(shù)據(jù)放最左潜支，冷數(shù)據(jù)經(jīng)過更迭就會(huì)滯后甸赃，map滿了每次剔除最后的數(shù)據(jù)即可。HashMap是無序的冗酿，需要加入順序埠对，第一個(gè)想到的肯定是LinkedHashMap。
• 因?yàn)長inkedHashMap.put順序是結(jié)尾插入已烤，刪除也需要從頭結(jié)點(diǎn)遍歷鸠窗，所以正好修改思路以頭結(jié)點(diǎn)定為最冷數(shù)據(jù)、結(jié)尾定為最熱數(shù)據(jù)胯究。
• put：分三種情況
  • map里存在key，但還需要修改為最熱數(shù)據(jù)躁绸，所以需要先remove后put即可裕循。
  • map里不存在key臣嚣，并且容量不滿，直接put即可剥哑。
  • map里不存在key硅则，并且容量滿，刪除最冷數(shù)據(jù)株婴，put即可怎虫。
• get：
  • get就是不存在key就返回-1，存在就先remove后put變?yōu)樽顭釘?shù)據(jù)即可困介。
• 調(diào)試后代碼：

class LRUCache {
  private Map<Integer, Integer> map;
    private int capacity;
    public LRUCache(int capacity) {
        map = new LinkedHashMap<>(capacity);
        this.capacity = capacity;
    }

    public int get(int key) {
        if(!map.containsKey(key)) {
            return -1;
        }
        int value = map.get(key);
        map.remove(key);
        map.put(key, value);
        return value;
    }

    public void put(int key, int value) {
        if(map.containsKey(key)){
            map.remove(key);
        }else if(map.size() == capacity){
            Integer removeKey = map.entrySet().iterator().next().getKey();
            map.remove(removeKey);
        }
        map.put(key, value);
    }
}

• 運(yùn)行結(jié)果：

執(zhí)行用時(shí): 36 ms
內(nèi)存消耗: 46.6 MB

思路2（看官方答案后）：

• 官方說不能使用自帶的LinkedHashMap大审，只能用基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)。
• 思路相同座哩，不過只能用HashMap和List實(shí)現(xiàn)了徒扶，效率沒有優(yōu)化，直接貼代碼根穷。

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        public DLinkedNode() {}
        public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用偽頭部和偽尾部節(jié)點(diǎn)
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果 key 存在姜骡，先通過哈希表定位，再移到頭部
        moveToHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedNode node = cache.get(key);
        if (node == null) {
            // 如果 key 不存在屿良，創(chuàng)建一個(gè)新的節(jié)點(diǎn)
            DLinkedNode newNode = new DLinkedNode(key, value);
            // 添加進(jìn)哈希表
            cache.put(key, newNode);
            // 添加至雙向鏈表的頭部
            addToHead(newNode);
            ++size;
            if (size > capacity) {
                // 如果超出容量圈澈，刪除雙向鏈表的尾部節(jié)點(diǎn)
                DLinkedNode tail = removeTail();
                // 刪除哈希表中對(duì)應(yīng)的項(xiàng)
                cache.remove(tail.key);
                --size;
            }
        }
        else {
            // 如果 key 存在，先通過哈希表定位尘惧，再修改 value士败，并移到頭部
            node.value = value;
            moveToHead(node);
        }
    }

    private void addToHead(DLinkedNode node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(DLinkedNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(DLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }

    private DLinkedNode removeTail() {
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}