一,题目描述

给定一个数组，求子数组的最大异或和。
一个数组的异或和为，数组中所有的数异或起来的结果

二,一般算法分析

2.1 普通解法

public static void getMax1(int[] arr)
{
      //设置最大值,初始值为无穷小
        int max=Integer.MIN_VALUE;
        //以i为结尾
        for(int i=0;i<arr.length;i++)
        {   
            //start到i的最大异或和
            for(int start=0;start<=i;i++)
            {
                 int res=0;
                 //遍历start---i
                 for(int k=start;k<=i;i++)
                 {
                     res^=arr[k];
                 }
                 max=Math.max(max, res);
            }
        }
        return max;
}

分析

三层循环,时间复杂度为O(n^3)

2.2 优化算法

图片.png

start--i的异或结果为0--i的异或结果^0---start的异或结果

public static int getMaxE2(int[] arr)
    {
        int max=Integer.MIN_VALUE;
        int[] dp=new int[arr.length];
        int eor=0;
        for(int i=0;i<arr.length;i++)
        {
            eor^=arr[i];
            max=Math.max(max, eor);
            //整个遍历得到了以i为结尾的最大异或和
            for(int start=1;start<=i;start++)
            {   
                //0---i的异或和^0---start的异或和==start-i的异或和
                int curEor=eor^dp[start-1];
                max=Math.max(max, curEor);
            }
            //dp[i]存放着0到i的异或和
            dp[i]=eor;
        }
        return max;
    }

分析

两层循环,时间复杂度为O(n^2),空间换时间

三,前缀树介绍

3.1介绍

前缀树也叫字典树,是处理字符串的常见的数据结构

图片.png

3.1.1性质

(1)根节点没有字符路径,除根节点外,每一个结点都被一个字符路径找到.
(2)从根节点到某一节点,除路径上经过的字符连接起来,为扫过的对应字符串
(3)每个节点下上的所有的字符路径上的字符都不同

3.2实现代码

四,由前缀树实现此题目

4.1 实现之前的准备

public class Test {
    public static void main(String[] args) {
        int num=3;
        for(int i=31;i>=0;i--)
        {
            int path=(num>>i)&1;
            System.out.print(path+" ");
        }
    }
}

运行结果: 图片.png 当num=32时, 图片.png

4.2定义结点

public static class Node{
        public Node[] nexts=new Node[2];
}

路径有两条0和1,如下图所示 图片.png

4.2定义整个结构NumTrie

public Node head=new Node();

4.2.1添加add()方法

public void add(int num)
        {
            Node cur=head;
            //int类型一共32位
            for(int move=31;move>=0;move--)
            {
                int path=((num>>move)&1);//当前位数
                cur.nexts[path]=cur.nexts[path]==null?new Node():cur.nexts[path];
                cur=cur.nexts[path];
            }
        }

int path=((num>>move)&1);将int的32位的每一位都分离出来

cur.nexts[path]=cur.nexts[path]==null?new Node():cur.nexts[path];如果下一位的结点已经存在就不动,否则添加一个结点 图片.png

4.2.2添加maxXor()方法

public int maxXor(int num)
        {
            Node cur=head;
            int res=0;
            for(int move=31;move>=0;move--)
            {
                int path=(num>>move)&1;
                int best=move==31?path:(path^1);
                best=cur.nexts[best]!=null?best:(best^1);
                res |=(path^best)<<move;
                cur=cur.nexts[best];
            }
            return res;
        }

传入一个值,遍历每一位,int path=(num>>move)&1;得到当前的位数
如果当前的位数为31,即当前为符号位,则选择本身(符号位如果是1,选择1异或变为正,0也是这样),其他位置尽量为1,则path^1;
best=cur.nexts[best]!=null?best:(best^1);
如果期待的位置不为空,则走,如果为空,只能走异或的情况
res |=(path^best)<<move;将得到的值移动到对应的位数

4.3 核心方法

    public static int maxXorSubarray(int[] arr)
    {
        if(arr==null||arr.length==0)
        {
            return 0;
        }
        int max=Integer.MIN_VALUE;
        int eor=0;
        NumTrie numTrie=new NumTrie();
        numTrie.add(0);
        for (int i = 0; i < arr.length; i++) {
            eor ^= arr[i];//0-i的异或和
            //0-i的
            max = Math.max(max, numTrie.maxXor(eor));
            numTrie.add(eor);
        }
        return max;
    }