子数组异或和为0的最多划分

链接

给定一个整型数组arr,其中可能有正有负有零。你可以随意把整个数组切成若干个不相容的子数组,求异或和为0的子数组最多可能有多少个?整数异或和定义:把数组中所有的数异或起来得到的值。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    private static int solve(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }

        int n = arr.length;
        Map<Integer, Integer> helper = new HashMap<>();
        int[] dp = new int[n];
        helper.put(0, -1);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            sum ^= arr[i];
            Integer index = helper.get(sum);
            dp[i] = i > 0 ? dp[i - 1] : 0;
            if (index != null) {
                dp[i] = Math.max(dp[i], 1 + (index >= 0 ? dp[index] : 0));
            }
            helper.put(sum, i);
        }

        return dp[n - 1];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] arr = new int[n];
            for (int i = 0; i < n; ++i) {
                arr[i] = in.nextInt();
            }
            System.out.println(solve(arr));
        }
    }
}
上一篇:剑指Offer | day11_双指针


下一篇:leetcode---二叉树的分层遍历(逐层的返回其按照层序遍历得到的节点值,从左到右访问所有节点)