Nuggets team number online, help you Offer impromptu! Click for details

Using your knowledge of data structures, implement an LRU(least recently used) cache mechanism. LRU cache implementation:

  • LRUCache(int capacity) The LRU cache is initialized using a positive integer as capacity
  • Int get(int key) Returns value if the value corresponding to the key is in the cache, otherwise -1 is returned.
  • Void put(int key,int value) If the value corresponding to the key already exists, the value is replaced; if the value does not exist, the key and value pair is inserted into the cache. If the cache reaches the upper limit, the element that has not been used for the longest time is deleted to free up space for the new element
  • The time complexity of get and PUT methods is O(1).

The general idea of LRU cache is to implement it in the way of linked list, but the query complexity of the cache in the conventional linked list implementation is O(n), which needs to traverse the linked list, so we need a Hash mapping table to do a < key-list node mapping >, so the query complexity is O(1). The corresponding class implemented in Java is LinkedHashMap, check the source code

Iii. AC Code:

class LRUCache {
    // In Java LinkedHashMap = bidirectional list +hashMap, achieve O(1) complexity
    // Two-way list +HashMap
    class DLinkNode {
        DLinkNode prev ;
        DLinkNode next;
        int key;
        int value;
        public DLinkNode(a){}
        public DLinkNode(int key,int value){this.key = key;this.value = value;}
    }
    / / the hash table
    Map<Integer,DLinkNode> map ;
    // an empty tail node
    DLinkNode head;
    DLinkNode tail;
    / / capacity
    private int capacity ;
    // Real-time quantity
    private int size;
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.head  = new DLinkNode();
        this.tail = new DLinkNode();
        map  = new HashMap(capacity);
        this.head.next = tail;
        this.tail.prev = head;
    }
    
    public int get(int key) {
        DLinkNode valueNode = map.get(key);
        if(valueNode == null) {return -1;
        }
        removeNode(valueNode);
        addHead(valueNode);
        return valueNode.value;
    }
    
    public void put(int key, int value) {
        DLinkNode valueNode = map.get(key);
        // If the value does not exist
        if(valueNode == null) {if(this.size >= this.capacity){
                // Delete from the list
                DLinkNode removedNode = removeOldest();
                // Delete from HashMap
                map.remove(removedNode.key);
                --size;
            }
            DLinkNode temp = new DLinkNode(key,value);
            addHead(temp);
            map.put(key,temp);
            ++size;
        }else{
            // Update the value in the HashMap when it exists
            valueNode.value = value;
            // Move the node to the headremoveNode(valueNode); addHead(valueNode); }}// Delete a node O(1) from the list.
    private void removeNode(DLinkNode valueNode){
        valueNode.prev.next = valueNode.next;
        valueNode.next.prev = valueNode.prev;
    }

    // Remove the oldest element
    private DLinkNode removeOldest(a){
        DLinkNode oldest = this.tail.prev;
        removeNode(oldest);
        return oldest;
    }

    // Add a node to the head O(1)
    private void addHead(DLinkNode valueNode){
        this.head.next.prev = valueNode;
        valueNode.next = this.head.next;
        valueNode.prev = this.head;
        this.head.next = valueNode; }}Copy the code

Four,