My Blog | 详情

1.leetcode_1829 - 求最大异或和 k 因子 https://leetcode.com/problems/maximum-xor-for-each-query/

思路：由于 k ∈ [0, 2^maxBit - 1], 而要求最大异或和也是 2^maxBit - 1, 不难想到我们总能找到 answer[i] 使得 XOR ^ answer[i] = 2^maxBit - 1, 其中 XOR 是 nums 当前所有元素的异或和。由于异或运算的归律，两边同乘 XOR，即 XOR ^ answer[i] ^ XOR = (2^maxBit - 1) ^ XOR 即 answer[i] = (2^maxBit - 1) ^ XOR, 所以对 i-th 次查询只需求 (2^maxBit - 1) ^ XOR 即可。

// AC: Runtime: 2 ms, faster than 99.68% of Java online submissions for Maximum XOR for Each Query.
// Memory Usage: 55.2 MB, less than 53.06% of Java online submissions for Maximum XOR for Each Query.
// for every query, answer is (2^maxBit - 1) ^ XOR, because we can always find a k to make XOR sum maximum.
// T:O(n), S:O(1)
// 
class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int size = nums.length, XOR = 0;
        for (int i: nums) {
            XOR ^= i;
        }

        int[] ret = new int[size];
        for (int i = 0; i < size; i++) {
            int answer = XOR ^ ((1 << maximumBit) - 1);
            ret[i] = answer;
            XOR ^= nums[size - 1 - i];
        }

        return ret;
    }
}