[TOC]
本文主要记录前缀和的相关LeetCode题目的实现代码，直接给出本文各个题目的答案，供有需求的读者学习或复制。
一、二进制计数问题
461. 汉明距离（简单难度）
class Solution {
public:
int hammingDistance(int x, int y) {
// 方法一：进制转换
// int count=0;
// if(x==y)
// return 0;
// // 同时取位
// while(x!=0||y!=0){
// if(x%2!=y%2)
// count++;
// x=x/2;
// y=y/2;
// }
// return count;
// 方法二：位运算
int count=0;
int a=x^y;// 异或运算，相同为0，不同为1
while(a){
count+=a&1;// 查看最后一位是否是1
a>>=1;// 右移1位
}
return count;
}
};
191. 位1的个数（简单难度）
剑指 Offer 15. 二进制中1的个数（简单难度）
class Solution {
public:
int hammingWeight(uint32_t n) {
// 方法一：进制转换
// string kbits="";
// if(n==0) kbits="0";
// while(n){
// kbits=to_string(n%2)+kbits;
// n/=2;
// }
// //
// int res=0;
// for(char c:kbits){
// if(c=='1') res++;
// }
// return res;
// 方法二:位运算
int count = 0;
while (n) {
count += n & 1;
n>>=1;
}
return count;
}
};
190. 颠倒二进制位（简单难度）
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t rev = 0;
int power=31;
while(n){
rev+=(n&1)<<power;//左移32位
n>>=1;
power--;
}
return rev;
}
};
二、数组中元素出现的次数
1、一个数出现1次，其余数都出现2次
136. 只出现一次的数字（简单难度）
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 方法一：位运算
// 数组中一定有奇数个元素，数组中的全部元素进行异或运算，结果即为只出现一次的数字
// int res=0;
// for(int num:nums) res^=num;
// return res;
// 方法二：位运算
int res=0;
for(int i=0;i<32;i++){
int mask=1<<i;//从右向左取第i位
int cnt = 0;//第i位出现的次数
// 遍历整个数组后的第i位出现了几次1
for (int num:nums) {
if ((num & mask) != 0) {
cnt++;
}
}
// 如果第i位没有出现3次则保留
if (cnt % 2 != 0) {
res |= mask;
}
}
return res;
// // 方法二：哈希法
// unordered_map<int,int> map;// 数字和出现次数
// // 遍历数组一遍统计频率
// for(int num:nums){
// map[num]++;
// }
// // 遍历哈希表
// for(auto it=map.begin();it!=map.end();++it){
// if(it->second==1)
// return it->first;
// }
// return -1;
}
};
2、一个数出现1次，其余数都出现3次
137. 只出现一次的数字 II（中等难度）
剑指 Offer 56 - II. 数组中数字出现的次数 II（中等难度）
剑指 Offer II 004. 只出现一次的数字（中等难度）
class Solution {
public:
int singleNumber(vector<int>& nums) {
// 方法一：位运算(异或)
// int ones=0;twos=0;
// for(int num:nums){
// ones=ones^num&(~twos);//x & ~x = 0;// num，0,0
// twos=twos^num&(~ones);//x & ~0 = x;// 0，num，0
// }
// return ones;
// 方法二：位运算
int res=0;
for(int i=0;i<32;i++){
int mask=1<<i;//从右向左取第i位
int cnt = 0;//第i位出现的次数
// 遍历整个数组后的第i位出现了几次1
for (int num:nums) {
if ((num & mask) != 0) {
cnt++;
}
}
// 如果第i位没有出现3次则保留
if (cnt % 3 != 0) {
res |= mask;
}
}
return res;
// 方法二：哈希法
// unordered_map<int,int> map;// 数字和出现次数
// // 遍历数组一遍统计频率
// for(int num:nums){
// map[num]++;
// }
// // 再次遍历遍历字符串
// for(int num:nums){
// if(map[num]==1)
// return num;
// }
// return -1;
}
};
3、两个数出现1次，其余数都出现2次
260. 只出现一次的数字 III（中等难度）
剑指 Offer 56 - I. 数组中数字出现的次数（中等难度）
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
vector<int> res(2,0);
int aob=0;
for(int num:nums){
aob^=num;
}
// 取出最后一位
int lastBit = (aob == INT_MIN ? aob : aob & (-aob));// 防止溢出
for (int num : nums) {
// 分成2个数
if ((lastBit & num) != 0)
res[0] ^= num;
else
res[1] ^= num;
}
return res;
}
};
二、四则运算
1、两数加法
371. 两整数之和（简单难度）
剑指 Offer 65. 不用加减乘除做加法（简单难度）
面试题 17.01. 不用加号的加法（简单难度）
class Solution {
public:
int getSum(int a, int b) {
// 当进位部分不为0，说明需要继续加
while (a != 0) {
int temp = a ^ b;//非进位部分（没有添加进位部分），按位异或，
//异或这里可看做是相加但是不显现进位，比如5 ^ 3
/*0 1 0 1
0 0 1 1
------------
0 1 1 0 */
a = ((unsigned int)a & b) << 1; //进位部分，都是1是发生进位，对有符号左移的溢出保护处理
//相与为了让进位显现出来，比如5 & 3
/* 0 1 0 1
0 0 1 1
------------
0 0 0 1
上面的最低位1和1相与得1*/
b = temp;
}
return b;
}
};
67. 二进制求和（简单难度）
剑指 Offer II 002. 二进制加法（简单难度）
class Solution {
public:
string addBinary(string a, string b) {
string res;
// 从右向左同时遍历2个可能不等长的字符串
int i=a.length()-1;
int j=b.length()-1;
bool carry=false;
int sum=0;
while(i>=0||j>=0){
sum=0;
if(i>=0) sum+=a[i--]-'0';
if(j>=0) sum+=b[j--]-'0';
if(carry) sum+=1;
res =to_string(sum%2)+res;
carry=sum>=2?true:false;
}
// 如果有多余的进位
if(carry) res =to_string(1)+res;
return res;
}
};
989. 数组形式的整数加法（简单难度）
class Solution {
public:
vector<int> addToArrayForm(vector<int>& num, int k) {
vector<int> res;
// 从右向左同时遍历2个可能不等长的序列
int i=num.size()-1;
int sum=0;
bool carry=false;
while(i>=0||k){
sum=0;
if(i>=0)sum+=num[i--];
if(k){
sum+=k%10;
k/=10;
}
if(carry) sum+=1;
res.push_back(sum%10);
carry=sum>=10?true:false;
}
if(carry) res.push_back(1);
reverse(res.begin(),res.end());//反转
return res;
}
};
415. 字符串相加（简单难度）
class Solution {
public:
string addStrings(string num1, string num2) {
string res;
// 从右向左同时遍历2个可能不等长的字符串
int i=num1.length()-1;
int j=num2.length()-1;
bool carry=false;
int sum=0;
while(i>=0||j>=0){
sum=0;
if(i>=0) sum+=num1[i--]-'0';
if(j>=0) sum+=num2[j--]-'0';
if(carry) sum+=1;
res =to_string(sum%10)+res;
carry=sum>=10?true:false;
}
// 如果有多余的进位
if(carry) res =to_string(1)+res;
return res;
}
};