题目:
题解:
const int HIGH_BIT = 30;struct Trie {// 左子树指向表示 0 的子节点struct Trie* left;// 右子树指向表示 1 的子节点struct Trie* right;
};struct Trie* createTrie() {struct Trie* ret = malloc(sizeof(struct Trie));ret->left = ret->right = NULL;return ret;
}void add(struct Trie* root, int num) {struct Trie* cur = root;for (int k = HIGH_BIT; k >= 0; --k) {int bit = (num >> k) & 1;if (bit == 0) {if (!cur->left) {cur->left = createTrie();}cur = cur->left;} else {if (!cur->right) {cur->right = createTrie();}cur = cur->right;}}
}int check(struct Trie* root, int num) {struct 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(int* nums, int numsSize) {struct Trie* root = createTrie();int x = 0;for (int i = 1; i < numsSize; ++i) {// 将 nums[i-1] 放入字典树,此时 nums[0 .. i-1] 都在字典树中add(root, nums[i - 1]);// 将 nums[i] 看作 ai,找出最大的 x 更新答案x = fmax(x, check(root, nums[i]));}return x;
}