leetcode

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

0421.cpp (1024B)

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