AcWing 143. 最大异或对 java
原题链接
简单
作者:
sowei
,
2021-05-18 02:22:12
,
所有人可见
,
阅读 265
import java.util.*;
class TrieNode{
TrieNode[] children;
TrieNode() {
children = new TrieNode[2];
}
}
public class Main{
public static void main(String args[]) {
int res = 0;
TrieNode root = new TrieNode();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] nums = new int[n];
for(int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
for(int num : nums) {
insert(num, root);
}
for(int num : nums) {
res = Math.max(res, query(num, root));
}
System.out.println(res);
}
private static void insert(int num, TrieNode root) {
TrieNode node = root;
for(int i = 30; i >= 0; i--) {
int curBit = num >> i & 1;
if(node.children[curBit] == null) node.children[curBit] = new TrieNode();
node = node.children[curBit];
}
}
private static int query(int num, TrieNode root) {
int res = 0;
TrieNode node = root;
for(int i = 30; i >= 0; i--) {
int curBit = num >> i & 1;
if(node.children[curBit ^ 1] != null) {
node = node.children[curBit ^ 1];
res += 1 << i; // res = res * 2 + 1
} else {
node = node.children[curBit];
// res = res * 2 + 0;
}
}
return res;
}
}