每個查詢的最大異或-php教程-PHP中文網

每個查詢的最大異或

Mary-Kate Olsen

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

原創

315 人瀏覽過

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 進行異或，以將其從下一次迭代的異或和中「刪除」。
回答案：
- 由於我們反向處理了列表，答案將包含相反順序的值，因此最終列表已根據我們的要求正確排列。