leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0432.cpp (2263B)

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