算法基礎集訓（第26天，共106天）------＞徹底搞懂Trie樹之【最大異或對】，附詳細思路和圖文代碼解析

目錄

一：概念定義 

二：題目描述 

三：思路分析 

四：萬年無誤代碼模闆 （含詳細解析）

一：概念定義 

異或：兩個數字轉化為二進制數，從低位開始進行異或運算。異或也算也可稱之為不進位加法。這題和上一題字元串統計有異曲同工之妙，兩者一起食用效果較好。

二：題目描述 

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

輸入格式

第一行輸入一個整數 N。

第二行輸入 N 個整數 。

輸出格式

輸出一個整數表示答案

資料範圍

1 ≤ N ≤ 10^5,

0 ≤ Ai < 2^31

輸入樣例

3

1 2 3

輸出樣例

3

三：思路分析 

這題當然有誰都能想到的樸素做法，兩層for循環，但是會逾時，是以需要改進算法，利用Trie樹進行簡化。

首先需要搞懂幾個目标：

1.數字要大，說明其轉化為二進制的1要盡可能多且在最高位是1的情況下位數盡可能多。

2.轉化為二進制的最大數字不會超過2^31,是以最多是31位進行存儲。

3.兩個數字異或要盡可能大，則要求兩個數字轉化為二進制之後，其對應數位的數字要盡可能不同。

畫一個圖幫助了解内部實作：

四：萬年無誤代碼模闆 （含詳細解析）

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x)//建造樹的過程
{
    int p = 0;
      for(int i = 30; i >= 0 ; i --)
      {
        int u = x >> i & 1;//從高位取數
        if (!son[p][u]) son[p][u] = ++idx;//不存在這個節點就創造這個節點
        p = son[p][u];//每次都要走到下一個節點
      }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int u = x >> i & 1;//從高位取數
        if (son[p][!u])//如果存在非的數，就往非的方向走
        {
            res += 1 << i;//将1左移i位
            p = son[p][!u];
        }
        else p = son[p][u];//不存在非的數字，隻能順勢而下
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));

    printf("%d\n", res);
    return 0;
}
           

 創作不易，建議點贊+收藏+關注，以免找不到寶貝文章了。

基礎集訓結束後将開展拔高系列