Problem List
- [1] 数组中数字出现的次数I
- [2] 数组中数字出现的次数II
- [3] 剑指 Offer 65. 不用加减乘除做加法
1 I. 数组中数字出现的次数
1.1 题目描述
1.1 题目描述
一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
示例1：
输入: nums = [4,1,4,6]
输出: [1,6] 或 [6,1]
示例2：
输入: nums = [1,2,10,4,1,4,3,3]
输出: [2,10] 或 [10,2]
1.2 思路
先将问题简化为“数组中除了一个数，其他数都出现了两次”的子问题，而该子问题可以直接通过对数组的全部元素进行异或操作，由于相同数字进行异或的结果为0，而0和一个非零数进行异或的结果为该非零数，进而对数组进行异或最后的结果即为只出现一次的那个数字。
而此题是有两个数字出现了一次、其余数字均出现了两次，因而可以将数组分为两组进行异或，而两组异或后的结果就是这两个数。那么如何分组？这两个数进行异或都必不为0，因此可以用两者异或后的数中不为0的bit作为mask，按照mask来对数组进行分组。
class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
int tmp = 0;
for(int i: nums){
tmp ^= i;
}
int bit = 1;
while((tmp&bit) == 0){
bit <<= 1;
}
int a = 0, b = 0;
for(int i: nums){
if(bit&i){
a ^= i;
}else{
b ^= i;
}
}
return {a, b};
}
}; 2 II. 数组中数字出现的次数 II
2.1 题目描述
2.1 题目描述
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例1：
输入: nums = [3,4,3,3]
输出: 4
示例2：
输入: nums = [9,1,7,9,7,9,7]
输出: 1
2.2 思路
遍历整个数组，按位对每个元素的对应位置上的bit进行求和，当和不为3的整数倍，即sum%3 == 1时，说明只出现1次的那个数的当前位上的bit为1，则将该bit转为十进制并加到答案中即可。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;;
for(int i = 0; i < 31; ++i){
int cnt = 0;
for(int j: nums){
cnt += (j>>i & 1);
}
if(cnt % 3){
res += 1<<i;
}
}
return res;
}
}; 3 不用加减乘除做加法
3.1 题目描述
3.1 题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
示例1：
输入: a = 1, b = 1
输出: 2
3.2 思路
本题不允许任何四则运算，因而首先考虑位运算。首先考虑两个二进制数的相加：a=1001, b=1011.
- 异或操作：
a ^ b = 0010, 可以看作没有进位的加法. - 与操作：
a & b = 1001, 可以看作发生进位的数字，相应的进位实际上是加到其左移一位的位置上，即(a & b) <<1.
因此，两个数的加法可以看作无进位加法和进位的叠加，即a+b = a^b + (a&b)<<1. 注意，左侧为加法，右侧依然为加法，因而可以持续进行异或和与操作直至无进位即可实现无四则运算的加法。
class Solution {
public:
int add(int a, int b) {
while(b){
int tmp = a ^ b; // 不考虑进位的加和
b = (unsigned int)(a & b) << 1; // 进位
a = tmp;
}
return a;
}
}; 实际上，这个过程就是一个递归过程，递归的结束标志为进位为零，这里即指b == 0, 因而可以改写为以下代码：
class Solution {
public:
int add(int a, int b) {
if(b==0) return a;
return add(a^b, (unsigned int)(a&b)<<1);
}
};注意: Cpp里不支持对负数进行左移操作，因此需要将与操作的结果转换为无符号整型。
