企业官网建设流程全解析

LeetCode 3681. 子序列最大 XOR 值 — Python3 实现

核心思路

这道题的关键在于一个巧妙的转化：

题目要求选择两个允许重叠的子序列，设它们的 XOR 分别为 `X` 和 `Y`，求 `X XOR Y` 的最大值。

对于每个元素 `nums[i]`，它在 `X XOR Y` 中的贡献取决于它被两个子序列选中的情况：

子序列1 子序列2 对 `X XOR Y` 的贡献
不选 不选 0
选 不选 `nums[i]`
不选 选 `nums[i]`
选 选 0（`nums[i] XOR nums[i] = 0`）

因此，每个元素要么贡献 `0`，要么贡献 `nums[i]`。这意味着 任意子集的 XOR 值都可以被构造出来。

于是问题转化为经典的 最大子集 XOR 问题，用线性基（XOR Basis）解决，时间复杂度 O(n \cdot 31)。

---

Python3 代码

```python
class Solution:
def maxXorSubsequences(self, nums: list[int]) -> int:
# 线性基，basis[i] 表示最高位为第 i 位的基向量
# nums[i] <= 1e9 < 2^30，所以 31 位足够
basis = [0] * 31

for x in nums:
cur = x
# 从高到低尝试消元
for bit in range(30, -1, -1):
if (cur >> bit) & 1 == 0:
continue # 当前位不是最高位，跳过
if basis[bit] != 0:
# 该位已有基向量，用当前基向量消去这一位
cur ^= basis[bit]
else:
# 该位没有基向量，插入新的基向量
basis[bit] = cur
break
# 如果 cur 最终变为 0，说明该数线性相关，无需插入

# 贪心构造最大 XOR 值
ans = 0
for bit in range(30, -1, -1):
if (ans ^ basis[bit]) > ans:
ans ^= basis[bit]
return ans
```

---

复杂度分析

项目 复杂度 说明
时间 O(n \cdot 31) 每个数最多处理 31 位
空间 O(31) 固定大小的线性基数组

---

示例验证

示例 1： `nums = [1, 2, 3]`
- 插入 1：`basis[0] = 1`
- 插入 2：`basis[1] = 2`
- 插入 3：`3 XOR 2 = 1`，`1 XOR 1 = 0`，线性相关，不插入
- 贪心构造：`ans = 0 → ans ^ 2 = 2 > 0`，`ans = 2`；`ans ^ 1 = 3 > 2`，`ans = 3`
- 输出：3 ✓

示例 2： `nums = [5, 2]`
- 插入 5：`basis[2] = 5`
- 插入 2：`basis[1] = 2`
- 贪心构造：`ans = 0 → ans ^ 5 = 5 > 0`，`ans = 5`；`ans ^ 2 = 7 > 5`，`ans = 7`
- 输出：7 ✓