leetcode

Solution to some Leetcode problems written in C++

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

0677.cpp (2128B)

0 // Only Trie 1 class MapSum { 2 struct Node { 3 Node(){}; 4 Node *children[27] = {nullptr}; 5 int &value = reinterpret_cast<int &>(children[0]); 6 int trail = 0; 7 }; 8 9 Node *trie = new Node(); 10 11 public: 12 void insert(const string &key, int val) { 13 Node *prev = trie; 14 for (const char c : key) { 15 const int idx = c & 0x1F; 16 if (!prev->children[idx]) { 17 prev = nullptr; 18 break; 19 }; 20 prev = prev->children[idx]; 21 } 22 23 const int diff = prev ? val - prev->value : val; 24 25 Node *crnt = trie; 26 for (const char c : key) { 27 const int idx = c & 0x1F; 28 crnt->trail += diff; 29 if (!crnt->children[idx]) crnt->children[idx] = new Node(); 30 crnt = crnt->children[idx]; 31 } 32 crnt->value = val; 33 } 34 35 int sum(const string &prefix) const { 36 const Node *crnt = trie; 37 for (const char c : prefix) { 38 const int idx = c & 0x1F; 39 if (!crnt->children[idx]) return 0; 40 crnt = crnt->children[idx]; 41 } 42 return crnt->value + crnt->trail; 43 } 44 }; 45 46 // Trie + hash map 47 class MapSum { 48 struct Node { 49 Node(){}; 50 Node *children[27] = {nullptr}; 51 int &value = reinterpret_cast<int &>(children[0]); 52 }; 53 54 Node *trie = new Node(); 55 unordered_map<string, int> um; 56 57 public: 58 void insert(const string &key, int val) { 59 const int diff = val - um[key]; 60 61 Node *crnt = trie; 62 for (const char c : key) { 63 const int idx = c & 0x1F; 64 crnt->value += diff; 65 if (!crnt->children[idx]) crnt->children[idx] = new Node(); 66 crnt = crnt->children[idx]; 67 } 68 crnt->value += diff; 69 um[key] = val; 70 } 71 72 int sum(const string &prefix) const { 73 const Node *crnt = trie; 74 for (const char c : prefix) { 75 const int idx = c & 0x1F; 76 if (!crnt->children[idx]) return 0; 77 crnt = crnt->children[idx]; 78 } 79 return crnt->value; 80 } 81 };