AcWing 143. 【Java】最大异或对
原题链接
简单
作者:
tt2767
,
2019-12-19 00:02:36
,
所有人可见
,
阅读 863
// 弹幕一个有意思的解释,异或: 二进制不进位加法
import java.util.*;
public class Main{
class Tire{
int[][] bin;
int idx;
public Tire(int n){
bin = new int[n][2];
idx = 0;
}
public void set(int x){
int p = 0;
for (int i = 30 ;i >= 0 ; i--){
// int cur = x & (1 << i); // 当时想移到高位,但是这样的话结果大概率不是0 or 1
int cur = (x >> i) & 1;
if (bin[p][cur] == 0) bin[p][cur] = ++idx;
p = bin[p][cur];
}
}
public int getMatch(int x){
int p = 0, res = 0;
for (int i =30 ; i >= 0 ; i--){
// int now = x & (1 << i);
// if (bin[p][now^1] != 0) now ^= 1;
// res |= now; // 直接| 是可以的,但是取now写错了。。。
// p = bin[p][now];
int cur = (x >> i ) & 1;
if (bin[p][cur^1] != 0){
res |= (1 << i);
cur ^= 1;
}
p = bin[p][cur];
}
return res;
}
}
void run(){
int n = jin.nextInt();
List<Integer> list = new ArrayList<>();
for (int i = 0 ; i < n ; i++) list.add(jin.nextInt());
System.out.println(solve(list));
}
int solve(List<Integer> list){
Tire tire = new Tire(3000000);
for (int i = 0 ; i < list.size(); i++) tire.set(list.get(i)) ;
int res = -1;
for(int i = 0 ; i < list.size(); i++){
int y = list.get(i);
// res = Math.max(res, y ^ tire.getMatch(y));
res = Math.max(res, tire.getMatch(y)); // 其实getMatch 直接求出最大的异或了,因为找每位^1就是最大异或
}
return res;
}
private Scanner jin = new Scanner(System.in);
public static void main(String[] args) throws Exception {new Main().run();}
}