146. LRU Cache — Medium

前往題目

搬運一下很久以前寫的

想法

• 需要Map來快速定位item
• 但我想不通如何儲存LRU和MRU(Most Recently Used)

思路

既然 get 和 put 需要 O(1) 的時間完成，get 很明顯就是用 Map，put 的話則是 DoubleLinkedList 可以做到!至於怎麼儲存 LRU 和 MRU，其實很簡單，只要每次 get 和 put 都重新放入 list 的最右邊，那最左邊就一定是 LRU，因為會被擠到最左邊去。

1. 需要 HashMap 來快速定位 item
2. 需要 DoubleLinkedList 來快速插入 item
3. 使用 dummy node 作為 LRU 和 MRU 的連結，這樣就不用處理 null pointer 的問題
4. put 裡要注意 exceeding capacity

其餘就是 pointer 操作了，不贅述。

Code

LRU 演算法解說

0146-lru-cache.java

class LRUCache {
    private Map<Integer, Node> cache;
    private int capacity;

    private Node left;
    private Node right;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();

        // Init. LRU and MRU
        this.left = new Node(0, 0); // dummy node
        this.right = new Node(0, 0); // dummy node
        this.left.next = this.right; // Real LRU
        this.right.prev = this.left; // Real MRU
    }
    
    public int get(int key) {
        if (cache.containsKey(key)) {
            remove(cache.get(key));
            insert(cache.get(key)); // Become MRU
            return cache.get(key).val;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            remove(cache.get(key));
        }
        cache.put(key, new Node(key, val));
        insert(cache.get(key));
        
        // Exceed capacity
        if (cache.size() > capacity) {
            Node lru = this.left.next;
            remove(lru); // Remove from list
            cache.remove(lru.key); // Remove from map
        }
    }

    private void remove(Node node) {
        // Previous Node of node
        Node prevNode = node.prev;
        // Next Node of node
        Node nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    private void insert(Node node) {
        // New node as the MRU
        Node prevNode = this.right.prev;
        // Dummy node
        Node nextNode = this.right;

        // Point to the new node
        prevNode.next = node;
        nextNode.prev = node;

        // New node point to its neighbours
        node.prev = prevNode;
        node.next = nextNode;
    }

    private class Node {
        private int key;
        private int val;

        Node prev;
        Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */