leetCode-hot100-位运算专题

例题中的视频讲解是B站中的宝藏博主的讲解视频，每道题后面都附有该题对应的视频链接~

1.异或

参考资料：位运算-异或，以下知识点讲解的内容参考了该篇博文，有兴趣的伙伴可以去看看，讲的很详细。在知识点的后面加入了该知识点相关的例题，所有的例题都来自力扣-hot100，按照题号搜索题目即可。
概念：
按位异或表示当两个二进制当前位相同则值为0，不同则为1
特点（重要！）：
（1）0 异或 任何数 = 任何数（0^0=0,0^1=1）
（2）1 异或 任何数 = 任何数取反 （1^0=1,1^1=0）
（3）任何数 异或 自己 = 把自己置为0
常见用途：
（1）实现特定位置的翻转
要将某个二进制数字的特定位置取反，可以让其与同位数的二进制数字异或，该二进制除了对应的特定位置为1，其他位置都为0（eg，将01011101的第2位和第3位取反，则可以与00000110异或）
（2）在不使用临时变量的情况下将两个数的值进行交换（a：10110110和b：00001101）

a = a ^ b
b = b ^ a
a = a ^ b
1
2
3

例题：
136.只出现一次的数字
思路：
本题用到了异或运算特点中（2）和（3）：

• 任何数异或自身等于把自己置为0 ->我们将数组中的所有元素异或，那么出现两次的元素全部变为0
• 0异或任何数等于任何数 ->经过上个步骤的处理，数组中只有0和只出现一次的数字，异或后即可得到该元素。

视频讲解点击视频讲解-只出现一次的数字。
时间复杂度：
时间复杂度为O(n)，n为数组的长度。
代码实现：

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i = 0; i < nums.length;i++){
            ans = ans ^ nums[i];
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

268.丢失的数字
思路：
本题和136题是相同的，将0~n的所有数字和数组元素异或，最后的结果即为结果，这里ans初始值设置为n，因为在循环中不包含n，数组的长度是n-1。
时间复杂度：
时间复杂度为O(n)，n为数组的长度。
代码实现：

class Solution {
    public int missingNumber(int[] nums) {
        int ans = nums.length;
        for(int i = 0; i < nums.length; i++){
            ans ^= nums[i] ^ i;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

389.找不同
思路：
本题的思路和268题类似，由于两个相同字符异或结果为 0，则 s 与 t 的全部字符异或之后就是 t 中添加的字符。其中由于 t 的长度比 s 大1，所以答案的初始值设置为 t 的最后一个字符。
时间复杂度：
时间复杂度为O(n)，其中n为字符串s的长度。
代码实现：

class Solution {
    public char findTheDifference(String s, String t) {
        char c = t.charAt(t.length() - 1);
        for(int i = 0; i < s.length(); i++){
            c ^= s.charAt(i) ^ t.charAt(i);
        }
        return c;
    }
}
1
2
3
4
5
6
7
8
9

2.与运算和或运算

与运算和或运算比较简单，这里简单介绍一下
概念：
与运算（&）：两者都为1时结果为1，其余情况为0
或运算（|） ：两者中有一个为1时结果为1，其余情况为0
使用场景：
（1） n & (n - 1)：用来判断一个数是否为2的幂，如果结果为0，则说明 n 是2的幂，否则不是，同时还可以统计一个数的二进制表示中有多少个1。
原理分析：
这个操作的原理是，对于一个2的幂，其二进制表示只有一个1，其余位都为0。而对于 n-1，其二进制表示中的最高位为0，其余位都为1。所以，当 n 和 n-1 进行按位与操作时，如果结果为0，则说明 n 是2的幂，否则不是（eg. 8(1000) 和7(0111)按位与，结果为0，说明8的2
的幂）。
…待完善
例题：
231.2的幂
思路：
本题使用到的是使用场景中的（1）可以直接解决，需要注意的是0和负数不可能是2的幂，所以需要返回false。
时间复杂度：
时间复杂度为O(1)，无论输入的n是多少，代码都只需要执行一次位运算操作即可判断n是否为2的幂次。
代码实现：

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}
1
2
3
4
5

3.左移和右移

概念：
左移运算符m<<n表示吧m左移n位。左移n位的时候，最左边的n位将被丢弃，同时在最右边补上n个0。
右移运算符m>>n表示把m右移n位。右移n位的时候，最右边的n位将被丢弃。但右移时处理最左边位的情形要稍微复杂一点。这里要特别注意，如果数字是一个无符号数值，则用0填补最左边的n位。如果数字是一个有符号数值，则用数字的符号位填补最左边的n位。也就是说如果数字原先是一个正数，则右移之后再最左边补n个0；如果数字原先是负数，则右移之后在最左边补n个1。
使用场景：
（1）获取x的第k位：(x >> k) & 1
（2）将1或0添加到x的最后一位 ：(x << 1) | 1或0
例题：
190.颠倒二进制位
思路：
使用左移和右移运算使用场景的（1）和（2），使用(n >> k) & 1取到n的第k位置，使用(x << 1) | 1或0将取到的第k位依次添加到答案中，视频讲解点击视频讲解-颠倒二进制位。
时间复杂度：
时间复杂度为O(1)，即常数时间复杂度。无论输入的n是多少，代码都需要执行32次循环。
代码实现：

public class Solution {
    // you need treat n as an unsigned value
    public int reverseBits(int n) {
        int ans = 0;
        for(int i = 0 ; i < 32; i++){
            ans = (ans << 1) | ((n >> i) & 1);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10

191.位1的个数
思路1：
通过右移依次得到n的每一位，然后和1做与运算，如果为1则结果+1，反之+0，最后处理完n后即可得到结果值，视频讲解点击视频讲解-位1的个数。
时间复杂度：
时间复杂度是O(1)，因为循环次数固定为32次。
代码实现：

class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            ans += (n >> i) & 1;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9

思路2：
使用与运算中的使用场景中的第（1） n & (n - 1)：统计一个数的二进制表示中有多少个1，每次执行 n & (n - 1)时都会消去n中的一位1，ans++，当n为0时及n中的1被全部消掉，此时ans即为所求。
时间复杂度：
时间复杂度为O(logn)，其中n表示给定的整数n的位数。代码中的while循环会执行的次数取决于n的二进制表示中1的个数，而一个整数n的二进制表示中1的个数最多为logn，因此时间复杂度为O(logn)。
代码实现：

class Solution {
    public int hammingWeight(int n) {
        int ans = 0;
         while (n > 0) {
            n &= (n - 1);
            ans++;
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10

4.综合例题

318.最大单词长度乘积
思路：
本题使用位运算的思想来判断两个字符串是否包含相同的字符。首先，创建一个大小与words数组长度相同的整数数组bitWords。然后，遍历words数组，将每个字符串转换为一个整数，用于表示该字符串包含的字符。具体地，对于每个字符串，将其中的每个字符与'a'做差，然后将结果作为二进制位的索引，将相应的位设置为1。这样，整数bitWords[i]就表示了words[i]字符串包含的字符。
接下来，使用两层循环遍历所有的字符串对，并通过位运算判断它们是否包含相同的字符。具体地，计算两个字符串长度的乘积，并将乘积与ans进行比较，更新ans的值。当且仅当两个字符串对应的整数按位与的结果为0时，说明它们不包含相同的字符。最后，返回ans作为结果。
时间复杂度：
时间复杂度为O(n^2 * m)，其中n是words数组的长度，m是单词的平均长度。
代码实现：

class Solution {
    public int maxProduct(String[] words) {
        int[] bitWords = new int[words.length];
        for(int i = 0; i < words.length; i++){
            bitWords[i] = 0;
            for(int j = 0;j < words[i].length(); j++){
                bitWords[i] |= 1 << (words[i].charAt(j) - 'a'); 
            }
        }
        int ans = 0;
        for(int i = 0;i < words.length;i++){
            for(int j = i;j < words.length;j++){
                int temp = words[i].length() * words[j].length();
                if((bitWords[i] & bitWords[j]) == 0) {
                    ans = Math.max(temp,ans);
                }
            }
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

78.子集
思路2：二进制法
由于数组中无重复元素，那么我们可以用二进制的位数来表示数组中的元素（n个元素即二进制为2^n，它的子集有2^n个），我们知道二进制是0和1的组合，当某一位为1时说明该位置对应的元素被选择了，由于二进制包含所有的组合，所以将0-2^n中所有的二进制数按照上述规则对应成子集，每一个二进制数字对应一个子集（对应位置为0即不选择，对应位置为1即选择），则可以得到子集的全集，视频讲解点击视频讲解-子集，视频中有详细的模拟举例。
时间复杂度：
这段代码的时间复杂度为O(2^n * n)，其中n为数组nums的长度。这是因为对于nums数组的每个元素，都有可能在子集中存在或不存在，所以一共有2^n种可能的子集组合，并且在每一种可能中，需要花费O(n)的时间来生成子集。因此，整体的时间复杂度为O(2^n * n)。
代码实现：

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int n = nums.length;
        for(int mask = 0;mask < (1 << n); mask++){
            List<Integer> subset = new ArrayList<>();
            for(int i = 0; i < n; i++){
                //(mask & (1 << i)) != 0表示索引为i的位置对应的mask二进制为1，所以将nums[i]加进subset
                if((mask & (1 << i)) != 0) subset.add(nums[i]);
            }
            ans.add(new ArrayList<>(subset));
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在LeetCode-hot100题解—Day7中还介绍了深度优先遍历的解决方法，相比于上述解法更加高效一点。
137.只出现一次的数字 Ⅱ
思路：
使用位运算来统计每个位上数字出现的次数，然后根据出现次数是否为3的倍数来确定只出现一次的数字在该位上的值。最后，将每个位上的值组合起来就得到了只出现一次的数字。简单来说，就是将每个数组元素用二进制表示，然后算出每个数组元素对应位置上1的总数，如果这个数字出现了三次，那么该位的1的个数是3的倍数，如果不是3的倍数，则将该位设置到结果中，举个栗子：

时间复杂度：
时间复杂度为O(n)，其中n是数组的长度。
代码实现：

class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for(int i = 0; i < 32;i++){
            int cnt = 0;
            for(int num : nums){
                cnt += (num >> i) & 1;
            }
            if(cnt % 3 != 0) ans |= (1 << i);
        }
        return ans;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

重要：在使用位运算的时候一定要注意运算符的优先级，该加括号的地方一定不能漏加，下面是个举例：

//错误
if(mask & (1 << i) != 0)
//正确
if((mask & (1 << i)) != 0)
1
2
3
4