Leetcode 78. 子集
程序员文章站
2022-04-04 11:14:45
...
Leetcode 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
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
位运算
其实嘛,取子集这件事情,对每一个元素就两种状态,取和不取,共有 种可能。这可以直接用一个二进制 bit (boolean)位向量表示:
nums = [1, 2, 3]
幂集 = [
[],
[1],
[2],
[1,2],
[3],
[1,3],
[2,3],
[1,2,3]
]
# 0 表示不取
# 1 表示取
对应取的状态 = [
[0, 0, 0],
[0, 0, 1],
[0, 1, 0],
[0, 1, 1],
[1, 0, 0],
[1, 0, 1],
[1, 1, 0],
[1, 1, 1]
]
可以看到,所有对应取的状态合在一起,其实就是遍历了 len(nums)
位的二进制位向量所有可能的取值。如果用整数表示二进制位向量,即遍历 [0, 1 << len(nums) - 1]
。这样实现起来很简单了,跑一个循环就行:
for i := 0; i < 1 << len(nums); i++ {
// ...
}
在这个遍历里,把二进制位向量映射到原数组的索引,就能取出一个子集了:
s := []int{}
for j, ii := 0, i; j < len(nums); j, ii = j+1, ii>>1 {
// 这个 for 其实就是每次从低位端 pop 一个位出来,这个位对应一个索引嘛
// pop 出的是 1 就取这个索引处的元素进子集
if ii & 1 == 1 {
s = append(s, nums[j])
}
}
合在一起,就有了完整的 Golang 实现:
func subsets(nums []int) [][]int {
subs := [][]int{}
for i := 0; i < 1 << len(nums); i++ {
s := []int{}
for j, ii := 0, i; j < len(nums); j, ii = j+1, ii>>1 {
if ii & 1 == 1 {
s = append(s, nums[j])
}
}
subs = append(subs, s)
}
return subs
}
啊,我写不清这个,,,我觉得二进制、位运算这种东西相当自然,就像我们算 1 + 1 很自然就得到了 2,用二进制位向量是一种很自然的事,它就该这么用,所有反倒难以解释了????
也许这不是一个很好的思路,但从结果上来看,这个算法还是比较快的:
上一篇: [leetcode]78. 子集
下一篇: 看来是蛮大的,已经影响智力了
推荐阅读
-
python 生成list的所有的子集 (不使用递归且不引入标准库)
-
Leetcode算法【114. 二叉树展开为链表】
-
LeetCode 50. Pow(x, n)
-
[leetcode]不同路径三连击~
-
LeetCode——Department Highest Salary(花式使用IN以及GROUP BY)
-
LeetCode——Department Top Three Salaries(巧妙使用子查询)
-
LeetCode——Customers Who Never Order(灵活使用NOT IN以及IN)
-
leetcode 921. 使括号有效的最少添加(Python)
-
#leetcode刷题之路13-罗马数字转整数
-
#leetcode刷题之路48-旋转图像