leetcode

Solution to some Leetcode problems written in C++

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

0421.cpp (1024B)

0 class Solution { 1 struct Node { 2 Node *child[2] = {nullptr, nullptr}; 3 }; 4 5 Node trie; 6 7 void insert(const int n) { 8 Node *crnt = &trie; 9 bitset<32> bs = n; 10 11 for (int i = 31; i >= 0; i--) { 12 const auto c = bs[i]; 13 if (!crnt->child[c]) crnt->child[c] = new Node(); 14 crnt = crnt->child[c]; 15 } 16 } 17 18 int find(const int n) const { 19 const Node *crnt = &trie; 20 bitset<32> bs = n; 21 22 int res = 0; 23 for (int i = 31; i >= 0; i--) { 24 const auto c = bs[i]; 25 if (crnt->child[!c]) { 26 crnt = crnt->child[!c]; 27 res += 1 << i; 28 } else { 29 crnt = crnt->child[c]; 30 } 31 } 32 return res; 33 } 34 35 public: 36 int findMaximumXOR(const vector<int> &nums) { 37 for (const int n : nums) 38 insert(n); 39 40 int res = 0; 41 for (const int n : nums) 42 res = max(res, find(n)); 43 return res; 44 } 45 };