leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0432.cpp (2263B)

      1 class AllOne {
      2     struct Node {
      3         int freq = 0;
      4         Node *prev = nullptr;
      5         Node *next = nullptr;
      6         unordered_set<string> keys;
      7     };
      8 
      9     unordered_map<string, Node *> map;
     10     Node head = {0, nullptr, &tail};
     11     Node tail = {0, &head, nullptr};
     12 
     13   public:
     14     void inc(const string &key) {
     15         if (map.find(key) != map.end()) {
     16             Node *node = map[key];
     17             int freq = node->freq;
     18             node->keys.erase(key);
     19 
     20             Node *nnode = node->next;
     21             if (nnode == &tail || nnode->freq != freq + 1) {
     22                 map[key] = node->next = nnode->prev = new Node(freq + 1, node, nnode, {key});
     23             } else {
     24                 nnode->keys.insert(key);
     25                 map[key] = nnode;
     26             }
     27 
     28             if (node->keys.empty()) {
     29                 removeNode(node);
     30             }
     31         } else {
     32             Node *firstNode = head.next;
     33             if (firstNode == &tail || firstNode->freq > 1) {
     34                 map[key] = head.next = firstNode->prev = new Node(1, &head, firstNode, {key});
     35             } else {
     36                 firstNode->keys.insert(key);
     37                 map[key] = firstNode;
     38             }
     39         }
     40     }
     41 
     42     void dec(const string &key) {
     43         if (map.find(key) == map.end()) {
     44             return;
     45         }
     46 
     47         Node *node = map[key];
     48         node->keys.erase(key);
     49 
     50         int freq = node->freq;
     51         if (freq == 1) {
     52             map.erase(key);
     53         } else {
     54             Node *pnode = node->prev;
     55             if (pnode == &head || pnode->freq != freq - 1) {
     56                 map[key] = pnode->next = node->prev = new Node(freq - 1, pnode, node, {key});
     57             } else {
     58                 pnode->keys.insert(key);
     59                 map[key] = pnode;
     60             }
     61         }
     62 
     63         if (node->keys.empty()) {
     64             removeNode(node);
     65         }
     66     }
     67 
     68     string getMaxKey() const { return tail.prev == &head ? "" : *(tail.prev->keys.begin()); }
     69 
     70     string getMinKey() const { return head.next == &tail ? "" : *(head.next->keys.begin()); }
     71 
     72   private:
     73     void removeNode(Node *node) {
     74         Node *pnode = node->prev;
     75         Node *nnode = node->next;
     76 
     77         pnode->next = nnode;
     78         nnode->prev = pnode;
     79 
     80         delete node;
     81     }
     82 };