题目
简单题
136. 只出现一次的数字
190. 颠倒二进制位
268. 丢失的数字
剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
338. 比特位计数
389. 找不同
401. 二进制手表
461. 汉明距离
1863. 找出所有子集的异或总和再求和
1720. 解码异或后的数组
中等题
子集
137. 只出现一次的数字 II
371. 两整数之和 代码是真简单,想是真的难想 秒啊
477. 汉明距离总和 咦 会超时。。。
1310. 子数组异或查询
难题
67. 二进制求和 尝试不去使用字符转整形和整形转字符 只使用字符加法?
260. 只出现一次的数字 III 想想分类
题解
136. 只出现一次的数字 异或的性质
int singleNumber(int* nums, int numsSize){ int ans = 0;// 0和任何数异或还是0 for(int i = 0;i < numsSize;i++) ans ^= nums[i]; return ans; }
190. 颠倒二进制位
bool getbit(uint32_t n,int k){ return n & ((uint32_t)1<<k); } uint32_t reverseBits(uint32_t n) { for(int i = 0; i < 16; ++i) if(getbit(n,i) != getbit(n, 31-i)){ n ^= (uint32_t)1 << i; n ^= (uint32_t)1 << 31 - i; } return n; }
268. 丢失的数字异或的性质
int missingNumber(int* nums, int numsSize){ unsigned ans = 0; for(int i = 0;i < numsSize;++i)//全体的异或 ans ^= nums[i]; for(int i = 0;i < numsSize + 1;i++)//0-n的异或 ans ^= i; return ans; }
137. 只出现一次的数字 II
int singleNumber(int* nums, int numsSize){ unsigned ans = 0; for(unsigned i = 0;i < 32;i++){ unsigned temp = 0; for(int j = 0;j < numsSize;j++) temp += (((unsigned) 1<<i)&nums[j])>>i; //计算此位所有元素的和 temp %= 3;//出现三次就是能被3整除 结果只会是0或者1 ans += temp << i; } return ans; //强制类型转换 }
338. 比特位计数
int* countBits(int n, int* returnSize){ *returnSize = n + 1; int *ans = malloc(sizeof(int) * (n + 1)),size= 0;//返回数组 for(int i = 0;i <= n;i++){//遍历 int temp = i,count = 0; while(temp){//计数 if(temp & 1) count++; temp >>= 1; } ans[size++] = count; } return ans; }
389. 找不同
char findTheDifference(char * s, char * t){ char ans = 0; for(int i = 0;s[i];i++) ans ^= s[i]; for(int j = 0;t[j];++j) ans ^= t[j]; return ans; }
401. 二进制手表
int countbit(int n){//数个数 int count = 0; while(n){ if(n&1) count++; n>>=1; } return count; } char ** readBinaryWatch(int turnedOn, int* returnSize){ char** ans = malloc(sizeof(char*) * 12 * 60); //申请空间 最多60种 *returnSize = 0; //返回大小 for (int h = 0; h < 12; ++h) {//枚举 for (int m = 0; m < 60; ++m) { if (countbit(h) +countbit(m) == turnedOn) { char* tmp = malloc(sizeof(char) * 6); //申请返回空间 6个字符刚好 sprintf(tmp, "%d:%02d", h, m); ans[(*returnSize)++] = tmp; } } } return ans; }
461. 汉明距离
int hammingDistance(int x, int y){ int count = 0; for(unsigned i = 1;i < 2147483648;i<<=1)//计算距离 if((i&x)^(i&y)) count++; return count; }
1863. 找出所有子集的异或总和再求和
int subsetXORSum(int* nums, int numsSize){ int num = 0; for(int i = 0; i < (1 << numsSize); ++i){//所有子集 int ans = 0; for(int j = 0; j < numsSize; ++j)//求异或 if(i&(1<<j)) ans ^= nums[j]; num += ans;//加和 } return num; } 剑指 Offer II 003. 前 n 个数字二进制中 1 的个数 int* countBits(int n, int* returnSize){ *returnSize = n + 1; int *ans = malloc(sizeof(int) * (n + 1)),size= 0; for(int i = 0;i <= n;i++){ int temp = i,count = 0; while(temp){ if(temp & 1) count++; temp >>= 1; } ans[size++] = count; } return ans; }
1720. 解码异或后的数组
int* decode(int* encoded, int encodedSize, int first, int* returnSize){ *returnSize = encodedSize + 1; int *ans = malloc(sizeof(int)*(encodedSize + 1) ); ans[0] = first; for(int i = 0; i < encodedSize; ++i) ans[i+1] = encoded[i] ^ ans[i]; return ans; }
78. 子集
int** subsets(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){ *returnSize = pow(2,numsSize); (*returnColumnSizes) = malloc(sizeof(int)*(*returnSize)); int **ans = malloc(sizeof(int *)*(*returnSize));//申请指针空间 int row = 0; ans[row] = 0; (*returnColumnSizes)[row++] = 0; for(int i = 1;i < pow(2,numsSize);i++){//循环所有生成所有子集 int *hash = malloc(sizeof(int) * 10),hashnum = 0;//申请每行的空间 for(int j = 0;j <10;j++) if((1<<j)&i) hash[hashnum++] = nums[j]; ans[row] = hash; (*returnColumnSizes)[row++] = hashnum; } return ans; }
371. 两整数之和
int getSum(int a, int b){ while(b){ unsigned temp = ((unsigned)a&(unsigned)b) << 1; a = a ^ b; b = temp; } return a; }
477. 汉明距离总和
int totalHammingDistance(int* nums, int numsSize){ int ans = 0; for(int i = 0;i < 32;i++){//按位计算 int count = 0; for(int j = 0;j < numsSize;j++) if(nums[j] & ((unsigned)1<<i)) count++; ans+=(numsSize - count)*count;//此位贡献的海明距离 } return ans; }
1310. 子数组异或查询
int* xorQueries(int* arr, int arrSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize){ int *ans=malloc(sizeof(int)*(queriesSize)); int qianzui[arrSize + 1];//前缀异或 *returnSize = 0; qianzui[0] = 0; for(int i = 0;i<arrSize;i++) qianzui[i+1] = qianzui[i] ^arr[i]; for(int i = 0;i <queriesSize;i++) ans[(*returnSize)++] = qianzui[queries[i][0]] ^ qianzui[queries[i][1]+1]; return ans; } 二进制求和 尝试不去使用字符转整形和整形转字符 只使用字符加法? char * addBinary(char * a, char * b){ char *ans = malloc(sizeof(char)*10010); int ansnum = 0; int jinwei = 0; //进位的值 int i = strlen(a) - 1,j = strlen(b) - 1; for(;i >=0 && j >= 0;i--,j--){ //处理字符串 if(a[i] -'0' + b[j] - '0' + jinwei >= 2){ //产生进位 ans[ansnum++] = a[i] - '0' + b[j] + jinwei - 2;//记录结果 jinwei = 1; } else{ ans[ansnum++] = a[i] - '0' + b[j] +jinwei; jinwei = 0; } } while(i >= 0) { //处理a过长 if(a[i] - '0' + jinwei >= 2){ ans[ansnum++] = a[i] +jinwei - 2; jinwei = 1; } else{ ans[ansnum++] = a[i] + jinwei; jinwei = 0; } i--; } while(j >= 0) { //处理b过长 if(b[j] - '0' + jinwei >= 2){ ans[ansnum++] = b[j] +jinwei - 2; jinwei = 1; } else{ ans[ansnum++] = b[j] + jinwei; jinwei = 0; } j--; } if(jinwei) ans[ansnum++] = jinwei +'0'; //处理最终进位 for(int i = 0;i < ansnum/2;i++){ //反转字符串 ans[i] = ans[i] ^ ans[ansnum - i - 1]; ans[ansnum - i - 1] = ans[i] ^ ans[ansnum - i - 1]; ans[i] = ans[i] ^ ans[ansnum - i - 1]; } ans[ansnum] = 0; return ans; }
260. 只出现一次的数字 III 想想分类
int* singleNumber(int* nums, int numsSize, int* returnSize){ unsigned ans = 0, *ans1= malloc(sizeof(unsigned)*2); memset(ans1,0,sizeof(ans1)); unsigned i ; for(i = 0;i <numsSize;++i) ans ^= nums[i]; //求出a^b for(i = 1;i < 4294967296;i<<=1) if(i & ans) break; //第i位不同 for(int j = 0;j < numsSize;++j) if(nums[j] & i) ans1[0] ^= nums[j]; else ans1[1] ^= nums[j]; *returnSize = 2; return ans1; }