20201129.md

Algorithm

146. LRU Cache

Description

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. Follow up: Could you do get and put in O(1) time complexity?

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

• 1 <= capacity <= 3000
• 0 <= key <= 3000
• 0 <= value <= 104
• At most 3 * 104 calls will be made to get and put.

Solution

class LRUCache
{
    static class DllNode
    {
        int val;
        DllNode left;
        DllNode right;

        public DllNode(int val)
        {
            this.val = val;
            this.left = this.right = null;
        }
    }
    // 头节点
    DllNode head = null;
    // 尾节点
    DllNode tail = null;
    // 容量
    private int capacity;

    private HashMap<Integer, DllNode> KeyToNodeRefMap;
    private HashMap<DllNode, Integer> NodeRefToKeyMap;

    public LRUCache(int capacity)
    {
        KeyToNodeRefMap = new HashMap<>(capacity);
        NodeRefToKeyMap = new HashMap<>(capacity);
        this.capacity = capacity;
    }

    public int get(int key)
    {
        // 不包含直接返回-1
        if(!KeyToNodeRefMap.containsKey(key))
            return -1;

        DllNode dllNode = KeyToNodeRefMap.get(key);

        removeNode(dllNode);
        appendNodeAtHead(dllNode);

        return dllNode.val;
    }

    public void put(int key, int value)
    {
        DllNode dllNode;

        if(KeyToNodeRefMap.containsKey(key))
        {
            dllNode = KeyToNodeRefMap.get(key);
            dllNode.val = value;
            removeNode(dllNode);
        }
        else
        {
            cleanUpIfMaxCapacityReached();
            dllNode = new DllNode(value);
        }

        KeyToNodeRefMap.put(key, dllNode);
        NodeRefToKeyMap.put(dllNode, key);

        appendNodeAtHead(dllNode);
    }

    private void appendNodeAtHead(DllNode dllNode)
    {
        if(head == null)
        {
             head = dllNode;
             tail = head;
        }
        else
        {
            head.left = dllNode;
            dllNode.right = head;
            head = dllNode;
        }
    }

    private void removeNode(DllNode dllNode)
    {
         if(head == dllNode)
            head = head.right;

        if(tail == dllNode)
            tail = tail.left;

        if(dllNode.left != null)
            dllNode.left.right = dllNode.right;

        if(dllNode.right != null)
            dllNode.right.left = dllNode.left;

        dllNode.left = null;
        dllNode.right = null;
    }

    private void cleanUpIfMaxCapacityReached()
    {
        if(KeyToNodeRefMap.size() == capacity)
        {
            Integer keyToBeRemoved = NodeRefToKeyMap.get(tail);
            KeyToNodeRefMap.remove(keyToBeRemoved);
            NodeRefToKeyMap.remove(tail);

            removeNode(tail);
        }
    }
}

Discuss

Review

Tip

Share