最大异或和 ——2021美团春季校招笔试题-一一网

原题描述： * 给定一个非负整数数列 a，初始长度为 N请在所有长度不超过 M 的连续子数组中，找出子数组异或和的最大值。子数组的异或和即为子数组中所有元素按位异或得到的结果。
注意：子数组可以为空。第一行包含两个整数 N,M 第二行包含 N 个整数，其中第 i 个为 a_i。1≤M≤N≤10⁵, 0≤ a_i≤ 2³¹−1

case:
输入：

3 2

1 2 4

输出：
6

前置知识:

异或，前缀树，双指针算法

Trie
作用高效存储和查找字符串集合
实现
树形结构,以字符为单位将字符串存入树中。如将abcd存入Trie中,首先在根结点root判断其孩子结点是否有a,若无则创建,接着在a结的叶子节点中是否有b,以此类推。使用时一般不会有很多字符类型。
图片[1]-最大异或和 ——2021美团春季校招笔试题-一一网
双指针，滑动窗口算法
用于解决固定大小区间内的最值等内容的求解。

思路:

首先确定异或操作如何Java实现，一般遇到最大和，区间最大和等问题，可以向前缀和靠拢，当然，现在的前缀和对应的是前缀异或和。现在需要确定的是，长度为M的连续子数组中区间异或和的最大值（第一反应需要采用双指针算法）。在求异或和的时候，最大值与普通的加法求最大值不一样，在本题中，使用前缀树的方法求最大异或和。关于限制长度M，可以使用滑动窗口或者双指针算法解决该问题。

暴力思路二重循环，略微优化规定异或对顺序(ai,aj),1<=i<j<=n 时间复杂度O(n^2) 。因为是连续的，所以基本上就是以每个数为起点试一下。
优化：第一重循环枚举a[i]不好优化,优化考虑在a[i]固定的情况下。
如何快速找到a[j],使得a[i]^a[j]最大。
贪心思路: 对于ai,我们从最高位开始向下按位枚举,设当前位值为u,那么我们可以将a1ai-1按当前位与u相等/不等分为两类,每次我们都尽量选取，与u不等的一类,这样最高位最大,可以保证这样求得的值最大.(1000一定大于0xxx,0xxx最大为0111)
实现: 我们可以发现将a1ai分为两大类的思想非常契合Trie数据结构,我们只要在插入aj时。从高位到低位按位插入,那么我们就可以自然的按贪心思路查找。

Trie的两种构造方法
1.树形结构的方式

public class Trie{
	TrieNode root;
    public Trie(){
        this.root = new TrieNode();
    }
    // 插入到前缀树中
    public void insert(String word){
        char ch[] = word.toCharArray();
        TrieNode node = root;
        for(int i=0;i<ch.length;i++){
            int u = ch[i]-'a';
            if(node.next[u]==null){
                node.next[u]=new TrieNode();
            }
            node = node.next[u];
        }
        // 需要对结尾的字符进行标记
        node.end = true;
    }
    
    // 判断字符串是否在
    public boolean search(String word){
        char ch[] = word.toCharArray();
        TrieNode node = root;
        for(int i=0;i<ch.length;i++){
        	int u = ch[i] - 'a';
            if(node.next[u]==null){
                return false;
            }
            node = node.next[u];
        }
        return node.end;
    }
    // 判断是否存在以字符串perfix开头的
    public boolean startsWith(String prefix){
        char ch[] = word.toCharArray();
        TrieNode node = root;
        for(int i=0;i<ch.length;i++){
        	int u = ch[i] - 'a';
            if(node.next[u]==null){
                return false;
            }
            node = node.next[u];
        }
        return true;
    }
}
// 字典树结构，每个节点有26个字母，所以每个节点的长度设计为26个字符
class TrieNode{
    boolean end;
    TrieNode next[];
    public TrieNode(){
    	this.end = false;
        this.next= new TrieNode[26];
    }
}
复制代码

数组实现树结构

class Trie2{

    static int N = 20010;
    static int trie[][] = new int[N][26];
    static int cnt[] = new int[N];
    int idx = 0;

    /**
     * 向集合中插入一个字符串 x；
     * @param ch
     */
    public void insert(char ch[]){
        int len = ch.length;
        int p=0;
        for (int i = 0;i<len;i++){
            int temp = ch[i]-'a';
            if (trie[p][temp]==0){
                // 字典表中该字符未被初始化过
                trie[p][temp] = ++idx;
            }
            // 顺延到子节点上,代表子节点长度
            p = trie[p][temp];
        }
        // 代表以P为结尾的串增加
        cnt[p]++;
    }

    /**
     * 询问一个字符串在集合中出现了多少次。cnt是用来计算出现次数的
     * @param ch
     * @return
     */
    public int query(char ch[]){
        int p=0;
        for (int i =0; i<ch.length; i++){
            int temp = ch[i]-'a';
            if (trie[p][temp]!=0){
                p = trie[p][temp];
            }else{
                return 0;
            }
        }
        return cnt[p];
    }
}

复制代码

基于上述两种方式，我们来计算这种最大异或和问题，其中包含前缀和的实现

import java.util.*;
public class MaxXOR{
    static int N = 100010 * 31;
    static int M = 100010;
    // 01数字，不再是26个字母的串
    static int trie[]=new int[N][2];
    static int cnt[]= new int[N];
    static int SUM[]=new int[N];
    static int idx = 0;
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        SUM[0] = sc.nextInt();
        // 计算前缀异或和
        for(int i=1;i<n;i++){
            int x = sc.nextInt();
            SUM[i] = SUM[i-1]^x;
        }
        int res = 0;
        // 通过前缀树计算局部最大异或和
        insertTire(SUM[0],1);
        for(int i=1;i<n;i++){
            if(i>m){
                insert(SUM[i-m-1],-1);
            }
            res = Math.max(res,query(SUM(i)));
           	insert(SUM[i],1);
        }
    }
    
    // 在Trie中插入或删除数据
    public static void insertTrie(int x,int value){
        int p=0;
        for(int i=30;i>=0;i--){
            int u = x>>i&1;
            if(trie[p][u]==0){
                trie[p][u]=++idx;
            }
            p = trie[p][u];
            cnt[p]+=value;
        }
    }
    // 查询当前前缀和的最大值
    public static int query(int x){
        int result = 0,p=0;
        for(int i=30;i>=0;i--){
            int u = x>>i&1;
            // 这里是为了找到和当前位不一致的数，如果当前位是0，则优先找当前位为1的数
            if(cnt[trie[p][1-u]]!=0){
                p =  trie[p][1-u];
                result = result*2+1;//往右子树走，即找1的地方
            }else{
                p = trie[p][u];
                result = result*2;
            }
            
        }
        return result;
    }
}
复制代码