146.LRU caching mechanism

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. Implement the LRUCache class:

  • LRUCache(int capacity)The capacity is a positive integercapacityInitialize theLRUThe cache
  • int get(int key)If the keywordkeyExists in the cache, returns the value of the keyword, otherwise returns- 1 。
  • void put(int key, int value)If the keyword already exists, change its data value; If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values.
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]Copy the code

Understand the question

When the cache is full, the first value is removed according to the first-in, first-out rule. If a value is accessed in the middle, the value is moved to the end of the queue. If the corresponding value cannot be accessed, -1 is returned.

// give the initial code
/ * * *@param {number} capacity* /
var LRUCache = function(capacity) {};/ * * *@param {number} key
 * @return {number}* /
LRUCache.prototype.get = function(key) {};/ * * *@param {number} key 
 * @param {number} value
 * @return {void}* /
LRUCache.prototype.put = function(key, value) {};Copy the code

Array +Map implementation

Arrays are used to store ordered keys, and maps are used to store key-values. When put, it checks whether the key already exists. If so, it moves the key to the end of the queue. If the array capacity overflows, the header element is removed and the corresponding key-value in the Map is deleted. Then add the key-value of the current put to the Map.Copy the code

The following code

/ * * *@param {number} capacity* /
var LRUCache = function(capacity) {
    // The size of the storage capacity
    this.capacity = capacity;
    this.que = [];
    this.map = new Map(a); };/ * * *@param {number} key
 * @return {number}* /
LRUCache.prototype.get = function(key) {
    const res = this.map.get(key);
    if (res === undefined) return -1;
    // Move the key to the end of the queue
    const index = this.que.findIndex(value= > value === key);
    this.que.splice(index, 1);
    this.que.push(key);
    return res;
};

/ * * *@param {number} key 
 * @param {number} value
 * @return {void}* /
LRUCache.prototype.put = function(key, value) {
    // If there is a key, move it to the end of the queue
    if (this.map.get(key)) {
        for(let i = 0; i<this.capacity; i++) {
            if (this.que[i] === key) {
                this.que.splice(i, 1); }}}this.que.push(key);
    // Delete the key-value corresponding to the team header key and map
    if (this.que.length > this.capacity) {
        const deleteKey = this.que.shift();
        this.map.delete(deleteKey)
    }
    this.map.set(key, value);
};
Copy the code

By using an array, this is easy to implement, but it takes O(n) time to find the subscript of the key in the queue.

Advanced: Can you do both operations in O(1) time?

Bidirectional linked list +Map

A bidirectional linked list is used to store key-values in the order in which they are used, and a Map is used to Map keys to list nodes.Copy the code

First, define a bidirectional linked list, including virtual head nodes and virtual tail nodes. When put is performed, cancel the next pointer to the previous end node and cancel the pre pointer to the end node. The next pointer of the last end node points to the new node created by the newly put key-value, and the pre pointer of the end node points to the new node. The pre pointer of the new node also points to the node before the end node, and the next pointer of the new node points to the end node. This completes the operation of adding a new node to the end of the listCopy the code

When the existing data is accessed, the corresponding nodes of the linked list need to be disconnected from the front and back nodes, which are connected to each other, and then the corresponding nodes are added to the front of the virtual tail node.Copy the code

The following code

/ * * *@param {number} capacity* /
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.vhead = new Node(null);
    this.vend = new Node(null);
    this.vhead.next = this.vend;
    this.vend.pre = this.vhead;
    this.map = new Map(a); };class Node {
    constructor(value){
        this.next = null;
        this.pre = null;
        this.val = value; }}/ * * *@param {number} key
 * @return {number}* /
LRUCache.prototype.get = function(key) {
    const res = this.map.get(key);
    if (res === undefined) return -1;
    if (this.length === 1) return res.val.value;
    res.pre.next = res.next;
    res.next.pre = res.pre;
    
    this.vend.pre.next = res;
    res.pre = this.vend.pre

    res.next = this.vend;
    this.vend.pre = res;
    return res.val.value;
};

/ * * *@param {number} key 
 * @param {number} value
 * @return {void}* /
LRUCache.prototype.put = function(key, value) {
    const node = this.map.get(key);
    if (node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        this.map.delete(node.val.key)
    } else {
        if (this.map.size === this.capacity) {
            const first = this.vhead.next;
            first.pre.next = first.next;
            first.next.pre = this.vhead
            this.map.delete(first.val.key)
        }
    }
        const newNode = new Node({
            value,
            key
        });
        this.vend.pre.next = newNode
        newNode.pre = this.vend.pre
        newNode.next = this.vend;
        this.vend.pre = newNode;
        this.map.set(key, newNode);
};
Copy the code
~ ~ ~ ~ ~ end 🖖.Copy the code