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));
    }
}