Code not working need help. Provided my algorithm and code.


  • 0
    S

    @LHearen My idea is that maintain a linked list along with hash map, if case of set function I insert values if it has not reached the capacity, however, if it has reached the capacity I replace the tail node in the linked list with the new key and update the hash map accordingly.

    In case of get function each time I return a value I am swapping the head of the linked list with the value that I get. Doing this in order to have the Least Recentl Used value at the tail of the linked list.

    Since I am not able to understand the sequence of the numbers in the test case array, I m not not able to undestand .

    struct Cache{
        int val;
        Cache *next;
        Cache(int x):val(x),next(NULL){}
    };
    class LRUCache{
    public:
        unordered_map<int,Cache*> dict;
        int cap;
        Cache* head;
        Cache* tail;
        Cache* cur;
        LRUCache(int capacity) {
            cap=capacity;
            head=new Cache(INT_MAX);
            tail=head;
            cur=head;
        }
        
        int get(int key) {
            if(dict.find(key)==dict.end())
                return -1;
            Cache* node=dict[key];
            int value=head->next->val;
            head->next->val=node->val;
            node->val=value;
            dict.erase(key);
            int oldkey;
            for(auto it:dict){
                if(it.second==head->next){
                    oldkey=it.first;
                    dict.erase(it.first);
                    break;
                }
            }
            dict[oldkey]=node;
            dict[key]=head->next;
            return dict[key]->val;
        }
        
        void set(int key, int value) {
            if(!cap){
                for(auto it:dict){
                    if(it.second==tail){
                        dict.erase(it.first);
                        dict[key]=tail;
                        tail->val=value;
                        break;
                    }
                }
            }
            else{
                --cap;
                cur->next=new Cache(value);
                cur=cur->next;
                tail=cur;
                dict[key]=cur;
            }    
        }
    };
    

  • 0
    J

    In the case of set function, it should see if the key is already present in the cache, and if so, update the cached value accordingly. You only insert (and replace if necessary) if the key is not present. You should never have duplicate keys cached.

    As for understanding the input format, there are other posts explaining the meaning of it.


Log in to reply
 

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