【题目】

给定一个数组，求子数组的最大异或和。

一个数组的异或和为，数组中所有的数异或起来的结果。

【题解】

必须以i结尾的最大异或和的最长数组

暴力解为O(N3)，就是每个数都暴力循环一遍

异或运算的性质：

e1 ^ e2 = e3

e1 = e2 ^ e3;

e2 = e3 ^ e1;

使用前缀树：

将0~i的异或和计算出来，换算成二进制数据

然后将二进制数据组成一颗二叉树

然后怎么找到最大异或和？

就是除了首位希望为0，因为首位为1是负数

然后后面的数尽量走1的这条路，然后那条路就是最大的异或和

主要难点就是使用移位将所位的二进制各个位置上的数提取出来

 【代码实现】

　　

1 #pragma once 2 #include 
     
       3 #include 
      
        4  5 using namespace std; 6  7 class TreeNode 8 { 9 10 public:11     struct Node12     {13         int val;14         vector
       
        nexts;15         Node(int a) :val(a), nexts({ nullptr,nullptr }) {}16     };17 18     void add(int num)19     {20         Node* cur = head;21         for (int i = 31; i >= 0; --i)22         {23             int k = ((num >> i) & 1);//取出每一位数字24             cur->nexts[k] = cur->nexts[k] == nullptr ? new Node(-1) : cur->nexts[k];25             cur = cur->nexts[k];26         }27     }28 29     int maxXor(int num)30     {31         Node* cur = head;32         int s = 0;33         for (int i = 31; i >= 0; --i)34         {35             int k = (num >> i) & 1;//从最高位一位一位取出数据36             int b = i == 31 ? k : (k ^ 1);37             b = cur->nexts[b] != nullptr ? b : (b ^ 1);38             s |= (k^b) << i;39             cur = cur->nexts[b];40         }41         return s;42     }43 public:44     Node* head = new Node(-1);45 };46 47 48 int getMaxXOR(vector
        
         num)49 {50     if (num.size() == 0)51         return 0;52     int xors = 0;53     int res = INT_MIN;54     TreeNode numTree;55     numTree.add(0);56     for (auto a : num)57     {58         xors ^= a;59         res = res > numTree.maxXor(xors) ? res : numTree.maxXor(xors);60         numTree.add(xors);61     }62     return res;        63 }64 65 66 void Test()67 {68     vector
         
          v;69     v = { 1,2,3,4,5 };70     cout << getMaxXOR(v) << endl;71 }