my c++ solution, not very neat, but sometimes it can beat 100%, 53ms


  • 0
    S

    ...
    /*
    *the private struct Node presents the priority of Cache,
    *head->next is the least recently used
    *use list<Node *> hash[prime] to store the prev Node of the present Node
    *to change the order of Cache
    *cap means capacity, siz means the cuurent number of used Cache
    */

    #define prime 997
    class LRUCache {
    private:
    struct Node {
    int key, val;
    Node *next;
    Node(int a = 0, int b = 0, Node *n = nullptr) : key(a), val(b), next(n) {}
    };

    public:
    LRUCache(int capacity) : head(new Node()), tail(head), cap(capacity), siz(0) {}

    int get(int key)
    {
        //check wether the key is in the Cache(hash table)
        if (hash[key % prime].empty())
            return -1;
        auto p = hash[key % prime].begin();
        Node *now = nullptr;
        for (; p != hash[key % prime].end(); ++p)
            if ((*p)->next->key == key) {
                now = *p;
                break;
            }
        if (now == nullptr) return -1;
        
        //if we need to change the priority of this Node
        if (now->next != tail) {
            tail->next = now->next;
            now->next = now->next->next;
            *p = tail;
            tail = tail->next;
            tail->next = nullptr;
            //and this
            for (auto p = hash[now->next->key % prime].begin(); p != hash[now->next->key % prime].end(); ++p)
                if (*p == tail) {
                    *p = now;
                    break;
                }
        }
        return tail->val;
    }
    
    void set(int key, int value)
    {
        bool flag = true;
        //the same as get()
        auto p = hash[key % prime].begin();
        Node *now = nullptr;
        if (hash[key % prime].empty())
            flag = false;
        else {
            for (; p != hash[key % prime].end(); ++p)
                if ((*p)->next->key == key) {
                    now = *p;
                    break;
                }
            if (now == nullptr) flag = false;
        }
    
        if (flag) {
            //this code is exactly the same as above...
            if (now->next != tail) {
                tail->next = now->next;
                now->next = now->next->next;
                *p = tail;
                tail = tail->next;
                tail->next = nullptr;
                tail->val = value;
    
                for (auto p = hash[now->next->key % prime].begin(); p != hash[now->next->key % prime].end(); ++p)
                    if (*p == tail) {
                        *p = now;
                        break;
                    }
            }
            tail->val = value;
        } else {
            if (siz == cap) { //if full
                for (auto q = hash[head->next->key % prime].begin(); q != hash[head->next->key % prime].end(); ++q) {
                    if (*q == head) {
                        q = hash[head->next->key % prime].erase(q);
                        break;
                    }
                }
    
                Node *tmp = head->next;
                delete head;
                head = tmp;
                --siz;
            }
            ++siz;
            tail->next = new Node(key, value);
            hash[key % prime].push_back(tail);
            tail = tail->next;
        }
    }
    

    private:
    Node *head, *tail;
    int cap, siz;
    list<Node *> hash[prime];
    };
    ...


Log in to reply
 

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