LeetCode78面试常用小技巧（LeetCode78面试常用小技巧）

今天是LeetCode专题第47篇文章，我们一起来看下LeetCode的第78题Subsets（子集），我来为大家科普一下关于LeetCode78面试常用小技巧?下面希望有你要的答案，我们一起来看看吧!

LeetCode78面试常用小技巧

今天是LeetCode专题第47篇文章，我们一起来看下LeetCode的第78题Subsets（子集）。

这题的官方难度是Medium，点赞3489，反对79，通过率59.9%。从这个数据我们也可以看得出来，这是一道难度不是很大，但是质量很高的题。的确，在这道题的解法当中，你会学到一种新的技巧。

废话不多说，我们先来看题意。

题意

这题的题意非常简单，和上一题有的一拼，基本上从标题就能猜到题目的意思。给定一个没有重复元素的int型数组，要求返回所有的子集，要求子集当中没有重复项，每一项当中也没有重复的元素。

样例

Input: nums = [1,2,3] Output: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ]

照搬上题

刚拿到手可能有点蒙，但是稍微想一下就会发现，这一题和上题非常接近，两者唯一的不同就是，子集没有数量的限制，从空集开始，一直到它本身结束，不论多少个元素都可以。而上一题要求的是有数量限制的，也就是说上一题我们求的其实是限定了k个元素的子集。

想明白这点就简单了，显然我们可以复用上一题的算法，我们来遍历这个k，从0到n，就可以获得所有的子集了。只要你上一题做出来了，那么这题几乎没有任何难度。如果你没有看过上一题的文章的话，可以通过传送门回顾一下：

LeetCode 77，组合挑战，你能想出不用递归的解法吗？

我们直接来看代码：

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: # 上一题求解k个组合的解法 def combine(n, k, ret): window = list(range(1, k 1)) [n 1] j = 0 while j < k: cur = [] for i in range(k): cur.append(nums[window[i] - 1]) ret.append(cur[:]) j = 0 while j < k and window[j 1] == window[j] 1: window[j] = j 1 j = 1 window[j] = 1 # 手动添加空集 ret = [[]] n = len(nums) # 遍历k从1到n for i in range(1, n 1): combine(n, i, ret) return ret

二进制组合

照搬上一题的解法固然是可行的，但是这么做完全没有必要，也得不到任何收获。所以我们应该想一下新的解法。

既然这道题让我们求的是所有的子集，那么我们可以从子集的特点入手。我们之前学过，一个含有n个元素的子集的数量是2^n。这个很容易想明白，因为n个元素，每个元素都有两个状态，选或者不选。并且这n个元素互相独立，也就是说某个元素选或者不选并不会影响其他的元素，所以我们可以知道一共会有2^n种可能。

我们也可以从组合数入手，我们令所有子集的数量为S，那么根据上面我们用组合求解的解法，可以得到：

S = C_n^0 C_n^1 ... C_n^n = 2^n

两者的结果是一样的，说明这个结论一定是正确的。

不知道大家看到n个元素，每个元素有两个取值有什么想法，如果做过的题目数量够多的话，应该能很快联想到二进制。因为在二进制当中，每一个二进制位就只有0和1两种取值。那么我们就可以用n位的二进制数来表示n个元素集合取舍的状态。n位二进制数的取值范围是[0, 2^n)，所以我们用一重循环去遍历它，就相当于一重循环遍历了整个集合所有的状态。

这种技巧我们也曾经在动态规划状态压缩的文章当中提到过，并且在很多题目当中都会用到。所以建议大家可以了解一下，说不定什么时候面试就用上了。

根据这个技巧， 我们来实现代码就非常简单了。

class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: ret = [] n = len(nums) # 遍历所有的状态 # 1左移n位相当于2的n次方 for s in range(1 << n): cur = [] # 通过位运算找到每一位是0还是1 for i in range(n): # 判断s状态在2的i次方上，也就是第i位上是0还是1 if s & (1 << i): cur.append(nums[i]) ret.append(cur[:]) return ret

从代码来看明显比上面的解法短得多，实际上运行的速度也更快，因为我们去掉了所有多余的操作，我们遍历的每一个状态都是正确的，也不用考虑重复元素的问题。

总结

不知道大家看完文章都有一些什么感悟，可能第一种感悟就是LeetCode应该按照顺序刷吧XD。

的确如此，LeetCode出题人出题都是有套路的，往往出了一道题之后，为了提升题目数量（凑提数），都会在之前题目的基础上做变形，变成一道新题。所以如果你按照顺序刷题的话，会很明显地发现这一点。如果你从这个角度出发去思考的话，不但能理解题目之间的联系，还能揣摩出出题人的用意，这也是一件很有趣的事情。

如果喜欢本文，可以的话，请点个关注，给我一点鼓励，也方便获取更多文章。

本文始发于公众号：TechFlow

,