哎呀我好菜

2020-04-14 21:09 美团_美团平台_系统开发

关注

leetcode高频题笔记之位运算

位运算常见问题

在这里插入图片描述

191.位1的个数

在这里插入图片描述
解法一：
利用x&1返回最低位是否为1，不断的左移1
从最低位一个1开始与，如果不为0计数加1

public class Solution {
    public int hammingWeight(int n) {
        int x = 1;
        int count = 0;
        for (int i = 0; i < 32; i++) {         
            if ((n & x) != 0) {//和某位的一个1进行与操作，如果不为0则存在1，计数+1
                count++;
            }
            x = x << 1;//左移一位
        }
        return count;
    } 
}

解法二：
利用x&(x-1)去掉最后一位1，判断如果去掉最后一位后为0了可以提前结束，去掉了多少次就去掉了多少个0

public class Solution {
    // you need to treat n as an unsigned value
     public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            count++;
            n &= (n - 1);
        }
        return count;
    }
}

231.2的幂

在这里插入图片描述
2的幂值都满足只有一个1
只有一个1的不一定是2的幂值，排除一个数-2147483648 即 Integer.MIN_VALUE,它的二进制是1个1和31个0，1代表符号位

采用x&(x-1)去除掉最低位的1，如果x&(x-1) == 0则只有一个1是2的幂

public class Solution {
    public boolean isPowerOfTwo(int n) {
        return n != 0 && n != Integer.MIN_VALUE && (n & (n - 1)) == 0;
    }
}

342.4的幂

在这里插入图片描述
与2的幂一样，只有一个1，并且这个1的位置是固定的，是偶数位
所以还需要剔除下在奇数位的值
0xaaaaaaaa = 0b10101010101010101010101010101010
只要1的位置全为0，则不符合

public class Solution {
    public boolean isPowerOfFour(int num) {
        return num != 0 && (num & (num - 1)) == 0 && (0xaaaaaaaa & num) == 0;
    }
}

190.颠倒二进制位

在这里插入图片描述
思路：返回结果初始化全0，从最低位开始判断每一位是否为0，如果不为0将返回值的31-i位设置为1

public class Solution {
    public int reverseBits(int n) {
        int x = 1;//用来&操作的变量
        int res = 0;//初始化全0
        for (int i = 0; i < 32; i++) {
            if ((n & x) != 0) {//如果&结果不为0，表明这一位为1，需要将res的31-i位设置为1
                res |= 1 << 31 - i;//或操作使新增的数到指定位置
            }
            x <<= 1;//&操作变量左移一位
        }
        return res;
    }
}

338.比特位计数

在这里插入图片描述
解法一：逐个计数

public class Solution {
    public int[] countBits(int num) {
        int res[] = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            int count = 0;//计数器
            int cur = i;//当前值
            while (cur != 0) {//通过去除尾部1的方式计数
                cur &= (cur - 1);
                count++;
            }
            res[i] = count;
        }
        return res;
    }
}

解法二：动态规划
第i项的值等于去除掉最后一位的值+最后一位和1与的值

public class Solution {
    public int[] countBits(int num) {
        int res[] = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            res[i] = res[i >> 1] + (i & 1);
        }
        return res;
    }
}

解法三：动态规格
第i位的值等于去除掉结尾1后的数量+1

public class Solution {
      public int[] countBits(int num) {
        int res[] = new int[num + 1];
        for (int i = 1; i <= num; i++) {
            res[i] = res[i & (i - 1)] + 1;
        }
        return res;
     }
}

461.汉明距离

在这里插入图片描述

x异或y获得不同的位
用x&(x-1)去除尾部1统计1个数

public class Solution {
    public int hammingDistance(int x, int y) {
        int z = x ^ y;
        int count = 0;
        while (z != 0) {
            z &= (z - 1);
            count++;
        }
        return count;
    }
}

136.只出现一次的数字

在这里插入图片描述

如果两个数相同，异或结果为0
将所有的数异或，剩下的就是单出来的数

public class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res ^= nums[i];
        }
        return res;
    }
}

260.只出现一次的数字III

在这里插入图片描述
因为存在两个不一样的，简单的异或完了肯定不行
首先异或下找到两个只出现一次的数字的异或，这两个数字至少有一位不一样，也就是说异或结果至少有一个1
通过diff&=-diff获取最右侧的那个1，以那个位是否为1将整个数组的数分成两堆，一堆那个位置为1，另一堆那个位置为0，那么从两堆中就可以找出这两个数了

public class Solution {
    public int[] singleNumber(int[] nums) {
        int diff = 0;
        for (int num : nums) diff ^= num;//得到两个值的异或

        diff &= -diff;//获得两个只出现一次的数字最右边不同的那一位数
        int[] res = new int[2];
        for (int num : nums) {
            if ((num & diff) == 0) res[0] ^= num;//第一堆，最右侧异或为1位位1
            else res[1] ^= num;//第二堆
        }
        return res;
    }
}

268.缺失数字

在这里插入图片描述
已知两个相同的数异或的结果为0
为了找出0-n中丢失的数字，将0-n中的已知n个数字和0-n进行异或，就转换成找只出现一次数字问题。

public class Solution {
    public int missingNumber(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res = res ^ i ^ nums[i];
        }
        return res ^ nums.length;
    }
}

面试题16.01.交换数字

在这里插入图片描述
非常容易想到，利用a=a+b;b=a;a=a-b可以完成，但是需要考虑越界
用异或实现就不需要考虑边界问题

a = a ^ b ^b ;
b = b ^ a ^a;

转化为代码就是

public class Solution {
    public int[] swapNumbers(int[] numbers) {
        numbers[0] = numbers[0] ^ numbers[1];//a = a^b
        numbers[1] = numbers[0] ^ numbers[1];//b = a^b^b = a
        numbers[0] = numbers[0] ^ numbers[1];//a = a^b^a^b^b = b
        return numbers;
    }
}

693.交替位二进制数

在这里插入图片描述

将n右移一位后与n进行异或操作，a = n&(n>>1)
如1010右移为101，异或得1111
如1011右移为101，异或得1110
为了判定a是否为全1，另flag = a&(a-1)
如1111加一为10000，与操作为0
如1110加一位1111，与操作为1110！=0

通过上面两步就可以判断一个数是否满足了

public class Solution {
    public boolean hasAlternatingBits(int n) {
        int a = n ^ (n >> 1);
        return (a & (a + 1)) == 0;
    }
}

476.数字的补数

在这里插入图片描述
求补数就是将有效的0和1进行互换，所以只需要一个和num位数相同全1的数进行异或运算就可以了
问题转换成求一个与num位数相同的全1的数

首先，获得数mask ：01000000000000000000000000000000（mask = 1 << 30）
将 mask与num进行与操作，如果为0一直右移
当num月mask与不为0是，mark的1所在的位置就是num的最高位的位置
mask左移1位-1得到从mask位开始的全1值
全1与num异或得补数
举例：
1101010
mark = 1000000
(mark<1)-1 = 1111111
1111111^1101010 = 0010101

class Solution {
    public int findComplement(int num) {
        if (num == 0) return 1;
        int mask = 1 << 30;//不考虑符号位，就移动到最大位
        while ((mask & num) == 0) mask >>= 1;
        mask = (mask << 1) - 1;
        return mask ^ num;
    }
}

371.两整数之和

在这里插入图片描述
不进位加法a^b
进位数计算（a&b）<<1
举例：计算12+7
12:1100
7:0111

12^7 = 1011
(12&7)<<1 = 1000

第一轮循环得到以上两个结果，递归调用，求1011+1000

1011^1000 = 0011
(1011&1000)<<1 = 10011

第二轮循环得以上两个结果，递归调用，求0011+10011

00011^10011 = 10000
(00011&10011)<<1 = 00011

第二轮循环得以上两个结果，递归调用，求10000+00011

10000^00011 = 10011
(10000&00011)<<1 = 0

return 10011 获得结果

迭代代码

public class Solution {
    public int getSum(int a, int b) {
        while (b != 0) {
            //不进位加法
            int tmp = a ^ b;
            //计算进位值
            int carry = (a & b) << 1;
            a = tmp;
            b = carry;
        }
        return a;
    }
}

递归代码：

public class Solution {
    public int getSum(int a, int b) {
        return b != 0 ? getSum(a ^ b, (a & b) << 1) : a;
    }
}

318.最大单词长度乘积

在这里插入图片描述

用二进制的一位表示某一个字母是否出现过，0表示没出现，1表示出现。

"abcd"二进制表示00000000 00000000 00000000 00001111

"bc"二进制表示00000000 00000000 00000000 00000110。

当两个字符串没有相同的字母时，二进制数与的结果为0。

public class Solution {
    public int maxProduct(String[] words) {
        int wordsLen = words.length;
        int compare[] = new int[wordsLen];
        //将字符串映射到位
        for (int i = 0; i < wordsLen; i++) {
            for (char c : words[i].toCharArray()) {
                compare[i] |= 1 << (c - 'a');
            }
        }
        //搜索完全不相同的两个串
        int maxres = 0;
        for (int i = 0; i < wordsLen; i++) {
            for (int j = i + 1; j < wordsLen; j++) {
                if ((compare[i] & compare[j]) == 0) {
                    maxres = Math.max(maxres, words[i].length() * words[j].length());
                }
            }
        }
        return maxres;
    }
}

leetcode分类题集文章被收录于专栏

按知识点分类整理leetcode的题目和解法