C++ beats 100%


  • 0
    A
    #include <iostream>
    #include <random>
    #include <unordered_map>
    
    using namespace std;
    
    template <class N> struct node {
      N *prev = nullptr, *next = nullptr;
      void attach(N *o) {
        if (next) {
          next->prev = o;
          o->next = next;
        }
        next = o;
        o->prev = (N*)this;
      }
    };
    
    template <class N> struct list {
      N *head, *tail;
      list() { head = tail = nullptr; }
    
      list(N *n) { head = tail = n; }
    
      bool is_empty() { return head == nullptr; }
    
      void detach(N *n) {
        if (head == n)
          head = n->next;
        if (tail == n)
          tail = n->prev;
        if (n->prev)
          n->prev->next = n->next;
        if (n->next)
          n->next->prev = n->prev;
        n->prev = n->next = nullptr;
      }
    
      void append(N *n) {
        if (!is_empty()) {
          tail->next = n;
          n->prev = tail;
          tail = n;
        } else {
          head = tail = n;
        }
      }
    
      void prepend(N *n) {
        if (!is_empty()) {
          head->prev = n;
          n->next = head;
          head = n;
        } else {
          head = tail = n;
        }
      }
    
      N *pop() {
        auto ret = head;
        detach(head);
        return ret;
      }
    };
    
    struct cnode;
    struct pnode : node<pnode> {
      ::list<cnode> c;
      int freq;
      pnode(cnode *n, int f) : c(n) { freq = f; }
    
      void append(cnode *n) {
        c.append(n);
      }
    
      void detach(cnode *n) {
        c.detach(n);
      }
    
      cnode *pop() {
        return c.pop();
      }
    
      bool is_empty() {
        return c.is_empty();
      }
    };
    
    struct cnode : node<cnode> {
      pnode *p;
      int k, v;
      cnode(int k, int v) : k(k), v(v) {}
      void detach() {
        p->detach(this);
        p = nullptr;
      }
    };
    
    class LFUCache {
    public:
      LFUCache(int capacity) { cap = capacity; }
    
      int get(int key) {
        auto ci = map.find(key);
        if (ci == map.end())
          return -1;
        auto c = ci->second;
        adjust(c);
        return c->v;
      }
    
      void set(int key, int value) {
        if (cap <= 0)
          return;
        if (map.find(key) == map.end()) { // insert key
          if (map.size() == cap) {        // evict
            auto p = lfu.head;
            auto c = p->pop();
            map.erase(c->k);
            delete c;
            if (p->is_empty()) {
              lfu.detach(p);
              delete p;
            }
          }
    
          // insert
          auto c = new cnode{key, value};
          map[key] = c;
          if (!lfu.is_empty() && lfu.head->freq == 1) {
            c->p = lfu.head;
            lfu.head->append(c);
          } else {
            auto p = new pnode{c, 1};
            c->p = p;
            lfu.prepend(p);
          }
        } else { // adjust list
          auto c = map[key];
          c->v = value;
          adjust(c);
        }
      }
    
      void print() {
        auto p = lfu.head;
        cout << "=======" << endl;
        while (p) {
          cout << "*" << p->freq << " : ";
          auto c = p->c.head;
          while (c) {
            cout << c->k << (p->c.tail == c ? "\n" : "-->");
            c = c->next;
          }
          cout << "|" << endl;
          p = p->next;
        }
        cout << "=======" << endl;
      }
    
    private:
      int cap;
    
      unordered_map<int, cnode *> map;
    
      ::list<pnode> lfu;
    
      void adjust(cnode *c) {
        auto p = c->p;
        c->detach();
        auto np = p->next;
        if (!np || np->freq != p->freq + 1) {
          np = new pnode{c, p->freq + 1};
          p->attach(np);
        } else {
          np->append(c);
        }
        c->p = np;
        if (p->is_empty()) {
          lfu.detach(p);
          delete p;
        }
      }
    };
    

Log in to reply
 

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