每個查詢的最大異或

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 按升序順序排序。

提示：

1. 請注意，最大可能的 XOR 結果總是 2^{(maximumBit) - 1}
2. 因此前綴的答案是該前綴與 2^{(maximumBit)-1} 的異或

解：

我們需要有效地計算數組中元素的異或，並使用值 k 來最大化結果，使得 k 小於 2^maximumBit。解決這個問題的方法如下：

觀察和方法

1. 最大化異或:
   我們可以與任何前綴和進行異或運算的最大位數是（2^{text{maximumBit}} - 1）。這是因為與多個全 1（即二進位的 111...1）進行異或總是會最大化結果。

2. 前綴異或計算:
   我們可以為整個陣列維護一個累積的 XOR，而不是為每個查詢重新計算 XOR。由於 XOR 具有 A XOR B XOR B = A 的屬性，因此可以透過從累積 XOR 中異或出該元素來從陣列中刪除最後一個元素。

3. 演算法:

   • 先計算 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]
?>

解釋：

1. 計算 maxNum:

   • maxNum 的計算方式為 2^maximumBit - 1，即指定位長度的二進位全 1 的數字。

2. 初始異或計算:

   • 我們對 nums 中的所有元素進行異或，得到累積異或（currentXOR），代表數組中所有數字的異或。

3. 向後迭代:

   • 我們從 nums 中的最後一個元素開始，計算每一步的最大異或：
     • currentXOR ^ maxNum 給出當前狀態的最大 k。
     • 將 k 加入答案。
   • 然後我們將 nums 的最後一個元素與 currentXOR 進行異或，以將其從下一次迭代的異或和中「刪除」。

4. 回答案：

   • 由於我們反向處理了列表，答案將包含相反順序的值，因此最終列表已根據我們的要求正確排列。

複雜性分析

• 時間複雜度：O(n)，因為我們在O(n)中計算初始異或，並且每個查詢都會在恆定時間內處理。
• 空間複雜度：O(n)，用於儲存答案。

這段程式碼很高效，應該可以很好地處理約束的上限。

聯絡連結

如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！

如果您想要更多類似的有用內容，請隨時關注我：

• 領英
• GitHub

以上是每個查詢的最大異或的詳細內容。更多資訊請關注PHP中文網其他相關文章！