mzoe666888

V1

2022/04/13阅读:24主题:兰青

内卷大厂系列《异或和问题二连击》

大厂高频算法面试题:《异或和问题系列》,您将学到异或运算的特性,如何利用异或运算这种魔性操作来快速求解,同时利用前缀树的路径异或解法,很不错。

一、子数组的最大异或和

数组异或和的定义:把数组中所有的数异或起来得到的值。

给定一个整型数组 arr,其中可能有正、有负、有零,求其中子数组的最大异或和。

1、分析

异或运算比较模型,有如下规律:

  • 异或运算满足交换律结合律
  • 0 ^ N = N
  • 0 ^ 0 = 0

方法一:暴力解,枚举所有子数组,每个子数组中求出异或值,选出最大异或和,时间复杂度O(N³)

方法二:增加预处理数组异或和,假设arr[i...j]这个子数组的异或和用 eor[i...j] 来表示。也就是说,eor[0...j] = eor[0...i-1] ^ eor[i...j],则可以推出 eor[i...j] = eor[0...j] ^ eor[0...i-1]时间复杂度O(N²)

方法三利用前缀树实现最优解,时间复杂度O(N)

假设以 j 位置结尾时我们是这么做的:

  • eor[0...j] = eor[j] ^ 0
  • eor[1...j] = eor[j] ^ eor[0]
  • ...
  • eor[i...j] = eor[j] ^ eor[i-1]
  • ...
  • eor[j...j] = eor[j] ^ eor[j-1]

我们要的是 max(以 j 结尾时的 max),即 max = (eor[0..j],eor[1..j],…,eor[j..j] 中最大的一项。也就是说,max = eor[j] ^(从 0,eor[0],eor[1],…,eor[j-1] 中挑一个出来)。

0,eor[0],eor[1],…,eor[j-1]构建成前缀树结构,每项都用二进制表示,eor[j]和前缀树上的哪个路径异或最大就是以 j 结尾的子数组异或和最大值,假如eor[j] = 0110,策略就是尽量让高位异或后结果为1,不就大了么,0 ^ 1 = 11 ^ 1 = 0,本质就是将挑选的过程加速。

如果把二进制位扩到32位,需要考虑符号位怎么异或得到最大,所以 eor[j] 的最高位如果是 0,希望能走 0 的路,因为这样异或之后符号位是 0,为正数;eor[j] 的最高位如果是 1,希望走 1 的路,因为这样异或之后符号位是 0,为正数。如果不能选择,只能被迫走唯一的路。

2、实现

2.1、方法一

public static int maxXorSubarray(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int max = Integer.MIN_VALUE;
    for (int i = 0; i < arr.length; i++) { // 枚举全部子数组
        for (int j = 0; j <= i; j++) {
            int ans = 0;
            for (int k = j; k <= i; k++) { // 子数组异或和
                ans ^= arr[k];
            }
            max = Math.max(max, ans);
        }
    }
    return max;
}

2.2、方法二

public static int maxXorSubarray(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    // 准备一个前缀异或和数组eor
    // eor[i] = arr[0...i]的异或结果
    int[] eor = new int[arr.length];
    eor[0] = arr[0];
    // 生成eor数组,eor[i]代表arr[0...i]的异或和
    for (int i = 1; i < arr.length; i++) {
        eor[i] = eor[i - 1] ^ arr[i];
    }
    int max = Integer.MIN_VALUE;
    for (int j = 0; j < arr.length; j++) { // 枚举全部子数组
        for (int i = 0; i <= j; i++) { // 依次尝试arr[0..j]、arr[1..j]、arr[i..j]、arr[j..j]
            max = Math.max(max, i == 0 ? eor[j] : eor[j] ^ eor[i - 1]);
        }
    }
    return max;
}

2.3、方法三

// 前缀树的节点类型,每个节点向下只可能有走向0或1的路
// node.nexts[0] == null 0方向没路
// node.nexts[0] != null 0方向有路
public static class Node {
    public Node[] nexts = new Node[2]; // 只有0或1两种路
}

// 基于本题,定制前缀树的实现
public static class NumTrie {
    // 头节点
    public Node head = new Node();

    // 把某个数字newNum加入到这棵前缀树里
    // num是一个32位的整数,所以加入的过程一共走32步
    public void add(int newNum) {
        Node cur = head;
        for (int move = 31; move >= 0; move--) {
            // 从高位到低位,取出每一位的状态,如果当前状态是0,
            // path(int) = 0
            // ,如果当前状态是1
            // path(int) = 1
            int path = ((newNum >> move) & 1);
            // 无路新建、有路复用
            cur.nexts[path] = cur.nexts[path] == null ? new Node() : cur.nexts[path];
            cur = cur.nexts[path];
        }
    }

    // 该结构之前收集了一票数字,并且建好了前缀树
    // sum,和 谁 ^ 最大的结果(把结果返回)
    public int maxXor(int sum) {
        Node cur = head;
        int res = 0;
        for (int move = 31; move >= 0; move--) {
            int path = (sum >> move) & 1// 不是0就是1
            // 期待的路,符号位不变,其余位走相反才能保证异或最大
            int best = move == 31 ? path : (path ^ 1);
            // 实际走的路
            best = cur.nexts[best] != null ? best : (best ^ 1);
            // (path ^ best) 当前位异或完的结果
            res |= (path ^ best) << move;
            cur = cur.nexts[best];
        }
        return res;
    }
}

public static int maxXorSubarray(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int max = Integer.MIN_VALUE;
    int eor = 0// 0..i 异或和
    // 前缀树 -> numTrie
    NumTrie numTrie = new NumTrie();
    numTrie.add(0); // 一个数也没有的时候,异或和是0
    for (int i = 0; i < arr.length; i++) {
        eor ^= arr[i]; // eor -> 0..i异或和
        // X, 0~0 , 0~1, .., 0~i-1
        max = Math.max(max, numTrie.maxXor(eor));
        numTrie.add(eor);
    }
    return max;
}

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

给定一个整型数组 arr,其中可能有正、有负、有零。你可以随意把整个数组切成若干个子数组,求异或和为 0 的子数组最多能有多少个?

示例

arr = {3,2,1,9,0,7,0,2,1,3}

把数组分割成{3,2,1}、{9}、{0}、{7}、{0}、{2,1,3}是最优分割,因为其中{3,2,1}、{0}、{0}、{2,1,3}

这四个子数组的异或和为 0,并且是所有的分割方案中,能切出最多异或和为 0 的子数组的方 案,返回 4。

1、分析

dp[i]的含义是如果在arr[0...i]上做分割,异或和为 0 的子数组最多能有多少个,那么 dp[N-1]的值就是:如果在 arr[0...N-1]上做分割,异或和为 0 的子数组最多能有多少个,也就是最终答案。

以子数组结尾分析可能性:

  • 最优分割的最后一个子数组,异或和不等于 0,则dp[i] = dp[i-1]
  • 最优分割的最后一个子数组,异或和等于 0,假设 arr[k...i] 就是最优分割的最后一个子数组,并且异或和等于 0,则dp[i] = dp[k-1] + 1

2、实现

public static int mostEOR(int[] arr) {
    if (arr == null || arr.length == 0) {
        return 0;
    }
    int N = arr.length;
    // dp[i] -> arr[0...i]在最优划分的情况下,异或和为0最多的部分是多少个
    int[] dp = new int[N]; // dp[i] = 0
    // key:某个前缀异或和,value:这个前缀异或和出现的最晚的结尾位置
    HashMap<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int sum = 0;
    for (int i = 0; i < arr.length; i++) {
        sum ^= arr[i]; // sum -> [0...i]所有数的异或和
        // 假设sum上次出现的结尾是k,0~k的异或和是sum,0~i的异或和也是sum,k+1~i是异或和等于0的
        // 前缀异或和出现的最晚的结尾位置,k+1是离i最近的
        if (map.containsKey(sum)) { // 上一次,这个异或和出现的位置
            // pre -> pre + 1 -> 1,最优划分,最后一个部分的开始位置,pre+1~i最后一个部分
            int pre = map.get(sum); // sum 0...pre  pre+1...i
            dp[i] = pre == -1 ? 1 : (dp[pre] + 1);
        }
        if (i > 0) {
            dp[i] = Math.max(dp[i - 1], dp[i]);
        }
        map.put(sum, i);
    }
    return dp[dp.length - 1];
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1