每个查询的最大异或-php教程-PHP中文网

每个查询的最大异或

Mary-Kate Olsen

发布： 2024-11-10 17:41:02

原创

259 人浏览过

Maximum XOR for Each Query

1829。每个查询的最大异或

难度：中等

主题：数组、位操作、前缀和

给你一个排序 n 个非负整数数组nums 和一个整数maximumBit。您想要执行以下查询 n 次:

找到一个非负整数 k maximumBit 使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 最大化。 k 是第 i^个查询的答案。
从当前数组 nums 中删除 last 元素。

返回数组答案，其中answer[i]是第i^第查询的答案。

示例1：

输入： nums = [0,1,1,3]，maximumBit = 2
输出： [0,3,2,3]
说明：问题解答如下：
- 1^stst 查询：nums = [0,1,1,3], k = 0，因为 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3。
- 2^nd 查询：nums = [0,1,1], k = 3 因为 0 XOR 1 XOR 1 XOR 3 = 3.
- 3^rd 查询：nums = [0,1], k = 2 因为 0 XOR 1 XOR 2 = 3.
- 4^第查询：nums = [0], k = 3，因为 0 XOR 3 = 3。

示例2：

输入： nums = [2,3,4,7]，maximumBit = 3
输出： [5,2,6,5]
说明：问题解答如下：
- 1^stst 查询：nums = [2,3,4,7], k = 5，因为 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。
- 2^nd 查询：nums = [2,3,4], k = 2 因为 2 XOR 3 XOR 4 XOR 2 = 7.
- 3^rd 查询：nums = [2,3], k = 6 因为 2 XOR 3 XOR 6 = 7.
- 4^第查询：nums = [2], k = 5，因为 2 XOR 5 = 7。

示例 3：

输入： nums = [0,1,2,2,5,7]，maximumBit = 3
输出： [4,3,6,4,6,7]

约束：

nums.length == n
1 5
1
0 最大位
nums 按升序顺序排序。

提示：

请注意，最大可能的 XOR 结果始终为 2^{(maximumBit) - 1}
因此前缀的答案是该前缀与 2^{(maximumBit)-1} 的异或

解决方案：

我们需要有效地计算数组中元素的异或，并使用值 k 最大化结果，使得 k 小于 2^maximumBit。解决这个问题的方法如下：

观察和方法

最大化异或:
我们可以与任何前缀和进行异或运算的最大位数是（2^{text{maximumBit}} - 1）。这是因为与多个全 1（即二进制的 111...1）进行异或总是会最大化结果。
前缀异或计算:
我们可以为整个数组维护一个累积的 XOR，而不是为每个查询重新计算 XOR。由于 XOR 具有 A XOR B XOR B = A 的属性，因此可以通过从累积 XOR 中异或出该元素来从数组中删除最后一个元素。
算法:
- 首先计算 nums 中所有元素的异或。我们称之为当前异或。
- 对于每个查询（从最后一个到第一个）：
  - 通过将 currentXOR 与 maxNum 进行异或计算，其中 maxNum = 2^maximumBit - 1。
  - 将 k 追加到结果列表中。
  - 通过对 currentXOR 进行异或来从 nums 中删除最后一个元素。
- 结果列表将以相反的顺序包含答案，因此最后将其颠倒过来。

让我们用 PHP 实现这个解决方案：1829。每个查询的最大异或

<?php
/**
 * @param Integer[] $nums
 * @param Integer $maximumBit
 * @return Integer[]
 */
function getMaximumXor($nums, $maximumBit) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [0,1,1,3];
$maximumBit = 2;
print_r(getMaximumXor($nums, $maximumBit));  // Output should be [0, 3, 2, 3]
?>

登录后复制

解释：

计算 maxNum:
- maxNum 的计算方式为 2^maximumBit - 1，即指定位长度的二进制全 1 的数字。
初始异或计算:
- 我们对 nums 中的所有元素进行异或，得到累积异或（currentXOR），代表数组中所有数字的异或。
向后迭代:
- 我们从 nums 中的最后一个元素开始，计算每一步的最大异或：
  - currentXOR ^ maxNum 给出当前状态的最大 k。
  - 将 k 添加到答案中。
- 然后我们将 nums 的最后一个元素与 currentXOR 进行异或，以将其从下一次迭代的异或和中“删除”。
返回答案：
- 由于我们反向处理了列表，答案将包含相反顺序的值，因此最终列表已经根据我们的要求正确排列。