c++11, hashTable+list, 83ms


  • 0
    X

    The idea is that create one list. And use the haspMap to store the pointer to the list. And everytime we operate some pointer, we move it to end->before. Then everytime when we need to change one list node, it must be before->next.

    class my_list {
    public:
        my_list(int key, int value): key(key), value(value), next(NULL), before(NULL) {}
        int key;
        int value;
        my_list* next;
        my_list* before;
        ~my_list() {
            if (next) {
                delete next;
                next = NULL;
            }
        }
    };
    
    class LRUCache {
    public:
        LRUCache(int capacity) {
            left_capacity = capacity;
            begin = new my_list(0, 0);
            end = new my_list(0, 0);
            end->before = begin;
            begin->next = end;
        }
        
        int get(int key) {
            if (hash_map.find(key) == hash_map.end()) {
                return -1;
            } else {
                my_list* result = hash_map[key];
                put_to_end(result);
                return result->value;
            }
        }
        
        void put(int key, int value) {
            if (hash_map.find(key) == hash_map.end() && left_capacity > 0) {
                my_list* node = new my_list(key, value);
                hash_map.insert({key, node});
                node->before = end->before;
                node->next = end;
                node->before->next = node;
                node->next->before = node;
                left_capacity--;
            } else if (hash_map.find(key) == hash_map.end()) {
                my_list* erase_node = begin->next;
                hash_map.erase(erase_node->key);
                hash_map.insert({key, erase_node});
                erase_node->key = key;
                erase_node->value = value;
                put_to_end(erase_node);
            } else if (hash_map.find(key) != hash_map.end()) {
                my_list* result = hash_map[key];
                result->value = value;
                put_to_end(result);
            }
        }
    private:
        std::unordered_map<int, my_list*> hash_map; // store the list pointer
        int left_capacity;
        my_list* begin;
        my_list* end;
        void put_to_end(my_list* node) {
            node->before->next = node->next;
            node->next->before = node->before;
            node->before = end->before;
            end->before->next = node;
            node->next = end;
            end->before = node;
        }
    };
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

Log in to reply
 

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