AcWing 143. 最大异或对-java
原题链接
中等
作者:
韦德
,
2021-06-13 13:11:08
,
所有人可见
,
阅读 273
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
static int[][] trie;
static int[] arr;
static int index = 1;
static void init(int n){
trie = new int[n * 31][2];
arr = new int[n];
}
static void initArr(String[] arrS){
for (int i = 0;i<arrS.length;i++){
arr[i] = Integer.parseInt(arrS[i]);
}
}
// 向trie中插入一个数
static void insert(int num){
int p = 0;
for (int i = 30;i>=0;i--){
int cur = (num >> i) & 1;
if(trie[p][cur] == 0){
trie[p][cur] = index;
index++;
}
p = trie[p][cur];
}
}
// 查询trie中和num异或最大的数
static int query(int num){
int p = 0;
int res = 0;
// 因为数据都是正数,第32为都是0(符号位),所以只用考虑前31位
for (int i = 30;i>=0;i--){
int cur = (num >> i) & 1;
int need = cur == 0 ? 1 : 0;
if(trie[p][need] != 0){
p = trie[p][need];
res = (res << 1) + need;
}else{
// 若没有需要的,那么trie中一定有需要的数,因此之前插入的数在第i位一定有一个数
p = trie[p][cur];
res = (res << 1) + cur;
}
}
return res;
}
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(reader.readLine());
init(n);
String[] arrS = reader.readLine().split(" ");
initArr(arrS);
int res = 0;
for (int i = 0;i<n;i++){
insert(arr[i]);
int cur = query(arr[i]);
res = Math.max(res,cur ^ arr[i]);
}
System.out.println(res);
}
}