This is [031, the least cache used recently] on LeetCode, and the difficulty is [medium]

subject

Using the mastered data structure, design and implement an LRU (Least Recently Used) cache mechanism.

Implement LRUCache class:

• LRUCache(int capacity) initializes the LRU cache with a positive integer as capacity
• int get(int key) if the keyword key exists in the cache, the value of the keyword is returned; otherwise, - 1 is returned.
• void put(int key, int value) if the keyword already exists, change its data value; If the keyword does not exist, insert the group keyword value. When the cache capacity reaches the maximum, it should delete the longest unused data value before writing new data, so as to make room for new data values.

Example

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]

explain
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); // This operation will invalidate keyword 2. The cache is {1 = 1, 3 = 3}
lRUCache.get(2);    // Return - 1 (not found)
lRUCache.put(4, 4); // This operation will invalidate keyword 1, and the cache is {4 = 4, 3 = 3}
lRUCache.get(1);    // Return - 1 (not found)
lRUCache.get(3);    // Return 3
lRUCache.get(4);    // Return 4

Tips:

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• Call get and put 2 * 105 times at most

Problem solution

The meaning of the question requires that the time complexity of get and put operations is O(1), so the hash table meets the requirements, but the hash table cannot find the least recently used key. Therefore, the hash table needs to be combined with other data structures to meet the meaning of the question. Through analysis, what data structure meets the least recently used key

Suppose that a container with a data structure meets the minimum usage recently, its capacity is n, and the initial is empty.

When the added elements are added to the container in sequence, the first added element is in the head of the container, and the last added element is in the tail of the container, then the head of the container is the least used element recently

There are two situations when performing put to add elements. (ignore the time when the container judges whether to add elements. This operation needs to be combined with the hash table)

If the container adds an element as an existing element, put is the update element (the value of the update key). At this time, the element is the most recently used element, and two operations need to be done

• Delete the original element in the container
• Add the element to the end of the container

If there is no added element in the container, put is the added element. At this time, the element is the most recently used element. You only need to do one operation to add the element to the tail of the container

To sum up, the container needs to meet the time complexity of adding and deleting elements at the tail is O(1). It is easy to think that the data structure meeting this condition is a two-way linked list

The two-way linked list has both head and tail nodes, that is, it can be traversed from the head or the tail. Therefore, the time complexity of adding elements to the tail is O(1)

Each node of the bidirectional linked list has a leading pointer to the previous node. Therefore, when deleting an element, you only need to find the previous node of the deleted element through the leading pointer of the deleted element, so the time complexity is O(1)

Earlier, when the container executes put, we ignored the time to judge whether elements are added in the container. For example, to add elements in the linked list, we need to judge whether the added elements are in the linked list first, and this operation needs to traverse the linked list, so the time complexity is O(n), which does not meet the meaning of the problem. Therefore, we need to combine the hash table to help us judge whether the added elements are in the linked list.

The key of the hash table stores the key of the added element, and the value of the hash table stores the nodes in the linked list. When we judge whether the added element is in the linked list, we only need to judge through the hash table. The time complexity is O(1), and the get operation is similar to put

code implementation

public class LRUCache {

    // Internal node class
    private class ListNode {

        // Post pointer
        ListNode next;
        // Leading pointer
        ListNode pre;
        // Node storage key value pair
        int key;
        int val;

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

    /* Declare two sentinel nodes as head nodes and tail nodes to reduce logical judgment
    * For example, when the two-way linked list is empty, the head node and tail node are empty, so conditional judgment is required
    * After the sentinel node is used, the head node and tail node are not empty, so conditional interpretation is not required*/
    private ListNode head;
    private ListNode tail;
    // Hash table, the key stores the key of the element, and the value stores the node of the two-way linked list
    private Map<Integer, ListNode> map;
    // Capacity of LRU
    private int capacity;

    public LRUCache(int capacity) {
        // Initial hash table
        this.map = new HashMap();
        // Create two sentinel nodes
        this.head = new ListNode(-1, -1);
        this.tail = new ListNode(-1, -1);
        // Initially, if the two-way linked list is empty, the post pointer of the head node points to the tail node
        head.next = tail;
        // The leading pointer of the tail node points to the head node
        tail.pre = head;
        this.capacity = capacity;
    }

    public int get(int key) {
        // Obtain the nodes in the linked list through the hash table
        ListNode node = map.get(key);
        // If it is null, this node does not exist in the linked list
        if (node == null) {
            return -1;
        }
        /* If it is not null, this node exists in the linked list,
        This node is used recently and first. You need to move it to the end of the linked list and delete the original position of this node in the linked list*/
        moveToTail(node, node.val);
        return node.val;
    }

    public void put(int key, int val) {
        // Obtain the nodes in the linked list through the hash table
        ListNode node = map.get(key);
        /* If it is not equal to null, the linked list already has this node, and the update operation is performed at this time
        * This node is used first recently, so you need to delete the original position of the node in the linked list and move the node to the tail of the linked list*/
        if (node != null) {
            moveToTail(node, val);
        // If it is equal to null, it is an add operation
        } else {
            // When the LRU capacity is full, you need to delete the first node of the linked list (least recently used) and the node recorded in the hash table
            if (map.size() == capacity){
                // Get the first node of the linked list
                ListNode toBeDeleted = head.next;
                // Delete the first node of the linked list
                deleteNode(toBeDeleted);
                // Delete the first node of the hash table record
                map.remove(toBeDeleted.key);
            }
            // Create a new node
            ListNode newNode = new ListNode(key, val);
            // The new node is inserted at the end of the linked list
            insertToTail(newNode);
            // Record the inserted new node in the hash table
            map.put(key, newNode);
        }
    }

    private void moveToTail(ListNode node, int newVal) {
        // Delete the original position of the node in the linked list
        deleteNode(node);
        // When put is an update operation, the value of the node needs to be updated
        node.val = newVal;
        // Insert the node into the tail of the linked list
        insertToTail(node);
    }

    private void insertToTail(ListNode newNode) {
        // The post pointer of the previous node of the tail node points to the new node
        tail.pre.next = newNode;
        // The leading pointer of the new node points to the previous node of the trailing node
        newNode.pre = tail.pre;
        // The post pointer of the new node points to the tail node
        newNode.next = tail;
        // The leading pointer of the tail node points to the new node
        tail.pre = newNode;
    }

    private void deleteNode(ListNode node) {
        // The post pointer of the previous node of the deleted node points to the next node of the deleted node
        node.pre.next = node.next;
        // The leading pointer of the next node of the deleted node points to the previous node of the deleted node
        node.next.pre = node.pre;
    }

}