1829. Maximum XOR for Each Query
给一个排序后的非负数矩阵nums，长度为n
再给一个maxnumBit
必须要执行n次下面的操作
1.找到一个非负整数k < 2^maxnumBit
使nums[0] xor nums[1] xor ...xor nums[nums.length-1] xor k是最大值
此时k就是answer[nums.length-1]的值
2.接着把nums最后的值去掉
最后回传answer
思路:
经过题目第1.操作后能得到的最大值就是 2^maxnumBit - 1
就先弄一个maxnum = 2^maxnumBit - 1
接着假设xor_result=nums[0] ^ nums[1] ^ ... ^ nums[nums.length-1]
再来就照着题目去做
因为ans[0] ^ xor_result = maxnum
所以ans[0] = xor_result ^ maxnum
就这样以此类推
记得每次操作后xor_result要xor nums[nums.length-1-i]
这样就可以得到答案了
C code :
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* getMaximumXor(int* nums, int numsSize, int maximumBit, int* returnSize) {
int *ans=(int*)calloc(numsSize,sizeof(int)),xor_res=0,max_num=0;
*returnSize=numsSize;
for (int i=0;i<maximumBit;i++)
{
max_num=(max_num<<1) +1 ;
}
for (int i=0;i<numsSize;i++)
{
xor_res^=nums[i];
}
for (int i=0;i<numsSize;i++)
{
ans[i]=xor_res^max_num;
xor_res ^= nums[numsSize-1-i];
}
return ans;
}

大师

大师