Day 08
异或运算:x ^ 0 = x , x ^ 1 = ~x
与运算:x & 0 = 0 , x & 1 = x
数组中数字出现的次数 I
在一个数组 nums 中除两个数字只出现一次之外,其他数字都出现了两次。请找出只出现一次的数字。
思路: 这个问题在于如何找出两个出现一次的数字。假设数字分别为x,y
如果只有一个数字,那么将数组所有数字异或便能得到那个数。但是题目中有两个,那么异或的结果为x^y。
因为x和y必不相同,所以至少二进制中有一位不相同,因此根据此位可以将 nums 拆分为分别包含 x 和 y 的两个子数组。易知两子数组都满足 「除一个数字之外,其他数字都出现了两次」。因此,仿照以上一个数字问题的思路,分别对两子数组遍历执行异或操作,即可得到两个只出现一次的数字 x, y 。
class Solution {
public int[] singleNumbers(int[] nums) {
int x = 0, y = 0, n = 0, m = 1;
for(int num : nums) // 1. 遍历异或
n ^= num;
while((n & m) == 0) // 2. 循环左移,计算 m
m <<= 1;
for(int num: nums) { // 3. 遍历 nums 分组
if((num & m) != 0) x ^= num; // 4. 当 num & m != 0
else y ^= num; // 4. 当 num & m == 0
}
return new int[] {x, y}; // 5. 返回出现一次的数字
}
}
数组中数字出现的次数 II
在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
思路: 各二进制位的 位运算规则相同 ,因此只需考虑一位即可。如下图所示,对于所有数字中的某二进制位 1 的个数,存在 3 种状态,即对 3 余数为 0, 1, 2。
若输入二进制位 1 ,则状态按照0->1->2顺序转换;
若输入二进制位 0 ,则状态不变。
例:
class Solution {
public int singleNumber(int[] nums) {
int ones = 0, twos = 0;
for(int num : nums){
ones = ones ^ num & ~twos;
twos = twos ^ num & ~ones;
}
return ones;
}
}
不用加减乘除做加法
写一个函数,求两个整数之和,要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。
思路: 一拿过来确实有些懵,这个题其实本质上还是用到了异或,可见异或在处理位运算问题的重要性。
可见,无进位和与异或相同,进位与与运算相同但是需要左移一位。所以两个数的和就是无进位和加进位。但是不能出现“+”,因此只能继续做无进位和,直到进位为0,得到结果
class Solution {
public int add(int a, int b) {
while(b != 0) { // 当进位为 0 时跳出
int c = (a & b) << 1; // c = 进位
a ^= b; // a = 非进位和
b = c; // b = 进位
}
return a;
}
}