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]选 选 0nums[i] XOR nums[i] 0因此每个元素要么贡献 0要么贡献 nums[i]。这意味着 任意子集的 XOR 值都可以被构造出来。于是问题转化为经典的 最大子集 XOR 问题用线性基XOR Basis解决时间复杂度 O(n \cdot 31)。---Java 代码javaclass 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]- 插入 1basis[0] 1- 插入 2basis[1] 2- 插入 33 XOR 2 11 XOR 1 0线性相关不插入- 贪心构造ans 0 → ans ^ 2 2 0ans 2ans ^ 1 3 2ans 3- 输出3 ✓示例 2 nums [5, 2]- 插入 5basis[2] 5- 插入 2basis[1] 2- 贪心构造ans 0 → ans ^ 5 5 0ans 5ans ^ 2 7 5ans 7- 输出7 ✓