乐趣区

关于程序员:子数组最大异或和

子数组最大异或和

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

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

【举例】

arr =【3】

数组中只有 1 个数,所以只有一个子数组,就是这个数组自身,最大异或和为 3

arr =【3,-28,-29,2】

子数组有很多,然而【-28,-29】这个子数组的异或和为 7,是所有子数组中最大的。

剖析:

异或和没有枯燥性。两个小的数的异或和可能比两个大数的异或和大。

解法一:暴力算法

对每一个以 i 为开始和以 j 为结尾的子数组,进行异或和计算,获取全局最大的异或和,就是答案。

工夫复杂度:$O(N^3)$

工夫复杂度:O(1)

import sys

def max_xor(arr):
    if not arr: return 0
    res = -sys.maxsize
    for i in range(len(arr)):
        for j in range(i, len(arr)):
             # 窗口:arr[i,j+1], 计算窗口内数据的异或和
            xor = 0
            for k in range(i, j + 1):
                xor ^= arr[k]
            res = max(res, xor)
    return res

解法二:前缀异或和

前缀和的性质:

  1. 归零率:A ^ A = 0
  2. 恒等率:A ^ 0 = A

根据上述两个性质能够推导出:

$C = A \oplus B \Longrightarrow \\ C \oplus A = A \oplus B \oplus A \Longrightarrow \\ C \oplus A = B \oplus 0 \Longrightarrow \\ A \oplus C = B$

依据前缀异或和能够计算出任意子数组的异或和。

工夫复杂度:$O(N^2)$

工夫复杂度:O(N)

def max_xor1(arr):
    if not arr: return 0

      # 前缀异或和
    prefix_sum = [arr[0]]
    for i in range(1, len(arr)):
        prefix_sum.append(arr[i] ^ prefix_sum[-1])

    res = -sys.maxsize
    for i in range(len(arr)):
        s = 0 if i == 0 else prefix_sum[i - 1]
        for j in range(i, len(arr)):
            # 窗口:arr[i,j+1]
            xor = prefix_sum[j] ^ s
            res = max(res, xor)
    return res

解法三:前缀树 + 贪婪

由解法二可知:$C = A \oplus B \Longrightarrow B = C \oplus A$

即:$arr[2…5] = arr[0…5] \oplus arr[0…2]$

  • arr[0..5] 与 0 联合示意:arr[0…5] 子数组的异或和
  • arr[0..5] 与 arr[0] 联合示意:arr[1…5] 子数组的异或和
  • arr[0..5] 与 arr[0…1] 联合示意:arr[2…5] 子数组的异或和
  • arr[0..5] 与 arr[0…2] 联合示意:arr[3…5] 子数组的异或和

与谁联合异或和大,应答的子数组就是要找的子数组。

目前不晓得 arr[0…5] 抉择哪个?在解法二中是枚举尝试,咱们当初想通过前缀树构建一种规定(贪婪策略)来减速寻找最佳联合子数组。

<font color=red> 贪婪策略:在 arr[0..j] 抉择 arr[0..i] 联合过程中,优先投合高位变成 1(高位为 1,对应值更大)。</font>

如下图:arr[0…j] 的异或和的二进制模式【0,1,1,0】,从高位 A 逐个匹配。因为 0 ^ 1 = 1,所以抉择 1 的分支(A –> C),在 F 地位,尽管最期待走的门路是 0,然而没有 0 门路所以只能走 1 门路。整条门路【1,0,1,1】就是 arr[0…j](【0,1,1,0】)最佳联合的子数组对应的异或和。【0,1,1,0】^【1,0,1,1】=【1,0,1,1】此时【1,0,1,1】就是的返回后果 arr[0..j]。

前缀树

# 将所有的前缀异或和,退出到 NumTrie,并依照前缀树组织
class NumTrie:
    def __init__(self):
        self.root = Node()

    def add(self, num):
        cur = self.root
        # move 向右位移多少位
        for move in range(31, -1, -1):
            # 获取对应位上的数字(0 或者 1)path = (num >> move) & 1
            cur.nexts[path] = cur.nexts[path] if cur.nexts[path] else Node()
            cur = cur.nexts[path]

    # num 最心愿遇到的门路,后果返回:最大的异或和
    # 工夫复杂度:O(32)
    def max_xor(self, num):
        cur = self.root
        # 返回值 (num ^ 最优抉择)
        res = 0
        for move in range(31, -1, -1):
            # 获取对应位上的数字(0 或者 1)path = (num >> move) & 1
            # sum 该位的状态,最期待的门路(如果 sum 位是 0,期待 path =1,否则 path = 0)# 留神:如果是符号位是 1(正数),期待 path = 1,异或后是 0(负数)#      如果是符号位是 0(负数),期待 path = 0,异或后是 0(负数)best = path if move == 31 else path ^ 1
            # 最期待走的门路  --> 理论门路
            best = best if cur.nexts[best] else best ^ 1
            # 留神:本代码是 python,左移 31 位不会变为正数,python 会将 int 转为 long 变为更大的数
            # 如果是 java:res |= (path ^ best) << move
            tmp = 1
            if move == 31 and num < 0:
                tmp = -1
            res |= tmp * (path ^ best) << move
            cur = cur.nexts[best]

        return res

工夫复杂度:$O(N)$

工夫复杂度:O(N)

def max_xor2(arr):
    if not arr: return 0
    res = -sys.maxsize

    trie = NumTrie()
    trie.add(0)
    # 一个数没有时,异或和为 0
    xor = 0
    for i in range(len(arr)):
        # xor 等于 0 ~ i 异或和
        xor ^= arr[i]
        # trie 装着所有:一个数也没有(0),0~1,0~2,0~3...0~i-1 的异或和
        res = max(res, trie.max_xor(xor))
        trie.add(xor)
    return res

对数器

import random

def check():
    max_value = 10
    for i in range(100):
        arr = [int(random.random() * max_value) - int(random.random() * max_value) for _ in
               range(int(random.random() * max_value))]
        res = max_xor(arr)
        res1 = max_xor1(arr)
        res2 = max_xor2(arr)
        if res != res1 or res != res2:
            print(i, "ERROR", arr, "res=", res, "res1=", res1, "res2=", res2)
    print("NICE")

本文由 mdnice 多平台公布

退出移动版