我要成为算法高手-位运算篇

前情提要：如果对一些常见的二进制位运算不熟悉，请看这篇文章： 常见的位运算

1. 判断字符是否唯一

面试题 01.01. 判定字符是否唯一 - 力扣（LeetCode）

思路：利用位图的思想，定义一个整数来模拟哈希表，根据每个比特位对应的值来映射字符

代码实现：

class Solution {public boolean isUnique(String astr) {        int BitMap = 0;int n = astr.length();if(n > 26){return false;}for(int i=0;i<n;i++) {char ch = astr.charAt(i);if(((BitMap>>(ch-'a')) & 1)==1){return false;} else {BitMap |= (1<<(ch-'a'));}}return true;}
}

2. 消失的数字

268. 丢失的数字 - 力扣（LeetCode）

思路：

代码实现：

class Solution {public int missingNumber(int[] nums) {// 异或运算int n = nums.length;int ret = 0;for(int i=0;i<=n;i++){ret^=i;}for (int i = 0; i < n; i++) {ret ^= nums[i];}return ret;// int n = nums.length;// //高斯求和// int sum = ((n)*(n+1))/2;// int numsSum = 0;// for(int i=0;i<nums.length;i++) {// numsSum += nums[i];// }// return sum - numsSum;}
}

3. 两整数之和

371. 两整数之和 - 力扣（LeetCode）

思路：

1、让这两个数a、b无进位相加（异或）所得结果x

2、a和b按位与所得结果carry

3、a=x，b=carry

4、a和b无进位相加（疑惑）

循环上面步骤直到b为0，此时相加结果是a

class Solution {public int getSum(int a, int b) {while(b!=0){int x = a^b;//先计算无进位相加int carry = (a & b)<<1;a = x;b = carry;}return a;}
}

4. 只出现一次的数字II

137. 只出现一次的数字 II - 力扣（LeetCode）

思路：

定义一个变量ret，依次计算nums数组中第i位的和sum，接着让sum%3，根据结果对应的值修改ret对应比特位的值

class Solution {public int singleNumber(int[] nums) {int ret = 0;for(int i=0;i<32;i++){//依次修改ret中的每一位int sum = 0;for(int j=0;j<nums.length;j++){sum+= ((nums[j]>>i)&1);//计算第i位的和}sum%=3;if(sum==1){//修改第i位置的值ret |= (1<<i);}}return ret;}
}

5. 消失的两个数字

面试题 17.19. 消失的两个数字 - 力扣（LeetCode）

思路：

class Solution {public int[] missingTwo(int[] nums) {int len = nums.length;int N = len + 2;int ret = 0;for (int i = 0; i < nums.length; i++) {ret ^= nums[i];}for (int i = 1; i <= N; i++) {ret ^= i;}// ret为消失的两个数^的结果int lowBit = ret & (-ret);int[] ans = new int[2];ans[0] = 0;ans[1] = 0;for (int i = 1; i <= N; i++) {if ((i & lowBit) != 0) {ans[0] ^= i;} else {ans[1] ^= i;}}for (int i = 0; i < nums.length; i++) {if ((nums[i] & lowBit) != 0) {ans[0] ^= nums[i];} else {ans[1] ^= nums[i];}}return ans;}
}