LeetCode 146. LRU Cache

[Woodyiiiiiii]

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

---

题目要求我们实现一个LRU cache(Least Recently Used cache)，实现基本的get和put功能。

LRU最大的特性就是每次使用过内部一个元素后，要把它的优先级提前。我们可以想到使用线性结构来实现，又因为需要频繁地插入和删除，就需要使用链表结构。因为最好get和put方法都是O(1)时间复杂度，我们可以尝试使用双向链表而不是单向链表(有点类似滑动窗口那道题)，因为单向链表查询节点的时间是线性复杂度，而双向链表节点有前驱节点信息。

定义一个双向链表节点类Node作为内部类，实现add和remove方法，时间复杂度都是O(1)。设置一个头节点head和一个尾节点tail，方便我们向链表头部插入和尾部删除。并且因为有关键值对，设置一个HahsMap，HashMap的key对应key，value对应Node，这样把HashMap和双向链表对应起来了。

get方法首先查询HashMap，如果有对应的key值，移除链表节点并插入头部(提高优先级)，返回value值。put方法首先调用get方法查询是否存在，如果存在，则修改value值并插入头部；如果不存在key，则先判断有没有达到指定容量，达到则移除尾节点的上一个节点，然后建立新链表节点插入头部，存入哈希表中：

class LRUCache {
    
    Node head = new Node(0, 0);
    Node tail = new Node(0, 0);
    int cap;
    HashMap<Integer, Node> map;

    public LRUCache(int capacity) {
        cap = capacity;
        map = new HashMap<>(cap);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        int ans = -1;
        Node node = map.get(key);
        if (node != null) {
            ans = node.val;
            remove(node);
            add(node);
        }
        return ans;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null) {
            remove(node);
            node.val = value;
            add(node);
        }else {
            if (map.size() == cap) {
                Node aban = tail.prev;
                remove(aban);
                map.remove(aban.key);
            }
            
            Node newNode = new Node(key, value);
            add(newNode);
            map.put(newNode.key, newNode);
        }
    }
    
    class Node {
        public int key;
        public int val;
        public Node prev;
        public Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            prev = null;
            next = null;
        }
    }
    
    public void add(Node node) {
        Node headNext = head.next;
        head.next = node;
        node.prev = head;
        node.next = headNext;
        headNext.prev = node;
    }
    
    public void remove(Node node) {
        Node nodePrev = node.prev;
        Node nodeNext = node.next;
        node.prev = null; 
        node.next = null;
        nodePrev.next = nodeNext;
        nodeNext.prev = nodePrev;
    }
}

上述解法是我们自己实现了一个双向链表，利用预先的头节点和尾节点优化了时间复杂度。

我们也可以使用Java的集合LinkedList双向链表，同理：

class LRUCache {
    
    Deque<Integer> list = new LinkedList<>(); 
    int cap;
    HashMap<Integer, Integer> map;

    public LRUCache(int capacity) {
        cap = capacity;
        map = new HashMap<>(cap);
    }
    
    public int get(int key) {
        int ans = -1;
        Integer val = map.get(key);
        if (val != null) {
            ans = val;
            list.remove(key);
            list.offerFirst(key);
        }
        return ans;
    }
    
    public void put(int key, int value) {
        Integer val = map.get(key);
        if (val != null) {
            map.put(key, value);
            list.remove(key);
            list.addFirst(key);
        }else {
            if (list.size() == cap) {
                Integer theLastKey = list.pollLast();
                map.remove(theLastKey);
            }
            
            map.put(key, value);
            list.offerFirst(key);
        }
    }
    
    
}

平均运行时间比自己实现的双向链表方法更多。注意： LinkedList的构造需要向上转型Deque，因为使用 remove方法 时会出现混乱。

我们可以不用链表结构。链表结构的作用是实现HashMap无法实现的功能——内部有序，保证增加新元素时在集合头部。所以我们想到Map集合中实现了按插入时间排序的LinkedHashMap，其实第一个解法中的双向链表+HashMap的结构就是LinkedHashMap的底层实现，同样有个预设的before和after节点。

get和put方法同理。removeEldestEntry方法是用来移除最后的键值对的，JDK1.8后文档解释如下：Returns true if this map should remove its eldest entry. This method is invoked by put and putAll after inserting a new entry into the map. It provides the implementor with the opportunity to remove the eldest entry each time a new one is added. This is useful if the map represents a cache: it allows the map to reduce memory consumption by deleting stale entries.

class LRUCache {
    
    int cap;
    LinkedHashMap<Integer, Integer> map;

    public LRUCache(int capacity) {
        cap = capacity;
        map = new LinkedHashMap<>() {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return size() > cap;
            }
        };
    }
    
    public int get(int key) {
        Integer val = map.get(key);
        if (val == null) return -1;
        else {
            map.remove(key);
            map.put(key, val);
            return val;
        }
    }
    
    public void put(int key, int value) {
        Integer val = map.get(key);
        if (val != null)
            map.remove(key);
        map.put(key, value);
    }
    
    
}

类似题目：

• 460. LFU Cache

---

参考资料：

• https://leetcode.com/problems/lru-cache/
• https://leetcode.com/problems/lru-cache/discuss/654039/Java-Easy-to-understand-with-only-add-and-remove-operation
• https://leetcode.com/problems/lru-cache/discuss/647354/JAVA-or-Straightforward-approach-or-linkedhashmap