在給定的N個整數A1，A2……ANA1，A2……AN中選出兩個進行xor（異或）運算，得到的結果最大是多少？
輸入格式
第一行輸入一個整數N，
第二行輸入N個整數A1A1～ANAN，
輸出格式
輸出一個整數表示答案，
資料范圍
1≤N≤1051≤N≤105,
0≤Ai<2310≤Ai<231
輸入樣例：
3
1 2 3
輸出樣例：
3
暴力做法：O（n^2）
import java.util.Scanner; public class Main{ static int a[]=new int[100005]; public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); for(int i=0;i<n;i++) a[i]=scan.nextInt(); int max=-1; for(int i=0;i<n;i++) for(int j=0;j<i;j++) max=Math.max(max, a[i]^a[j]); System.out.println(max); } }
對此步做優化
for(int i=0;i<n;i++) for(int j=0;j<i;j++)//----這一步 max=Math.max(max, a[i]^a[j]);
O（n*logn）
異或運算，同為0，不同為1
建立trie樹，左0右1
先插入一個整數，然后查詢，查詢程序中，如果u是1，就盡可能往0那邊走；如果u是0，就盡可能往1那邊走
AC代碼：
import java.util.Scanner; public class Main{ static final int N=100005,M=N*31; static int a[]=new int[N]; static int son[][]=new int [M][2]; static int idx=0; static void insert(int x){ int p=0; for(int i=30;i>=0;i--){ int u=x>>i&1; if(son[p][u]==0) son[p][u]=++idx; p=son[p][u]; } } static int query(int x){ int p=0,res=0; for(int i=30;i>=0;i--){ int u=x>>i&1; //如果u是1，就盡可能往0那邊走；如果u是0，就盡可能往1那邊走 if(son[p][u==1?0:1]!=0){ p=son[p][u==1?0:1]; res=res*2+(u==1?0:1);//加括號，優先級問題 } else{ p=son[p][u]; res=res*2+u; } } return res; } public static void main(String[] args) { Scanner scan=new Scanner(System.in); int n=scan.nextInt(); for(int i=0;i<n;i++) a[i]=scan.nextInt(); int res=0; for(int i=0;i<n;i++){ insert(a[i]); int num=query(a[i]); res=Math.max(res, a[i]^num); } System.out.println(res); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102328.html
標籤：其他
下一篇：關于matlab的問題