文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個 有序 數組 nums ，它由 n 個非負整數組成，同時給你一個整數 maximumBit 。你需要執行以下查詢 n 次：

• 找到一個非負整數 k < 2^maximumBit ，使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的結果 最大化 。k 是第 i 個查詢的答案。
• 從當前數組 nums 刪除 最后 一個元素。

請你返回一個數組 answer ，其中 answer[i]是第 i 個查詢的結果。

示例 1： 輸入：nums = [0,1,1,3], maximumBit = 2 輸出：[0,3,2,3] 解釋：查詢的答案如下： 第一個查詢：nums = [0,1,1,3]，k = 0，因為 0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。 第二個查詢：nums = [0,1,1]，k = 3，因為 0 XOR 1 XOR 1 XOR 3 = 3 。 第三個查詢：nums = [0,1]，k = 2，因為 0 XOR 1 XOR 2 = 3 。 第四個查詢：nums = [0]，k = 3，因為 0 XOR 3 = 3 。示例 2： 輸入：nums = [2,3,4,7], maximumBit = 3 輸出：[5,2,6,5] 解釋：查詢的答案如下： 第一個查詢：nums = [2,3,4,7]，k = 5，因為 2 XOR 3 XOR 4 XOR 7 XOR 5 = 7。 第二個查詢：nums = [2,3,4]，k = 2，因為 2 XOR 3 XOR 4 XOR 2 = 7 。 第三個查詢：nums = [2,3]，k = 6，因為 2 XOR 3 XOR 6 = 7 。 第四個查詢：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 <= n <= 10^5 1 <= maximumBit <= 20 0 <= nums[i] < 2^maximumBit nums??? 中的數字已經按 升序 排好序。

https://leetcode-cn.com/contest/biweekly-contest-50/problems/maximum-xor-for-each-query/

2. 解題

class Solution { public:vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {int n = nums.size();vector<int> ans(n);int XOR = 0;for(int i = 0; i < n; i++){XOR ^= nums[i];//前綴異或int t = XOR, k = 0;for(int j = 0; j < maximumBit; j++){if(((t>>j)&1)==0)//前綴異或 j 位 為 0，將其變成1k |= 1<<j;}ans[n-1-i] = k;}return ans;} };

• 直接求前綴異或 的 低maximumBit位的反即可

class Solution { public:vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {int n = nums.size();vector<int> ans(n);int XOR = 0;for(int i = 0; i < n; i++){XOR ^= nums[i];//前綴異或 ans[n-1-i] = (~XOR)^(~((1<<maximumBit)-1));}return ans;} };

160 ms 90.5 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 1829. 每个查询的最大异或值（前缀异或 + 位运算）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。