Simple solution with queue and hashmap


  • 0
    L
    /**
     * @constructor
     */
    function LRUCache(capacity) {
        var cache = {};
        var queue = [];
        
        return {
            get: get,
            set: set
        };
        
        function get(k) {
            if (!cache[k]) {
                return -1;
            }
            var idx = queue.indexOf(k);
            queue.splice(idx, 1);
            queue.unshift(k);
            return cache[k];
        }
        
        function set(k, v) {
            // existed
            if (cache[k]) {
                cache[k] = v;
                get(k);
                return;
            }
            
            // overflow
            if (queue.length === capacity) {
                var keyToDestroy = queue.pop();
                cache[keyToDestroy] = undefined;
            }
            
            // cache
            cache[k] = v;
            queue.unshift(k);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.