In order to keep the habit of efficient brushing, I will try my best to keep the daily state here.

Today are two things you probably won’t pay much attention to on the front end:

  • For example: have you studiedvue 的 keepaliveHow does it work?
  • You’re on the front endset/mapIs the use of their own unique insights?

I’ve done a set/map summary before, hoping it will be helpful.

Address: set vs map and Object

146. The LRU cache

Implementation idea: the main implementation idea is to use: with the help of map to store each key,vlaue;

Get () to fetch, put() to update. It is important to get the keys that have not been used recently

this.cache.keys().next().value

Code implementation:

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.cache = new Map();
    this.capacity = capacity;
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if (this.cache.has(key)) {
        let temp = this.cache.get(key);
        this.cache.delete(key);
        this.cache.set(key, temp);
        return temp;
    }
    return -1;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if (this.cache.has(key)) {
        this.cache.delete(key)
    // } else if (this.capacity >= this.cache.size) { // error
    } else if (this.cache.size >= this.capacity) {
        this.cache.delete(this.cache.keys().next().value)
    }
    return this.cache.set(key, value);
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */


Copy the code
380. O(1) time to insert, delete, and obtain random elements

Array +map as the theme of the idea:

  • The implementation of inserts can actually be put in the end as an array
  • The deletion implementation requires O(1), so we need a structure to record the index of the currently inserted value. Map is recommended here tovalue: indexFormat storage; We need to find the current value when we want to delete itCorresponding index.Let’s get rid of the indexAnd then swap it with the last element of the array,Then delete the value; Finally, the last element overwrites the current deleted value, updating the array length.
  • The implementation of the fetch will be relatively simple, according toRandom * array lengthAccording to theindexTo get it directly

Code implementation:

var RandomizedSet = function() { this.num = []; this.map = new Map(); }; /** * @param {number} val * @return {boolean} */ RandomizedSet.prototype.insert = function(val) { if (this.map.has(val))  return false; // this.map.set(val, this.num. Length); this.num.push(val); return true; }; / * * * @ param @ return {Boolean} {number} val * * / RandomizedSet prototype. Remove = function (val) {/ / there is no return false if (! this.map.has(val)) return false; let index = this.map.get(val); Set (this.num[this.num. Length-1], index); // Delete index map this.map.set(this.num[this.num. Num this.num[index] = this.num[this.num. Length -1]; this.num.length--; return true; }; /** * @return {number} */ RandomizedSet.prototype.getRandom = function() { let p = parseInt(Math.random() * this.num.length) return this.num[p]; }; /** * Your RandomizedSet object will be instantiated and called as such: * var obj = new RandomizedSet() * var param_1 = obj.insert(val) * var param_2 = obj.remove(val) * var param_3 = obj.getRandom() */Copy the code

Another way:

If you’re familiar with the Set structure, you can solve this problem in a second. We can look directly at the implementation of the code:

Code implementation:

var RandomizedSet = function() { this.set = new Set(); }; /** * @param {number} val * @return {boolean} */ RandomizedSet.prototype.insert = function(val) { if (this.set.has(val))  return false; this.set.add(val); return true; }; /** * @param {number} val * @return {boolean} */ RandomizedSet.prototype.remove = function(val) { if (! this.set.has(val)) return false; this.set.delete(val); return true; }; /** * @return {number} */ RandomizedSet.prototype.getRandom = function() { let p = parseInt(Math.random() * this.set.size); return [...this.set][p]; }; /** * Your RandomizedSet object will be instantiated and called as such: * var obj = new RandomizedSet() * var param_1 = obj.insert(val) * var param_2 = obj.remove(val) * var param_3 = obj.getRandom() */Copy the code

Code practice address:

146. The LRU cache

380. O(1) time to insert, delete, and obtain random elements