[LeetCode] 每日一题 3287. 求出数组中最大序列值
题目链接
题目描述
给你一个整数数组 nums
和一个 正 整数 k
。
定义长度为 2 * x
的序列 seq
的 值 为:
(seq[0] OR seq[1] OR ... OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR ... OR seq[2 * x - 1])
.
请你求出 nums
中所有长度为 2 * k
的子序列的最大值 。
子序列 是可以通过从另一个数组删除或不删除某些元素,但不更改其余元素的顺序得到的数组。
示例输入
示例 1
输入:nums = [2,6,7], k = 1
输出:5
解释:
子序列 [2, 7] 的值最大,为 2 XOR 7 = 5 。
示例 2
输入:nums = [4,2,5,6,7], k = 2
输出:2
解释:
子序列 [4, 5, 6, 7] 的值最大,为 (4 OR 5) XOR (6 OR 7) = 2 。
提示
2 <= nums.length <= 400
1 <= nums[i] < 2^7
1 <= k <= nums.length / 2
解题思路
本题的核心思路是通过分割数组,并对每个分割位置计算两个部分的 OR 值,然后通过 XOR 计算得到最大的值
分割思想:我们可以将
nums
数组分割成两部分,分别计算这两部分的 OR 值,然后对这两个部分的 OR 结果进行 XOR 计算。具体来说,前k
个元素的 OR 与后k
个元素的 OR 计算 XOR0-1 背包转化:可以通过动态规划(DP)来计算每一部分的 OR 值。我们将问题转化为一个二维的 0-1 背包问题,维度分别为:
选取的元素个数
当前的 OR 值
我们通过动态规划计算出所有可能的 OR 值,并将前缀部分和后缀部分的 OR 值进行组合,计算它们的 XOR,最终得到最大值
优化空间:为了节省空间,我们只需要保存当前和前一个状态,而无需保存所有状态。利用这种优化,可以有效降低空间复杂度
代码实现
class Solution {
public int maxValue(int[] nums, int k) {
// OR的最大值
final int MAX_OR_VALUE = 1 << 7;
int n = nums.length;
// 后缀部分的 OR 结果
boolean[][] suffixOR = new boolean[n - k + 1][MAX_OR_VALUE];
boolean[][] dp = new boolean[k + 1][MAX_OR_VALUE];
dp[0][0] = true;
// 计算后缀的 OR 值
for (int i = n - 1; i >= k; i--) {
int currentValue = nums[i];
// 循环更新 dp 数组
for (int j = Math.min(k - 1, n - 1 - i); j >= 0; j--) {
for (int x = 0; x < MAX_OR_VALUE; x++) {
if (dp[j][x]) {
dp[j + 1][x | currentValue] = true;
}
}
}
// 将当前的 dp[k] 结果保存到后缀 OR 数组
if (i <= n - k) {
suffixOR[i] = dp[k].clone();
}
}
// 存储最大 XOR 值
int maxXor = 0;
dp = new boolean[k + 1][MAX_OR_VALUE];
dp[0][0] = true;
// 计算前缀的 OR 值并与后缀的结果进行组合计算 XOR
for (int i = 0; i < n - k; i++) {
int currentValue = nums[i];
for (int j = Math.min(k - 1, i); j >= 0; j--) {
for (int x = 0; x < MAX_OR_VALUE; x++) {
if (dp[j][x]) {
dp[j + 1][x | currentValue] = true;
}
}
}
if (i < k - 1) {
continue;
}
for (int x = 0; x < MAX_OR_VALUE; x++) {
if (dp[k][x]) {
// 与后缀的 OR 值进行 XOR 运算
for (int y = 0; y < MAX_OR_VALUE; y++) {
if (suffixOR[i + 1][y]) {
maxXor = Math.max(maxXor, x ^ y);
}
}
}
}
// 如果已经得到了理论上的最大值,直接返回
if (maxXor == MAX_OR_VALUE - 1) {
return maxXor;
}
}
return maxXor;
}
}
复杂度分析
时间复杂度:O(nkU + nU^2),其中
n
是nums
的长度,U
是nums
所有元素的 OR 值的上界,本题至多为 2^7 - 1。动态规划的部分是 O(nkU),计算 XOR 最大值是 O(nU^2) 的空间复杂度:O(nU),需要存储动态规划表格和后缀 OR 值
总结
本题通过动态规划和 0-1 背包转化的思想,求解了最大 XOR 值。通过合理的优化和思路的转换,减少了空间复杂度并使得算法更加高效。今天题目较为复杂,一开始没想到思路,最后参考了大佬 灵茶山艾府 的解法
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。