数组中两个数的最大异或值(哈希表、前缀树：实现前缀树)
LeetCode题目：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/
哈希表解法
本题使用哈希表方法主要运用到一个定理：异或满足算法交换律。即如果a^b = c，那么必然 b ^ c = a。且数组中的元素都在 [ 0 , 2 31 ) [0,2^{31}) [0,231),因此可以确定数值的最高位是30位。
因此，可以假设从最高位开始进行计算。依次确定每一位是0还是1，即将上一次的计算值x乘以2再加上1，就是当前理想的最大值（因为此时新增为假设为1）
因此便可以应用异或的交换律，将数组中的数值num右移k位以映射为当前从30位到第k位的二进制数值。
再分别与当前的理想最大值进行异或。如果异或后的计算结果可以在哈希表中查询到，则说明存在num_i和num_j，可以异或组成最大值。
可能有人会疑问，这样循环30次，会不会可能导致每次异或的i和j，与上一轮k的不一样，那不就不符合唯一的i 和 j了嘛？
其实因为算法从高位计算，如果高位已经确定可以到达1，那么后面就由这个结果倒推罢了（交换律，在高位已经置1的条件下进行接下来的推导）因此并不会出现这种问题。
代码如下：
class Solution {
static final int HIGH_BIT = 30;
public int findMaximumXOR(int[] nums) {
int x = 0;
for (int k = HIGH_BIT; k >= 0; k--) {
Set<Integer> seen = new HashSet<Integer>();
//通过哈希表构建第30位到第k位的num数据
for (int num :nums) {
seen.add(num >> k);
}
//当前理想情况下x的最大值（即新增的第k位可以异或取1）
int x_Next = x * 2 + 1;
boolean found = false;
for (int num: nums) {
if (seen.contains(x_Next ^ (num >> k))) //异或满足交换律，所以num i和 num j异或是否可以得到当前位标记为1的数x_Next
{
found = true;
break;
}
}
if (found) {
x = x_Next;
}else {
x = x_Next - 1;//如果没有找到，则说明k位不能被置为1，所以-1即可
}
}
return x;
}
}
前缀树解法
首先先要了解前缀树是什么？Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
相关题目：实现 Trie (前缀树)
LeetCode题目：https://leetcode.cn/problems/implement-trie-prefix-tree/
对于字符串来说，相当于一个26叉树，每个分叉对应一个字母，从开始到结尾依次对应字符每个位置是否存在该字符。
代码如下：文章来源地址https://www.toymoban.com/news/detail-742667.html
class Trie {
private Trie[] children;
private boolean isEnd;
public Trie() {
children = new Trie[26];
isEnd = false;
}
public void insert(String word) {
Trie node = this;
for (int i = 0; i < word.length(); i++) {
char ch = word.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
node.children[index] = new Trie();
}
node = node.children[index];
}
node.isEnd = true;
}
public boolean search(String word) {
Trie node = searchPrefix(word);
return node != null && node.isEnd;
}
public boolean startsWith(String prefix) {
return searchPrefix(prefix) != null;
}
private Trie searchPrefix(String prefix) {
Trie node = this;
for (int i = 0; i < prefix.length(); i++) {
char ch = prefix.charAt(i);
int index = ch - 'a';
if (node.children[index] == null) {
return null;
}
node = node.children[index];
}
return node;
}
}
/**
* Your Trie object will be instantiated and called as such:
* Trie obj = new Trie();
* obj.insert(word);
* boolean param_2 = obj.search(word);
* boolean param_3 = obj.startsWith(prefix);
*/
字典树的应用
个人理解，字典树适合查询一些可重复的状态类别，比如当前需要查询的数据，是之前所有已经放入的数据总和的情况下，字典树十分方便。
可以将字典树应用在该题目上，主要用到的核心点有： 0 ≤ i ≤ j < n 0 ≤ i ≤ j < n 0≤i≤j<n ，以及逐位进行异或的思想。
首先假定字典树是从高位开始统计每一位的0或者1，且因为异或为i与j索引数字的异或。所以j只要保证一直比i要大1即可。
此时维护一个公共的字典树，并将其与num_j进行按位异或运算。并随着i的更新不断更新字典树内部的索引。即可完成。文章来源：https://www.toymoban.com/news/detail-742667.html
代码如下：
class Solution {
Trie root = new Trie();
static final int HIGH_BIT = 30;
public int findMaximumXOR(int[] nums) {
int x = 0;
for (int i = 1; i < nums.length; i++) {
add(nums[i - 1]);
x = Math.max(x, check(nums[i]));
}
return x;
}
private void add(int num) {
Trie cur = root;
for (int k = HIGH_BIT; k >= 0 ; k--) {
int bit = (num >> k) & 1;
if (cur.children[bit] == null) {
cur.children[bit] = new Trie();
}
cur = cur.children[bit];
}
}
private 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) {
if (cur.children[1] != null) {
cur = cur.children[1];
x = x * 2 + 1;
}else if (cur.children[0] != null){
x = x * 2;
cur = cur.children[0];
}else {
break;
}
}else {
if (cur.children[0] != null) {
cur = cur.children[0];
x = x * 2 + 1;
}else if (cur.children[1] != null){
x = x * 2;
cur = cur.children[1];
}else {
break;
}
}
}
return x;
}
}
class Trie{
public Trie[] children;
public Trie() {
children = new Trie[2];
}
}
到了这里，关于每日一题411数组中两个数的最大异或值(哈希表、前缀树：实现前缀树)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
