Kimi LeetCode 3681. 子序列最大 XOR 值 Java实现
LeetCode 3681. 子序列最大 XOR 值 — Java 实现
核心思路
这道题的关键在于一个巧妙的转化：
题目要求选择两个允许重叠的子序列，设它们的 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)。
---
Java 代码
```java
class Solution {
public int maxXorSubsequences(int[] nums) {
// 线性基，basis[i] 表示最高位为第 i 位的基向量
// nums[i] <= 1e9 < 2^30，所以 31 位足够
int[] basis = new int[31];
for (int x : nums) {
int cur = x;
// 从高到低尝试消元
for (int bit = 30; bit >= 0; bit--) {
if ((cur >> bit & 1) == 0) {
continue; // 当前位不是最高位，跳过
}
if (basis[bit] != 0) {
// 该位已有基向量，用当前基向量消去这一位
cur ^= basis[bit];
} else {
// 该位没有基向量，插入新的基向量
basis[bit] = cur;
break;
}
}
// 如果 cur 最终变为 0，说明该数线性相关，无需插入
}
// 贪心构造最大 XOR 值
int ans = 0;
for (int bit = 30; bit >= 0; bit--) {
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 ✓