位运算题目-Java实现-LeetCode题解：判断字符是否唯一-丢失的数字-两整数之和-只出现一次的数字 II-消失的两个数字
这里是Themberfue
上一篇文章讲完了常见位运算的技巧以及总结
那么本章则通过五道题来运用这些技巧
判定字符是否唯一
题目解析
本题要求判断给定字符串中的字符是否唯一，也就是每个字符是否只出现一次
算法讲解
· 本题用哈希表遍历每一个字符也可以解决
· 如果这题使用位运算的技巧的做题的话，还需引入一个位图的概念：众所周知，int类型有32个bit位，每个bit位不是0就是1，那么便可利用这一性质。
· 将这32个bit位看成一个长度为32的boolean类型的数组，0表示假，1表示真
· 再用到 判断一个数字的某一位是否为0，以及，将一个数字的某一位的0改为1。运用这两个位运算技巧便可解出此题。
编写代码
class Solution {
public boolean isUnique(String astr) {
char[] s = astr.toCharArray();
// 鸽巢原理
if (s.length > 26) return false;
// 位图的思想 => 使用比特位存储信息
int bitMap = 0;
for (char ch: s) {
int x = ch - 'a';
if (((bitMap >> x) & 1) == 1) {
return false;
}
bitMap |= 1 << x;
}
return true;
}
}丢失的数字
题目解析
本题要求寻找丢失的那个数字，我觉得看到示例解释应该就能看懂了
算法讲解
· 我们额外创建一个数组，其长度应该为给定数组长度加一：比如示例3中，n = 9，那么我们的创建数组的长度应该为10，我们需要初始化数组为包含 [0, 9] 中所有数字。
· 有了这一数组，不难发现，除了给定数组那个丢失的数字，加上我们创建的数组，每个数字肯定出现了两次。
· 根据异或(^)运算符的特性，相同的两个数异或的结果为0，所以我们将这两个数组都异或在一起。那么结果就是那个丢失的数字。
· 我们不需要关系异或顺序，因为异或好比乘法，先乘还是后乘都是一样的。
编写代码
class Solution {
public int missingNumber(int[] nums) {
int ret = 0;
for (int x: nums) ret ^= x;
for (int i = 0; i <= nums.length; i++) ret ^= i;
return ret;
}
}两整数之和
题目解析
本题就是求给定两个数的和，但是切记不能使用 + - 运算符，不然回去等通知吧
算法讲解
· 重复下面这个步骤，直到 b 等于 0 ，那么此时的 a 就是结果。
· 异或( ^ )操作符的本质就是无进位相加，所以我们再获取二数实际需要在哪个地方的进位就可以
· (a & b) << 1完成的就是这个操作
编写代码
class Solution {
public int getSum(int a, int b) {
while (b != 0) {
int carry = (a & b) << 1;
a = a ^ b;
b = carry;
}
return a;
}
}只出现一次的数字 II
题目解析
算法讲解
编写代码
class Solution {
public int singleNumber(int[] nums) {
int ret = 0;
for (int i = 0; i < 32; i++) {
int sum = 0;
for (int num: nums) {
if ((num >> i & 1) == 1) sum++;
}
sum %= 3;
if (sum == 1) ret |= 1 << i;
}
return ret;
}
}消失的两个数字
题目解析
算法讲解
编写代码
class Solution {
public int[] missingTwo(int[] nums) {
// 将所有数字异或在一起
int xorsum = 0;
for (int num: nums) xorsum ^= num;
for (int i = 1; i <= nums.length + 2; i++) xorsum ^= i;
// 找出两个数字比特位不同的那位
int lsb = 0;
while (true) {
if (((xorsum >> lsb) & 1) == 1) break;
else lsb++;
}
int type1 = 0, type2 = 0;
for (int num: nums) {
if (((num >> lsb) & 1) == 1) type1 ^= num;
else type2 ^= num;
}
for (int i = 1; i <= nums.length + 2; i++) {
if (((i >> lsb) & 1) == 1) type1 ^= i;
else type2 ^= i;
}
return new int[]{type1, type2};
}
}