C++ full custom single linked list + unordered_map, beats 99.52%


  • 0
    A

    Not really satisfied with the performance of STL list / forward_list, I write my own single linked list.
    Yes, single linked list is enough for this problem. No need to waste space on double linked list.

    17 / 17 test cases passed
    Status: Accepted
    Runtime: 62 ms
    Your runtime beats 99.52% of cpp submissions

    class LRUCache{
    public:
        LRUCache(int capacity) {
            c = 0;
            cc = capacity;
            h = new Node[cc+1];
            for (uint i = 0; i < cc; h[i++].n = h+i);
            h[cc].n = h;
            t = &h[cc].n;
        }
        int get(int key) {
            auto i = m.find(key);
            if (i == m.end()) return -1;
            else {
                Node **p = i->second, *q = *p;
                if (&q->n != t) {
                    *p = q->n;
                    m[q->n->k] = p;
                    q->n = *t;
                    *t = q;
                    i->second = t;
                    t = &q->n;
                }
                return q->v;
            }
        }
        void set(int key, int value) {
            auto i = m.find(key);
            if (i != m.end()) {
                Node **p = i->second, *q = *p;
                q->v = value;
                if (&q->n != t) {
                    *p = q->n;
                    m[q->n->k] = p;
                    q->n = *t;
                    *t = q;
                    i->second = t;
                    t = &q->n;
                }
            } else {
                if (c < cc) c++;
                else m.erase((*t)->n->k);
                (*t)->k = key;
                (*t)->v = value;
                m[key] = t;
                t = &(*t)->n;
            }
        }
    private:
        struct Node {
            int k;
            int v;
            Node *n;
        };
        uint c, cc;
        Node *h, **t;
        unordered_map<int, Node**> m;
    };

  • 0
    S

    lost something
    delete[] h


  • 0
    A

    @sefs You are right, but that should be in the destructor.


Log in to reply
 

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