每日一题411数组中两个数的最大异或值(哈希表、前缀树：实现前缀树)

数组中两个数的最大异或值(哈希表、前缀树：实现前缀树)

LeetCode题目：https://leetcode.cn/problems/maximum-xor-of-two-numbers-in-an-array/

哈希表解法

  本题使用哈希表方法主要运用到一个定理：异或满足算法交换律。即如果a^b = c，那么必然 b ^ c = a。且数组中的元素都在$[0,2^{31})$,因此可以确定数值的最高位是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叉树，每个分叉对应一个字母，从开始到结尾依次对应字符每个位置是否存在该字符。

代码如下：

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\le i\le j<n$ ，以及逐位进行异或的思想。

  首先假定字典树是从高位开始统计每一位的0或者1，且因为异或为i与j索引数字的异或。所以j只要保证一直比i要大1即可。

  此时维护一个公共的字典树，并将其与num_j进行按位异或运算。并随着i的更新不断更新字典树内部的索引。即可完成。

代码如下：

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];}
}