ARTS | 0x000

reboot my techical journey

Algorithm

Leetcode 146 LRU cache

经典题目，设计题，设计一个最近使用元素的队列，每次使用过后，提到最前面队列最前面，超出长度时候，去掉队列最后一个元素

看了C++的方案，可以使用双向指针 + hashmap来完成，每个操作都是时间复杂度O(1)，由于js没有默认的双向指针结构，使用了数组以及其indexOf方法做顺序+hashmap，用unshift方法来把顺序排到最前面，但unshift方法是O(n)所以其实不是很优的结果，需要注意的关键点有put的时候put重复key的时候需要重新排序以及reset map的值

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.capacity = capacity;
    this.cache = []; // should be two way linklist instead by array can unshift
    this.map = {};
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.cache.indexOf(key) === -1) return -1;
    // shift the key to the top of cache
    this.cache.unshift(this.cache.splice(this.cache.indexOf(key), 1)[0]);
    return this.map[key]
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    this.map[key] = value;
    
    if(this.cache.indexOf(key) === -1) {
        // new key
        this.cache.unshift(key);
    } else {
        // the already in cache switch to first one 
        this.cache.unshift(this.cache.splice(this.cache.indexOf(key), 1)[0]);
    }
    if(this.cache.length > this.capacity) {
        this.cache.pop();
        // delete map here too lazy to do that;
    }
    
};

Review

We have a problem with promises

是一篇比较老的文章，对于Promise的应用，列出了非常多有用的新手以及老手错误，并且还给出了一些习题，非常好的文章，需要找时间深入的了解其中的点

Tip

一直在找好的 Markdown 软件后来发现 vscode 加一些插件就够了

Share

万事开头难，坚持就更加难

·