Can anyone help me to see whether these two lines of code are necessary?


  • 1
    D

    For the following solution, are the commented out
    //cacheMap[key] = cacheList.begin();

    in both get and set necessary? Or can we safely remove those lines? With or without those 2 lines, the answer can pass OJ. See comments for ideas/algorithm.

    Thanks

    class LRUCache{
    private:
       struct CacheNode{
           int key;
           int value;
           CacheNode(int k, int v) :key(k),value(v){}
       };
       
       list<CacheNode> cacheList;
       unordered_map<int, list<CacheNode>::iterator> cacheMap;
       int capacity;
        
    public:
        LRUCache(int capacity) {
            this->capacity = capacity;
        }
        
        int get(int key) {
            if (cacheMap.find(key)==cacheMap.end()) return -1;
            //Move the current visited node to head of the list and update the address of it in map
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
           // cacheMap[key] = cacheList.begin();
            return cacheMap[key]->value;
        }
        
        void set(int key, int value) {
            if (cacheMap.find(key) == cacheMap.end()) {
    if (cacheList.size() == capacity) {
        cacheMap.erase(cacheList.back().key);
    cacheList.pop_back();
        }
    //add new node to head of list and add this node to map
        cacheList.push_front(CacheNode(key, value));
        cacheMap[key] = cacheList.begin();
    } else {
    //update the node value, and move the visited node to head of the list, and update the address in map.
    cacheMap[key]->value = value;
    cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
    //cacheMap[key] = cacheList.begin();
    }
    }
    };

  • 0
    S

    You can remove those two lines as long as you use list::splice. The whole point of those two lines is to update the iterators aftera node is moved to the front of the list. Since splice does not invalidate the iterators, there is no need to use to update them. However, if you use erase + push front instead, then these two lines would be crucial.


Log in to reply
 

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