MENU

Xor(滴滴笔试题)

August 15, 2018 • Read: 3206 • 算法阅读设置

题目描述

给出一个数组,问最多有多少个不重叠的非空区间,使得每个区间内的数字的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));
    }
}
Last Modified: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment