今天是 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):
- Windows = list(range(1, k+1)) + [n+1]
- j = 0
- while j <k:
- cur = []
- for i in range(k):
- cur.append(nums[Windows[i] - 1])
- ret.append(cur[:])
- j = 0
- while j < k and Windows[j+1] == Windows[j] + 1:
- Windows[j] = j + 1
- j += 1
- Windows[j] += 1
- # 手动添加空集
- ret = [[]]
- n = len(nums)
- # 遍历 k 从 1 到 n
- for i in range(1, n+1):
- combine(n, i, ret)
- return ret
二进制组合
照搬上一题的解法固然是可行的, 但是这么做完全没有必要, 也得不到任何收获. 所以我们应该想一下新的解法.
既然这道题让我们求的是所有的子集, 那么我们可以从子集的特点入手. 我们之前学过, 一个含有 n 个元素的子集的数量是 . 这个很容易想明白, 因为 n 个元素, 每个元素都有两个状态, 选或者不选. 并且这 n 个元素互相独立, 也就是说某个元素选或者不选并不会影响其他的元素, 所以我们可以知道一共会有 种可能.
我们也可以从组合数入手, 我们令所有子集的数量为 S, 那么根据上面我们用组合求解的解法, 可以得到:
两者的结果是一样的, 说明这个结论一定是正确的.
不知道大家看到 n 个元素, 每个元素有两个取值有什么想法, 如果做过的题目数量够多的话, 应该能很快联想到二进制. 因为在二进制当中, 每一个二进制位就只有 0 和 1 两种取值. 那么我们就可以用 n 位的二进制数来表示 n 个元素集合取舍的状态. 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 出题人出题都是有套路的, 往往出了一道题之后, 为了提升题目数量(凑提数), 都会在之前题目的基础上做变形, 变成一道新题. 所以如果你按照顺序刷题的话, 会很明显地发现这一点. 如果你从这个角度出发去思考的话, 不但能理解题目之间的联系, 还能揣摩出出题人的用意, 这也是一件很有趣的事情.
如果喜欢本文, 可以的话, 请点个关注, 给我一点鼓励, 也方便获取更多文章.
本文使用 https://mdnice.com/ 排版
来源: https://www.cnblogs.com/techflow/p/13151068.html