题目421. 数组中两个数的最大异或值题解. - 力扣LeetCodestruct Trie { // 左子树指向表示 0 的子节点 Trie* left nullptr; // 右子树指向表示 1 的子节点 Trie* right nullptr; Trie() {} }; class Solution { private: // 字典树的根节点 Trie* root new Trie(); // 最高位的二进制位编号为 30 static constexpr int HIGH_BIT 30; public: void add(int num) { Trie* cur root; for (int k HIGH_BIT; k 0; --k) { int bit (num k) 1; if (bit 0) { if (!cur-left) { cur-left new Trie(); } cur cur-left; } else { if (!cur-right) { cur-right new Trie(); } cur cur-right; } } } int check(int num) { Trie* cur root; int x 0; for (int k HIGH_BIT; k 0; --k) { int bit (num k) 1; if (bit 0) { // a_i 的第 k 个二进制位为 0应当往表示 1 的子节点 right 走 if (cur-right) { cur cur-right; x x * 2 1; } else { cur cur-left; x x * 2; } } else { // a_i 的第 k 个二进制位为 1应当往表示 0 的子节点 left 走 if (cur-left) { cur cur-left; x x * 2 1; } else { cur cur-right; x x * 2; } } } return x; } int findMaximumXOR(vectorint nums) { int n nums.size(); int x 0; for (int i 1; i n; i) { // 将 nums[i-1] 放入字典树此时 nums[0 .. i-1] 都在字典树中 add(nums[i - 1]); // 将 nums[i] 看作 ai找出最大的 x 更新答案 x max(x, check(nums[i])); } return x; } };class Solution { public: /** * param nums: * return: the maximum result of ai XOR aj, where 0 ≤ i, j n */ int findMaximumXOR(vectorint nums) { // Write your code here if (nums.size() 0) { return {}; } Trie* root new (std::nothrow)Trie; for (auto num : nums) { insert(root, num); } int result 0; for (auto num : nums) { int val search(root, num); result max(result, val ^ num); } return result; } private: struct Trie { std::vectorTrie* next; bool end; int num; Trie() { num -1; end false; next.resize(2, nullptr); } }; void insert(Trie* root, int num) { for (int i 30; i 0; --i) { int index (num i) 1; if (!root-next[index]) { root-next[index] new (std::nothrow) Trie; } root root-next[index]; } root-num num; root-end true; } int search(Trie* root, int num) { for (int i 30; i 0; --i) { int index (num i) 1; if (root-next[1-index]) { root root-next[1-index]; } else { root root-next[index]; } } return root-num; } };