编辑
阿华代码，不是逆风，就是我疯
你们的点赞收藏是我前进最大的动力！！
希望本文内容能够帮助到你！！
目录
零：位运算基础公式
编辑
编辑
零：五道基础题
1：位1的个数
编辑
class Solution { public int hammingWeight(int n) { int count = 0; while(n != 0){ n &= (n-1); //干掉n最右侧的1 count++; } return count; } }
2：比特位计数
编辑
class Solution { public int[] countBits(int n) { int[] ans = new int[n+1]; for(int i = 0 ; i <= n ; i++ ){ int count = 0 , tem = i; while(tem != 0){ tem &= (tem-1);//干掉最右侧的1 count++; } ans[i] = count; } return ans; } }
3：汉明距离
编辑
class Solution { public int hammingDistance(int x, int y) { int tem = x ^ y; int count = 0; while(tem != 0){ tem &= (tem-1); count++; } return count; } }
4：只出现一次的数字|
编辑
class Solution { public int singleNumber(int[] nums) { int ret = nums[0]; for(int i = 1 ; i < nums.length ; i++){ ret ^= nums[i]; } return ret; } }
5：只出现一次的数字|||
用位上数字不同进行分组
编辑
class Solution { public int[] singleNumber(int[] nums) { int ret = 0; for(int x : nums){ ret ^= x; } int sign = ret & (-ret); int firNum = 0; int secNum = 0; for(int x : nums){ if((sign & x) == 0){ firNum ^= x; }else{ secNum ^= x; } } int[] result = new int[2]; result[0] = firNum; result[1] = secNum; return result; } }
一：判定字符是否唯一
1：位图思想总结
编辑
编辑
2：位图思想和hash表两种方法
编辑
class Solution { public boolean isUnique(String astr) { //鸽巢原理优化 if(astr.length() > 26){ return false; } //位图原理 char[] str = astr.toCharArray(); int bitMap = 0; for(int x : str){ int move = x - 'a'; if((bitMap & (1 << move)) == 0){ //bitMap&0001000只有非0或者0两个结果 //说明当前bitMap位是0，那就添加进去 bitMap |= (1 << move); }else{ return false; } } return true; } } //1:把字符串转化为字符数组 // char[] str = astr.toCharArray(); // //2:把字符扔到hash表中 // Map<Character,Integer> hash = new HashMap<>(); // for(char x : str){ // //获取hash表中x的value值 // int num = hash.getOrDefault(x,0); // if(num == 0){ // hash.put(x,hash.getOrDefault(x,0)+1); // }else{ // return false; // } // } // return true;
二：丢失的数字
编辑
class Solution { public int missingNumber(int[] nums) { //高斯求和 int len = nums.length; int sum1 = 0; for(int i = 0 ; i < len ; i++){ sum1 += nums[i]; } int sum2 = (0+len)*(len+1)/2; int ret = sum2 - sum1; return ret; } } // hash数组 // int len = nums.length; // int[] hash = new int[len+1]; // for(int i = 0 ; i < len ; i++){ // hash[nums[i]] = 1; // } // int ret = 0; // for(int i = 0 ; i < len+1 ; i++){ // if(hash[i] == 0){ // ret = i; // }else{ // } // } // return ret; // 异或运算方法 // int len = nums.length; // int[] arr = new int[2*len+1]; // for(int i = 0 ; i < len ; i++){ // arr[i] = nums[i]; // } // int count = 0; // for(int i = len ; i < (2*len+1) ; i++){//i作为添加元素的下标 // arr[i] = count; // count++; // } // int ret = 0; // for(int x : arr){ // ret ^= x; // } // return ret;
三：两整数之和
耍赖：直接return；正规军：异或运算无进位相加
编辑
class Solution { public int getSum(int a, int b) { while(b != 0){ int ret = a ^ b;//结果 int x = (a & b)<<1; a = ret; b = x; } return a; } } // return a + b;
四：只出现一次的数字||
137. 只出现一次的数字 II - 力扣（LeetCode）
编辑
编辑
class Solution { public int singleNumber(int[] nums) { //这一层for循环i作为比特位 int ret = 0; for(int j = 0 ; j < 32 ; j++){ //所有元素的该bit位相加 int sum = 0; for(int i = 0 ; i < nums.length ; i++){ sum += (nums[i]>>j)&1; } int tem = sum % 3; if(tem == 1){ ret |= (1<<j); }else{ ret &= ~(1<<j); } } return ret; } }
五：消失的两个数字
面试题 17.19. 消失的两个数字 - 力扣（LeetCode）
编辑
class Solution { public int[] missingTwo(int[] nums) { //创建tem数组用来存放nums数组中的元素和1~N数字 int len = nums.length; int n = len + 2; int[] tem = new int[2*len+2]; //处理nums数组 int ret = 0; for(int i = 0 ; i < nums.length ; i++){ ret ^= nums[i]; tem[i] = nums[i]; } //处理1~N for(int i = 1 ; i <= n ; i++){ ret ^= i; tem[len-1+i] = i; } int sign = 0; while(ret != 0){ if( ((ret >> sign) & 1) == 1){ break; }else{ sign++; } } //基于sign把数组分成两组 int[] result = new int[2]; for(int x : tem){ if(((x >> sign) & 1) == 1){ result[0] ^= x; }else{ result[1] ^= x; } } return result; } }
class Solution { //穷举法 public int[] missingTwo(int[] nums) { Arrays.sort(nums); int len = nums.length; int[] ret = new int[2]; int j = 0; for(int i = 0 ; i < nums.length-1 ; i++){ int tem = nums[i+1] - nums[i]; if(tem == 2){ ret[j++] = nums[i]+1; }else if(tem == 3){ ret[j++] = nums[i]+1; ret[j] = nums[i]+2; } } if(nums[0] != 1){ if(ret[0] == 0){ ret[0] = 1; if(len == 1){ if(nums[0]-1 > 1){ ret[1] = 2; }else{ ret[1] = 3; } }else{ ret[1] = nums[len-1]+1; } }else{ if(ret[1] == 0){ ret[1] = 1; }else{ } } }else{ if(ret[0] == 0){ ret[0] = nums[len-1]+1; ret[1] = nums[len-1]+2; }else{ if(ret[1] == 0){ ret[1] = nums[len-1]+1; }else{ } } } return ret; } }
