Kimi LeetCode 3630. 划分数组得到最大异或运算和与运算之和 Python3实现

根据搜索结果中的信息我来为您提供 LeetCode 3630. 划分数组得到最大异或运算和与运算之和 的 Python3 实现。题目分析题目要求将数组 nums 划分为三个子序列 A、B、C最大化- XOR(A) AND(B) XOR(C)关键约束1 nums.length 19这意味着可以使用状态压缩枚举。核心思路1. 枚举子序列 B使用位掩码因为 AND 运算比较特殊2. 剩余元素需要分成 A 和 C最大化 XOR(A) XOR(C)3. 对于两个异或子序列的最大和问题使用线性基优化关键数学推导对于剩余元素集合 S设 s XOR(S)我们要将 S 分成 A 和 C- XOR(A) XOR(C) 的最大值有一个重要结论设 x XOR(A)则 XOR(C) s ^ x所以XOR(A) XOR(C) x (s ^ x) s 2 * (x ~s)这意味着我们需要在 S 中找到一个子集其异或值 x 在 ~s 的位上尽可能大。这可以通过线性基来解决。Python3 实现pythonfrom typing import Listfrom functools import reducefrom operator import or_class XorBasis:异或线性基def __init__(self, W: int 31):self.W Wself.basis [0] * (W 1)def insert(self, x: int) - None:将 x 插入线性基for k in range(self.W, -1, -1):if not ((x k) 1):continueif self.basis[k] 0:self.basis[k] xreturnx ^ self.basis[k]def get_max(self) - int:获取最大异或值res 0for k in range(self.W, -1, -1):if (res ^ self.basis[k]) res:res ^ self.basis[k]return resclass Solution:def maximizeXorAndXor(self, nums: List[int]) - int:n len(nums)# 预处理所有子集的异或值和与值# xor_mask[mask] 子集 mask 的异或值# and_mask[mask] 子集 mask 的与值xor_mask [0] * (1 n)and_mask [0] * (1 n)for mask in range(1, 1 n):lb mask -mask # 最低位的1i (lb.bit_length() - 1) # 对应的元素下标prev mask ^ lbxor_mask[mask] xor_mask[prev] ^ nums[i]if prev 0:and_mask[mask] nums[i]else:and_mask[mask] and_mask[prev] nums[i]# 计算所有数的最高位数OR_all reduce(or_, nums, 0)bitlen OR_all.bit_length()full_bits_mask (1 bitlen) - 1 if bitlen 0 else 0full (1 n) - 1ans 0# 枚举 B 子集for B in range(1 n):R full ^ B # 剩余元素分配给 A 和 C# B 的与值and_B and_mask[B]# 剩余元素的异或值XR xor_mask[R]# 可翻转的位XR 为 0 的位在这些位上我们可以通过分组让两边都为1Z full_bits_mask ^ XR# 构建线性基对剩余元素的每个数只保留可翻转位basis XorBasis(bitlen)for i in range(n):if (R i) 1: # 如果元素 i 在剩余集合中v nums[i] Z # 只保留可翻转位if v:basis.insert(v)# 最大额外增益M basis.get_max()# 计算当前答案XR 2*M AND(B)# XR 是 A 和 C 异或和的基础值# 2*M 是通过翻转带来的额外增益current XR 2 * M and_Bans max(ans, current)return ans代码说明1. 预处理使用动态规划计算所有子集的异或值和与值避免重复计算2. 枚举 B遍历所有可能的 B 子集2^n 种3. 线性基优化对于每个 B剩余元素需要分成 A 和 C- 计算 XR XOR(剩余元素)- 确定可翻转位 Z ~XR在 full_bits_mask 范围内- 对剩余元素只保留可翻转位构建线性基- 通过线性基求最大可翻转值 M4. 答案计算XR 2*M AND(B)复杂度分析- 时间复杂度O(2^n * n * log(max(nums)))- 枚举 B 需要 2^n 次- 每次构建线性基需要 O(n * log(max(nums)))- 空间复杂度O(2^n log(max(nums)))- 预处理数组需要 O(2^n)- 线性基需要 O(log(max(nums)))示例验证- 示例 1nums [2,3]- B {2}, A {3}, C {}- AND(B) 2, XOR(A) 3, XOR(C) 0- 结果3 2 0 5 ✓- 示例 2nums [1,3,2]- B {2}, A {1}, C {3}- AND(B) 2, XOR(A) 1, XOR(C) 3- 结果1 2 3 6 ✓- 示例 3nums [2,3,6,7]- B {2,3}, A {7}, C {6}- AND(B) 2, XOR(A) 7, XOR(C) 6- 结果7 2 6 15 ✓