This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions

I. Title Description:

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

Capacity Initializes the LRU cache int GET (int key) Returns the value of the key if the key exists in the cache; 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, 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.

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

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] LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); / / return 4Copy the code

Ii. Analysis of Ideas:

Stick under the AC code personally think actually is a kind of “practice” skipping classes, idea is to use a hash data structure to save key-value pairs, here with the Object with the Map, along with a data structure to delete “the longest unused data values”, take advantage of the js Set here, can be enumerated and the order in accordance with order, It just “remembers” the order of use, there are no duplicate elements, and if the current LRU is full, the earliest element in the collection is deleted.

Iii. AC Code:

var LRUCache = function(capacity) {
    this.stack = new Set();
    this.hash = {};
    this.len = capacity;
};

LRUCache.prototype.get = function(key) {
    if (this.stack.has(key)){
        this.stack.delete(key);
        this.stack.add(key);
        return this.hash[key]
    }
    return -1
};

LRUCache.prototype.put = function(key, value) {
    if (this.stack.has(key)){
        this.stack.delete(key)
    }
    this.stack.add(key);
    this.hash[key] = value;
    if(this.stack.size>this.len){
        // delete 1
        for (let x of this.stack) {
            this.stack.delete(x);
            break
        }
    }
    
};
Copy the code

Iv. Summary:

The above implementation is ok in terms of time complexity, but not in terms of space complexity. The redundant key-value pairs in the hash structure are not released, which will be improved later