My code have different results running on my Visual Studio and on your compiler.


  • 1
    Y

    Hi, I have written the following code. That works fine with the "set[2,1] set[2,2] get(2) set[1,1] set[4,1] get(2)" case on my machine. But on the server it will fail. Can anybody figure out why?

    The basic idea is I have two set, visited and unvisited. For each time an element is touched, it is added to the visited set and deleted from unvisited set. When visited set has all the elements in the cache, I clear the visited set and make the unvisited set full. That is an emulation of LRU. The tricky part I did is I didn't set the unvisited set manually. In stead, I exchange the two sets.

    class LRUCache{
        unordered_map<int, int> cache;
        int _capacity;
        
        unordered_set<int> set1;
        unordered_set<int> set2;
        unordered_set<int>* visited;
        unordered_set<int>* unvisited;
    
        public:
        LRUCache(int capacity) {
            _capacity = capacity;
            visited = &set1;
            unvisited = &set2;
        }
        
        int get(int key) {
            int res;
            auto iter = cache.find(key);
            if(iter == cache.end())
                return -1;
            else
                res = iter->second;
            update_set(key);
            return res;
        }
        //update the two set accordingly
        void update_set(int key)
        {
            visited->insert(key);
            unvisited->erase(key);
    		//visited set full, actually I want to do
    		//clear the visited set, and set the unvisited set
            if(visited->size() >= _capacity)
            {
                unordered_set<int>* temp;
                temp = visited;
                visited = unvisited;
                unvisited = temp;
                visited -> clear();
            }
        }
        
        void set(int key, int value) {
            if(cache.find(key) != cache.end())
                cache.erase(key);
    		//here I need to delete one element
            if(cache.size() == _capacity){
                if(unvisited->size() != 0){
                    int del_key = *(unvisited->begin());
    				//delete element in cache
                    cache.erase(del_key);
    				//delete element in unvisited set
                    unvisited->erase(del_key);
                }
                else cache.erase(cache.begin()->first);
            }
            pair<int,int> p(key, value);
            cache.insert(p);
            update_set(key);
        }
    };

  • 0
    M

    same here, maybe is the problem for the auto grader?


  • 0

    @yushaoshi You might want to briefly explain your code so others can help you.


  • 0
    Y

    Sure. The basic idea is I have two set, visited and unvisited. For each time an element is touched, it is added to the visited set and deleted from unvisited set. When visited set has all the elements in the cache, I clear the visited set and make the unvisited set full. That is an emulation of LRU. The tricky part I did is I didn't set the unvisited set manually. In stead, I exchange the two sets.


  • 0
    S

    @yushaoshi, you can prefer edit your question content with this explanation rather than reply in comments. Thx!


  • 0
    C

    I think your solution does not comply with LRU totally
    , when deleting the least used element. Here is other's solution.Implement LRU Cache


Log in to reply
 

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