两个数组之间的最大异或 |树

Question

给定两个整数向量 A 和 B，我们必须从每个向量中选择一个元素，使得它们的 xor 为最大值，我们需要 return 这个最大值 xor来自函数的值 int Solution::solve(vector &A, vector &B).

我发现下面的代码没有通过所有测试用例当我全局声明和初始化头指针时就在 class 三节点的正下方。这是为什么？

代码

class Trienode
{
    public:
        Trienode* left;
        Trienode* right;

        Trienode()
        {
            left=0;
            right=0;
        }
};

// Trienode* head = new Trienode;


int Max_Xor_Pair(Trienode* head, vector<int> B)
{
    int n=B.size();
    int max_xor=INT_MIN;

    for(int i=0; i<n; i++)
    {
        int pair1 = B[i];
        int pair2 = 0;
        Trienode* curr=head;

        for(int j=31; j>=0; j--)
        {
            int bit = (pair1>>j)&1;

            if(bit)
            {
                if(curr->left)
                    curr=curr->left;
                else
                {
                    curr=curr->right;
                    pair2 += pow(2,j);
                }
                    
            }
            else
            {
                if(curr->right)
                {
                    curr=curr->right;
                    pair2 += pow(2,j);
                }
                else
                    curr=curr->left;
            }

        }

        int curr_xor = pair1 ^ pair2;
        max_xor = max(max_xor, curr_xor);
    }
    
    return max_xor;
}

void Insert(Trienode* head, int num)
{
    Trienode* curr=head;
    for(int i=31; i>=0; i--)
    {
        int x = num;
        int bit= (x>>i)&1;

        if(bit)
        {
            if(!curr->right)
            {
                Trienode* temp = new Trienode;
                curr->right=temp;
            }
            curr=curr->right;            
        }
        else
        {
            if(!curr->left)
            {
                Trienode* temp = new Trienode;
                curr->left=temp;
            }
            curr=curr->left;            
        }
    }
}


int Solution::solve(vector<int> &A, vector<int> &B) {

    Trienode* head = new Trienode;

    for(int x:A)
        Insert(head,x);

    return Max_Xor_Pair(head,B);
}

示例输入

A : [ 15891, 6730, 24371, 15351, 15007, 31102, 24394, 3549, 19630, 12624, 24085, 19955, 18757, 11841, 4967, 7377, 13932, 26309, 16945, 32440, 24627, 11324, 5538, 21539, 16119, 2083, 22930, 16542, 4834, 31116, 4640, 29659, 22705, 9931, 13978, 2307, 31674, 22387, 5022, 28746, 26925, 19073, 6271, 5830, 26778, 15574, 5098, 16513, 23987, 13291, 9162 ]

B : [ 18637, 22356, 24768, 23656, 15575, 4032, 12053, 27351, 1151, 16942 ]

Answer 1

当head是一个全局变量，而你在Solution::solve中没有这一行：

 Trienode* head = new Trienode;

...然后 head 将在第一个测试用例完成后保留其值，因此第二个测试用例不会以空树开始。每个测试用例都会添加个节点到 one 树。当然这意味着，除了第一个测试用例，以 head 为根的树不是预期的树。

要使带有全局变量的版本正常工作，在Solution::solve:

中重置它

head->left = head->right = nullptr;

顺便说一句，您还应该在 TrieNode 构造函数中使用 nullptr（而不是 0）初始化这些成员。这更好地反映了意图。

Answer 2

您也可以采用这种方法：

代码：

struct Node {
    Node* left;
    Node* right;
};

class MaxXorHelper{
  private : Node* root;    
  public :
    MaxXorHelper() {
        root = new Node();
    }

    void addElements(vector<int> &arr) {
        for(int i=0; i<arr.size(); i++) {
            Node* node = root;
            int val = arr[i];
            for(int j=31; j>=0; j--) {
                int bit = (val >> j) & 1;

                if(bit == 0) {
                    if(!node->left) {
                        node->left = new Node();
                    }
                    node = node->left;
                } 
                else {
                    if(!node->right) {
                        node->right = new Node();
                    }
                    node = node->right;
                }
            }
        }
    }

    int findMaxXor(vector<int> &arr) {
        int maxXor = INT_MIN;
        for(int i=0; i<arr.size(); i++) {
            Node* node = root;
            int val2 = 0;
            int val1 = arr[i];
            for(int j=31; j>=0; j--) {
                int bit = (val1 >> j) & 1;

                if(bit == 0) {
                    if(node->right) {
                        val2 |= (1 << j);
                        node = node->right;
                    } else{
                        node = node->left;
                    } 
                }
                else {
                    if(node->left) {
                        node = node->left;
                    } else{
                        val2 |= (1 << j);
                        node = node->right;
                    }
                }
            }
            int curXor = val1 ^ val2;
            maxXor = max(maxXor, curXor);
        }
        return maxXor;
    }
};

int Solution::solve(vector<int> &A, vector<int> &B) {
    MaxXorHelper helper;
    helper.addElements(A);
    return helper.findMaxXor(B);
}

两个数组之间的最大异或 |树

Maximum Xor between Two Arrays | Trie

global-variables

xor

local-variables

trie

代码

示例输入