Xor（滴滴笔试题）

题目描述展开目录

给出一个数组，问最多有多少个不重叠的非空区间，使得每个区间内的数字的 xor 都等于 0。

示例展开目录

输入 1 2 3 0 3 2 1 0
输出 4

思路展开目录

DP，假设数组最后一个数的下标是 i，并且数组存在一个最优划分，使得划分的子数组个数最多，那么 i 有两种情况，第一，i 所在的划分区间异或为 0；第二，i 所在的划分区间，异或不为 0。对于第一种情况 dp [i] = dp [i-1] 的，对于第二种情况，假设 i 的最优划分区间是 [k,i]，0 到 i 的连续异或为 sum，之要求出一个最大的下标 k-1，使得 0 到 k-1 的异或也为 sum 就行了

代码展开目录

import java.util.*;
public class Main {    
    public static int mostXor(int[] arr) {
        int ans = 0;
        int xor = 0;
        int[] dp = new int[arr.length];
        HashMap<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        for(int i = 0;i < arr.length;i++) {
            xor ^= arr[i];
            if(map.containsKey(xor)) {
                int pre = map.get(xor);
                dp[i] = pre == -1 ? 1 : (dp[pre] + 1);
            }
            if(i > 0)
                dp[i] = Math.max(dp[i - 1],dp[i]);
            map.put(xor,i);
            ans = Math.max(ans,dp[i]);
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] test = {1,2,3,0,3,2,1,0};
        System.out.println(mostXor(test));
    }
}