My solution (O(1) complexity for both) for your reference


  • 8
    U

    I used the following hash table:
    key->next younger key, next older key, value

    If you think about it, you will see that it enjoys the convenience of both a hash table and a linked list.

     class LRUCache{
        public:
            struct triple{
                int older;
                int younger;
                int value;
            };
            
            bool debug;
            int capacity;
            unordered_map<int, triple> cache;  //key, next younger key, next older key, value
            int o_key;//oldest key, valid only if cache is non-empty
            int y_key;//youngest key, valid only if cache is non-empty
            LRUCache(int capacity) { //assume capacity>0
                this->capacity=capacity;
                cache.clear();
                debug=0;
            }
            
            void print(){
                if (cache.empty()) cout<<"Empty!"<<endl;
                else{
                    int current_key=y_key;
                    while (true){
                        cout<<current_key<<':'<<cache[current_key].value<<' ';
                        if (current_key==o_key) break;
                        current_key=cache[current_key].older;
                    }
                    cout<<endl;
                }
            }
            
            int get(int key) {
                if (cache.count(key)>0){
                    
                    if (key!=y_key){  //need to update the ordering 
                        if (key==o_key){  //accessed key is the oldest one
                            o_key=cache[key].younger;
                            cache[key].older=y_key;
                            cache[y_key].younger=key;
                            y_key=key;
                        }
                        else{
                            cache[cache[key].younger].older=cache[key].older;
                            cache[cache[key].older].younger=cache[key].younger;
                            cache[key].older=y_key;
                            cache[y_key].younger=key;
                            y_key=key;
                        }
                    }
                    if (debug) print();
                    return cache[key].value;
                }
                if (debug) print();
                return -1;
            }
            
            void set(int key, int value) {
                if (cache.empty()){
                    o_key=key;
                    y_key=key;
                    cache[key].value=value;
                    if (debug) print();
                    return;
                }
                if (cache.count(key)>0){ //already present
                    cache[key].value=value;  //update value
                    bool temp_debug=debug;
                    debug=0;
                    get(key);
                    debug=temp_debug;
                }else{
                    cache[key].value=value;  //insert entry
                    cache[key].older=y_key;
                    cache[y_key].younger=key;
                    y_key=key;
                    if (cache.size()>capacity){ //delete the oldest one
                        o_key=cache[o_key].younger;
                        cache.erase(cache[o_key].older);
                    }
                }
                if (debug) print();
            }
        };

  • 0
    S

    Hi @uniqueness, really appreciate your sharing. However, it would be better describe your brief thought, it will help others understand your code easily.


  • 0
    U

    I have comments on the key points for every solution I posted. People should be able to get my idea from these comments. I added some more explanation to this one anyway. Can I ask why you closed my postings? My solutions should be very helpful for the community.


  • 0

    Hi @uniqueness, first, I want to say welcome and I appreciate your contribution to the community. If you have a question about your algorithm, feel free to ask a question. Discuss is not built for the purpose of sharing your solution, though in future OJ might have a separate feature for you to share your solution. If you would like to contribute to the community, I would suggest contributing answers to questions that other users had posted.


  • 0
    C
    This post is deleted!

Log in to reply
 

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