421. Maximum XOR of Two Numbers in an Array[Medium](Leetcode每日一题-2021.05.15)--抄答案

本文主要是介绍421. Maximum XOR of Two Numbers in an Array[Medium](Leetcode每日一题-2021.05.15)--抄答案，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 ≤ i ≤ j < n.

Constraints:

1 <= nums.length <= 2 * 104
0 <= nums[i] <= 231 - 1

Example1

Input: nums = [3,10,5,25,2,8]
Output: 28
Explanation: The maximum result is 5 XOR 25 = 28.

Example2

Input: nums = [0]
Output: 0

Example3

Input: nums = [2,4]
Output: 6

Example4

Input: nums = [8,10,2]
Output: 10

Example5

Input: nums = [14,70,53,83,49,91,36,80,92,51,66,70]
Output: 127

Solution

struct Trie {// 左子树指向表示 0 的子节点Trie* left = nullptr;// 右子树指向表示 1 的子节点Trie* right = nullptr;Trie() {}
};class Solution {
private:// 字典树的根节点Trie* root = new Trie();// 最高位的二进制位编号为 30static 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(vector<int>& 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;}
};