|
今天是小浩算法 “365刷题计划” 第105天。这是昨天一个同学面试快手被问到的算法题，很不幸的是他被挂掉了。征得对方同意后，拿出来分享给大家~ （如果要进入算法交流群的， 关注后回复进群就可以了） 01 PART 子集 子集：如果集合A的任意一个元素都是集合B的元素，那么集合A称为集合B的子集。 第48题：给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。 说明：解集不能包含重复的子集 示例: 输入: nums = [1,2,3] 输出: [ [3], [1], [2], [1,2,3], [1,3], [2,3], [1,2], [] ] 题目本身没有太多需要补充的，初中数学知识： 02 PART 题解分析（吊） 上一个很厉害的题解。 首先我们可以证明一下 N 个元素的子集个数有 2^N 个： 可以类比为 N 个不同的小球，一次拿出若干个小球（可以不拿），对于每一个球都可以选择拿或者不拿，共有 N 个球，总共判断 N 次，产生了 2^N 个子集。比如：123，共有下面 8 个子集： 然后考虑解题思路，暂且不谈回溯，我们其实可以用二进制来模拟每个元素是否选中的状态。又因为我们已知了对于 N 个元素共有 2^N 个子集，所以我们直接遍历 2^N 个元素。 1class Solution {2 public List<List<Integer>> subsets(int[] nums) {3 //存放所有子集4 List<List<Integer>> res = new ArrayList<>();5 //子集总数共有 2^N 个6 int length = 1 << nums.length;7 //遍历所有的子集8 for (int i = 0; i < length; i++) {9 List<Integer> sub = new ArrayList<>();10 //TODO ： 找到对应的子集元素11 }12 return res;13 }14}
但是我们并不知道具体的子集元素。那如何找到对应的子集元素呢？对于 2^N 个 N 位的二进制数，我们可以通过从后往前的第 j 个二进制位的 0 和 1 来表示是否放入子集集合。 1for (int j = 0; j < nums.length; j++) {2 if (((i >> j) & 1) == 1) sub.add(nums[j]);3}
综合一下代码： 1class Solution {2 public List<List<Integer>> subsets(int[] nums) {3 //存放所有子集4 List<List<Integer>> res = new ArrayList<>();5 //子集总数公有 2^N 个6 int length = 1 << nums.length;7 //遍历所有的子集8 for (int i = 0; i < length; i++) {9 List<Integer> sub = new ArrayList<>();10 for (int j = 0; j < nums.length; j++) {11 if (((i >> j) & 1) == 1) sub.add(nums[j]);12 }13 res.add(sub);14 }15 return res;16 }17}
为帮助大家理解，假设 nums 为 [1,2,3]，res 的存储过程为： 大家可以仔细体会一下这个题解。 03 PART 题解分析（普通） 当然，上面的题解并不是凡人可以直接想到的。所以我们这里还是给出一种更为通用的题解~ 集合中所有元素的选/不选，其实构成了一个满二叉树。左子树选，右子树不选。自然，那从根节点到所有叶子节点的路径，就构成了所有的子集。 （旋转90°） 那这种解法其实就好理解很多了： 1class Solution {23 List<List<Integer>> res;45 public List<List<Integer>> subsets(int[] nums) {6 res = new ArrayList<>();7 List<Integer> list = new ArrayList<>();8 dfs(nums, 0, list);9 return res;10 }1112 private void dfs(int[] nums, int start, List<Integer> list) {13 for (int i = start; i < nums.length; i++) {14 list.add(nums[i]);15 dfs(nums, i + 1, list);16 list.remove(list.size() - 1);17 }18 res.add(new ArrayList<>(list));19 }2021}
如果对这种解法也不理解，可以看下我之前的二叉树系列： 总之，这道题目其实还是有一定难度的，难点主要包括：
但并不是不可以攻克，建议大家下去自行练习一番~ 加油，奥利给！
如果你也想加入我们每日刷题 扫码，回复【进群】就可以啦。 推荐几篇必看文章： 漫画：呕心泣血算法指导篇（真正的干货，怒怼那些说算法没用的人）
彩蛋： 1//py2class Solution:3 def subsets(self, nums: List[int]) -> List[List[int]]:4 arr = [[]]5 for i in nums:6 arr+=[j+[i] for j in arr]7 return arr
（艾玛，我什么都不知道） |
|
|
