leetcode top100 刷题(位运算)

78. 子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/subsets
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个就是代数里面的幂集，首先考虑代数的方法。对于一个有(n)个数的列表，其幂集大小为(2^n)。我们可以采取这样的思路，即首先将这(2^n)个数字在列表中呈现出来，然后再将每个数字按照2进制位数为0或者1映射到子集中去，然后再将子集添加到幂集中。具体考虑映射的时候，我们先将每个数字转化为2进制，随后将二进制数字转化为字符列表，然后反转来补全‘1’，再然后继续再翻转（其实可以去掉这个翻转，不影响结果，纯粹为了数学上好看），然后将原集合映射到子集中去。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        powerset = []
        for i in range(pow(2, len(nums))):
            b = list(bin(i)[2:])
            b.reverse()
            while len(b) < len(nums):
                b.append('0')
            b.reverse()
            subset = []
            for i in range(len(nums)):
                if (b[i] == '1'):
                    subset.append(nums[i])
            powerset.append(subset)
        return(powerset)

看了一下各种题解，发现有各种简单的方法，特别来记录一下。

首先是一种简洁写法的位运算，道理和上述道理一样，但是写的很简洁，如下。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        powerset = []
        for i in range(2**len(nums)):
            sebset = []
            for j in range(len(nums)):
                if i >> j & 1:
                    subset.append(nums[j])
            powerset.append(subset)
        return res

这个比上面简短的地方就在

i >> j & 1

这里。对于数字i，如果他右移j位，末位仍然是1，就说明其倒数第j位本来就是1（从第0位开始计算）。举个例子的话，就比如11，11的二进制为0b1011，那么右移动0位是1011，和1的与运算结果是1，说明其倒数第0位是1。而右移2位的时候是10，10&1=0，那么倒数第二位就是0。与第一个同理，根据1，0的在倒数第j位的有无来判断子集中某个数的有无，但是用位运算简化了操作。

还有一种思路就是迭代，简而言之就是在已有子集中插入新元素，构成2个子集，其中一个有新元素，另一个没有新元素。

要考虑迭代，首先要引入一种列表加法：

>>> [[2]]+[[3]]

得到的结果还是列表

[[2],[3]]

只有基于这种结构，我们才能对这个题目进行迭代，当然迭代复杂度比上面的高很多。

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        powerset = [[]]
        for num in nums:
            powerset = powerset + [[num]+j for j in powerset]
        return(powerset)

这个算法复杂度是(n!)。

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/single-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

考虑其他元素都只出现两次，针对只出现两次的元素有异或运算。异或运算有如下真值表。

异或运算有(A⊕B = (A+B)mod2)。

也就是说异或运算其实就是2整数群(Z_2)中的加法运算，满足交换律，结合律。考虑到位运算中，依然满足结合律交换律。同时群的0元素就是0。所以有(forall A,B,C in Z_2,A⊕0 = 0,A⊕A = 0,A⊕B = B⊕A,A⊕(B⊕C)=(A⊕B)⊕C)。

于是我们可以返回数组中所有元素的逻辑异或值，即为所求。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        a = 0
        for i in nums:
            a = a^i
        return(a)

除此之外还可以用数学方法做，很惭愧，是看了题解发现的官方做法。我们有(2(a+b+c)-(2a+2b+c)=c)，因此我们需要找到(2(a+b+c))。Python中恰好有集合函数，可以实现如下功能：

nums = [1,2,3,1]
print(set(nums))
>>> {1, 2, 3}

于是我们可以在本题中如此操作：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return(2*sum(set(nums))-sum(nums))

这个比上一个使用了额外的空间（集合），因此相对不如上一个。

169. 多数元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:

输入: [3,2,3]
输出: 3
示例 2:

输入: [2,2,1,1,1,2,2]
输出: 2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/majority-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先想到的还是字典，把所有数字和出现次数都用键值对对应起来，然后就完事了。

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = {}
        for i in nums:
            if i not in dic:
                dic[i] = 1
            else:
                dic[i] += 1
        max = 0
        num = 0
        for key in dic:
            if dic[key]>max:
                max = dic[key]
                num = key
        return(num)

然后发现题解的字典方法比我写的简单很多，如下：

class Solution:
    def majorityElement(self, nums):
        counts = collections.Counter(nums)
        return max(counts.keys(), key=counts.get)

发现有一个没见过的函数，即collection函数。

题解中用到了collection.Counter。

这个函数是这样用的

import collections
num = [1,2,3,4,5,6,1,2,3]
dic  = collections.Counter(num)
print(dic)
type(dic)

结果

Counter({1: 2, 2: 2, 3: 2, 4: 1, 5: 1, 6: 1})
collections.Counter

返回对象也是collections.Counter类的，这么一看好像leetcode好像默认引入了很多python的其他库。

然后还可以简化的是字典中找最值的方法。

还是上面的字典，在其中找最大值：

max(dic.keys(), key=dic.get)

或者

max(dic, key=dic.get)

结果

1

所以其实我一开始的回答也可以简化为

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        dic = collections.Counter(nums)
        return(max(dic,key = dic.get))

338. 比特位运算

给定一个非负整数 num。对于 0 ≤ i ≤ num 范围中的每个数字 i ，计算其二进制数中的 1 的数目并将它们作为数组返回。

示例 1:

输入: 2
输出: [0,1,1]
示例 2:

输入: 5
输出: [0,1,1,2,1,2]

进阶

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/counting-bits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

暴力法首当其冲，直接算每个字符2进制中有多少1。

class Solution:
    def countBits(self, num: int) -> List[int]:
        return([sum(1 for q in str(bin(i)) if q == '1') for i in range(num + 1)])

代码确实很短，就是暴力法执行效率太低。

除此我们考虑这道题在位运算下面，于是我们可以看看位运算可以怎么操作一波。

461.汉明距离

两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。

给出两个整数 x 和 y，计算它们之间的汉明距离。

注意：
0 ≤ x, y < 231.

示例:

输入: x = 1, y = 4

输出: 2

解释:
1 (0 0 0 1)
4 (0 1 0 0)
↑ ↑

上面的箭头指出了对应二进制位不同的位置。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hamming-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

开始还是简单粗暴的直接暴力求和。

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        return(sum(1 for i in range(len(str(bin(x^y)))) if (x^y)>>i & 1 == 1))

后来发现看字符串函数发现字符串函数count，可以求其中某个字符数量的多少，比如

'asdasdadfasds'.count('a')

结果：

4

并且bin函数返回的2进制格式也是一个字符串，因此可以直接用

return(bin(x^y).count('1'))

更为简洁。