Leetcode NO.146 lru-cache LRU Cache 最近最少使用實作

目錄

• 1.問題描述
• 2.測試用例
  • 示例 1
• 3.提示
• 4.代碼
  • 1.繼承LinkedHashMap實作
    • code
    • 複雜度
  • 2.HashMap && DoubleLinklist

運用你所掌握的資料結構，設計和實作一個 LRU (最近最少使用) 緩存機制 。

實作 LRUCache 類：

LRUCache(int capacity) 以正整數作為容量 capacity 初始化 LRU 緩存

int get(int key) 如果關鍵字 key 存在于緩存中，則傳回關鍵字的值，否則傳回 -1 。

void put(int key, int value) 如果關鍵字已經存在，則變更其資料值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新資料之前删除最久未使用的資料值，進而為新的資料值留出空間。

注意：

你隻能使用隊列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 這些操作。

你所使用的語言也許不支援隊列。 你可以使用 list （清單）或者 deque（雙端隊列）來模拟一個隊列 , 隻要是标準的隊列操作即可。

輸入

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]

[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

輸出

[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋

LRUCache lRUCache = new LRUCache(2);

lRUCache.put(1, 1); // 緩存是 {1=1}

lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}

lRUCache.get(1); // 傳回 1

lRUCache.put(3, 3); // 該操作會使得關鍵字 2 廢棄，緩存是 {1=1, 3=3}

lRUCache.get(2); // 傳回 -1 (未找到)

lRUCache.put(4, 4); // 該操作會使得關鍵字 1 廢棄，緩存是 {4=4, 3=3}

lRUCache.get(1); // 傳回 -1 (未找到)

lRUCache.get(3); // 傳回 3

lRUCache.get(4); // 傳回 4

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多調用 2 * 105 次 get 和 put

public class LRU_Cache_With_LinkedHashMap extends LinkedHashMap<Integer, Integer> {


    private int capacity;

    public LRU_Cache_With_LinkedHashMap(int initialCapacity) {
        /**
         * initialCapacity 容量
         * loadFactor 擴容因子
         * accessOrder false 不删除，
         */
        super(initialCapacity, 0.75f, true);
        this.capacity = initialCapacity;
    }


    @Override
    public Integer get(Object key) {
        return super.get(key) == null ? -1 : super.get(key);
    }

    @Override
    public Integer put(Integer key, Integer value) {
        return super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        // return true 的話，如果map容量已滿，允許新的插入，并且移除老的資料
        //這裡是實作，容量滿了以後，最老的資料删除的操作
        return size() > capacity;
    }
}
           

1.時間 O(1)

2.空間 O(capacity)
           

public class LRUCache {

    private int capacity;
    private int size;
    private DoubleListNode startSentinel;
    private DoubleListNode endSentinel;
    private HashMap<Integer, DoubleListNode> hashMap;


    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        hashMap = new HashMap<>(capacity);
        startSentinel = new DoubleListNode();
        endSentinel = new DoubleListNode();
        startSentinel.next = endSentinel;
        endSentinel.pre = startSentinel;
    }

    class DoubleListNode {
        private Integer key;
        private Integer val;
        private DoubleListNode pre;
        private DoubleListNode next;

        public DoubleListNode() {
        }

        public DoubleListNode(Integer key, Integer val) {
            this.key = key;
            this.val = val;
        }

        @Override
        public String toString() {
            return "val=" + val;
        }
    }

    @Override
    public String toString() {
        return "LRUCache{" +
                "hashMap=" + hashMap +
                '}';
    }




    public Integer get(Integer key) {
        DoubleListNode node = hashMap.get(key);
        //擷取不到傳回-1
        if (node == null) {
            return -1;
        }
        //移動資料到連結清單結尾
        moveToTail(node);
        return node.val;
    }

    public void put(Integer key, Integer value) {
        DoubleListNode node = hashMap.get(key);
        if (node == null) {
            //判斷目前size 和 capacity 的大小
            if (size < capacity) {
                //size ++
                size++;
                //新增節點
                node = new DoubleListNode(key, value);
                //移動新節點到連結清單末尾
                addToTail(node);
                hashMap.put(key, node);

            } else {
                //删除頭結點
                DoubleListNode rmNode = removeNode(startSentinel.next);
                hashMap.remove(rmNode.key);
                //移動新節點到連結清單尾部
                DoubleListNode newNode = new DoubleListNode(key, value);
                addToTail(newNode);
                //添加結點到hashmap
                hashMap.put(key,newNode);
            }
        } else {
            //更新值
            node.val = value;
            //放到尾部
            moveToTail(node);
        }
    }


    /**
     * 移動節點到連結清單尾部
     *
     * @param node
     */
    private void moveToTail(DoubleListNode node) {
        removeNode(node);
        addToTail(node);
    }

    /**
     * 添加結點到雙向連結清單尾部
     *
     * @param node node
     */
    private void addToTail(DoubleListNode node) {
        node.next = endSentinel;
        node.pre = endSentinel.pre;
        endSentinel.pre.next = node;
        endSentinel.pre = node;
    }

    /**
     * 移除節點
     * @param node node
     * @return re
     */
    private DoubleListNode removeNode(DoubleListNode node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node;
    }

}
           

1.時間 O(1)

2.空間 O(capacity)