【LC周赛-371】 D. Trie树求最大异或对

【LC周赛-371】 D. Trie树求最大异或对

题意

• 给一个数组，求两个数满足|x-y|<=min(x,y)的异或最大值。

题解

• 从|x-y|<=min(x,y)知道，每个y可以考虑的x范围是 y / 2 <= x < y;
• 然后Trie树实现更优复杂度内，从窗口获得最大异或值
• 思路就是高位依次取值，具体看代码吧

代码

const int N = 1e6 + 5;
int trie[N][2];
int num[N];
int cnt = 1;

void trie_Insert(int x){
    int root = 0;
    for(int i = 20; i >= 0; -- i){
        int id = (x>>i)&1;
        if(!trie[root][id]) trie[root][id] = ++ cnt;
        root = trie[root][id];
        num[root] ++;
    }
}

void trie_del(int x) {
    int root = 0;
    for(int i = 20; i >= 0; -- i) {
        int id = (x>>i)&1;
        root = trie[root][id];
        num[root] --;
    }
}

int trid_Xormax(int x) {
    int root = 0;
    int res = 0;
    for(int i = 20; i >= 0; -- i) {
        int id = (x>>i)&1;
        if(num[trie[root][!id]]) {
            root = trie[root][!id];
            res = (res << 1) + 1;
        } else {
            root = trie[root][id];
            res = (res << 1) + 0; 
        }
    }
    return res;
}

class Solution {
public:
    int maximumStrongPairXor(vector<int>& nums) {
        memset(trie, 0, sizeof(trie));
        memset(num, 0, sizeof(num));
        cnt = 1;
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int l = 0, r = 1;
        int res = 0;
        trie_Insert(nums[0]);
        while(r < n) {
            while(l < r && nums[l] * 2 < nums[r]) {
                trie_del(nums[l]);
                l ++;
            }
            res = max(res, trid_Xormax(nums[r]));
            trie_Insert(nums[r]);
            r ++;
        }
        return res;
    }
};