目录
传送门
题目描述：
给定一个整数数组
nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
回想昨天那个只出现一次的数字（其余均出现两次）,我们是利用两个相同的数异或为0，异或所有数就行了
int singleNumber(int* nums, int numsSize){
int ans = 0,i;
for(i=0; i<numsSize; ++i){
ans ^= nums[i]; // n^n = 0 且 n^0 = n
}
return ans;
}但这题，只出现一次的数字有两个a、b，异或所有数的结果是 sum = a^b
所以我们可以想办法把a、b分到两个不同的组，然后异或得到的便是a、b
因为 sum = a ^ b 如果sum的某一位位1，则说明a 和 b在这一位的状态是不同的，所以我们可以随便找一位sum为1的位，按照这一位进行分组
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* singleNumber(int* nums, int numsSize, int* returnSize){
int sum = 0,i,k;
for(i=0; i<numsSize; ++i){
sum ^= nums[i]; //异或所有 得到的sum = a ^ b
}
for(i=0; i<=31; ++i){
if((sum>>i)&1){ // 随便找到一位 sum 位1的位
k = 1L<<i; // 使K的这位置1
break;
}
}
int a=0,b=0;
for(i=0; i<numsSize; ++i){
if(nums[i] & k) // 按这位进行分组,位1 为一组,位0 为另外一组
a ^= nums[i];
else
b ^= nums[i];
}
*returnSize = 2;
nums[0] = a;nums[1] = b;
return nums;
}习题
1442. 形成两个异或相等数组的三元数目
题目描述：
给你一个整数数组 arr 。
现需要从数组中取三个下标 i、j 和 k ，其中 (0 <= i < j <= k < arr.length) 。
a 和 b 定义如下：
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
注意：^ 表示 按位异或 操作。请返回能够令 a == b 成立的三元组 (i, j , k) 的数目。
最直观的想法就是直接暴力，四层循环，超时……
然后就想到了前缀和，三层循环，给过了
int countTriplets(int* arr, int arrSize){
int *sum = (int*)malloc(sizeof(int)*(arrSize+1));
memset(sum,0,sizeof(sum));
int i,j,k,ans = 0;
for(i=1; i<=arrSize; ++i){
sum[i] = (sum[i-1] ^ arr[i-1]); //构造前缀和（异或）数组
}
for(i=1; i<=arrSize; ++i){
for(j=i+1; j<=arrSize; ++j){ //
// int t=0;
for(k=j; k<=arrSize; ++k){
if((sum[i-1]^sum[j-1]) == (sum[k]^sum[j-1]))
++ans;
}
}
}
free(sum);
return ans;
}