《藍橋杯每日一題》trie樹·143. 最大異或對

1. 題目描述

在給定的 N 個整數 A1，A2……AN 中選出兩個進行 xor（異或）運算，得到的結果最大是多少？

輸入格式

第一行輸入一個整數 N。

第二行輸入 N個整數 A1～AN。

輸出格式

輸出一個整數表示答案。

資料範圍

1≤N≤105,

0≤Ai<231

輸入樣例：

3

1 2 3

輸出樣例：

3

2.思路分析

從數組裡挑兩個數 這兩個數要滿足異或結果最大

暴力枚舉O(n2)O(n2) 一次枚舉這兩個數 取異或最大值

Trie樹優化 O(n∗31)O(n∗31)

對于某個數A 能與它異或得到較大結果的另一個數記為B

那麼當A、B 越高位的數字不同時 異或結果也就越大

什麼意思呢 舉個例子

A = 1010, B = 1111 AB二進制表示中 最高的不同位在右起第 三 位 此時異或結果為A^B=0101

A = 1010, B = 0011 AB二進制表示中 最高的不同位在右起第 四 位 此時異或結果為A^B=1001

顯然這時候B=0011才是我們需要的

如果有另一個B 使得不同位也在右起第 四 位呢 那就看下一個不同位誰比較高

A=1010, B=0111 觀察到第二高的不同位在右起第 三 位，異或結果為 A^B=1101

而B=0011第二高的不同位在右起第 二 位，異或結果為 A^B=1001

顯然這時候就要選新的B了 B=0111

上面隻是原理 代碼怎麼實作呢 這裡要靠Trie樹

每次選一個數A 然後從已經記錄的數字裡找能與它組成最大異或和的另一個數B

1. 按照A的二進制表示數從高到低依次周遊

2. 每次在樹中 找該位置的表示數的不同的數 （不知道取什麼名了 如果A的某位是1就找0 是0就找1）

3. 如果樹中恰好有記錄到“在本位置不同的數” 那就移到對應的子樹 繼續判斷下一個位置

4. 但如果樹中沒有記錄到“在本位置不同的數” （即所有數在這個位置都跟A一樣） 那就隻好被迫移到對應的那棵子樹上了

5. 周遊到第0位（也就是葉子節點） 就能找到我們所需要的數B了

記異或和位res 初始時 res = 0

當某個位置有不同的數時 這個位置異或完的結果必定為 1 是以res = (res << 1) + 1

如果沒有不同的數 隻好選擇相同的 那這個位置異或完的結果必定為 0 是以res = (res << 1) + 0

直到周遊完葉子節點 res就是A能取得的最大異或和

3.Ac代碼

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    static int M=31,N=31*100010,idx=0;
    static int[][] trie=new int[N][2];
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());
        String []s=br.readLine().split(" ");
        for (int i = 1; i <=n; i++) {
            insert(Integer.parseInt(s[i-1]));
        }
        int ans=-1;
        for (int i = 1; i <=n; i++) {
            int t=Integer.parseInt(s[i-1]);
            ans=Math.max(ans,query(t));
        }
        System.out.println(ans);

    }

    private static int query(int x) {
        int t=0,res=0;
        for(int i=M-1;i>=0;i--){
            int k=((x>>i)&1)^1;   //因為要找的是相反的數，是以異或一下
            if(trie[t][k]!=0){   //如果存過相反的，那麼更新一下res并到下一節點
                t=trie[t][k];
                res=(res << 1) + 1;
            }else {
                t=trie[t][k^1];
                res<<=1;
            }
        }
        return res;
    }

    private static void insert(int x) {
        int t=0;
        for(int i=M-1;i>=0;i--){
            int k=(x>>i) &1;   // 取得第i位上的數  （這裡i從右往左 從0開始）
            //如果沒有建立過，那麼先存進去
            if(trie[t][k]==0)  trie[t][k]=++idx;
            t=trie[t][k];  // 移到下一節點
        }
    }

}
           

感謝你能看完， 如有錯誤歡迎評論指正，有好的思路可以交流一波，如果對你有幫助的話，點個贊支援下