Try   HackMD

LeetCode 1829. Maximum XOR for Each Query

https://leetcode.com/problems/maximum-xor-for-each-query/description/

題目大意

給定長度為 n 的有序非負整數陣列 nums及整數 maximumBit

你執行以下操作 n 次:

  1. 找到一個非負整數 k,其中 k < 2^maximumBit,使得 nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k 的值最大,k 即為第 i 次操作的答案
  2. 從當前的陣列 nums 中移除最後一個元素

回傳一個陣列 answer,其中 answer[i] 是第 i 次操作的答案

思考

如果被題目給迷惑的人可能不會立刻注意到,每次操作後要使值最大,那個值不用多想,就是 2^maximumBit - 1
我們只需要透過 XOR 的特性去反算出 k 就好

C++ 參考答案:

class Solution
{
public:
    vector<int> getMaximumXor(vector<int> &nums, int maximumBit)
    {
        const int mx = (1 << maximumBit) - 1;
        vector<int> ans;
        ans.reserve(nums.size());
        int xors = 0;

        for (int num : nums)
        {
            xors ^= num;
            ans.push_back(xors ^ mx);
        }

        reverse(ans.begin(), ans.end());

        return ans;
    }
};

Go 參考答案:

func getMaximumXor(nums []int, maximumBit int) []int {
	mx := (1 << maximumBit) - 1
	n := len(nums)
	ans := make([]int, n)
	xors := 0

	for i, num := range nums {
		xors ^= num
		ans[n-i-1] = xors ^ mx
	}

	return ans
}