成都建网站公司电话,创办公司的基本流程,网站备案需要准备哪些资料,体育彩票网站开发该做哪些步骤子集
[78]子集I
题目描述
给你一个整数数组 nums #xff0c;数组中的元素 互不相同 。返回该数组所有可能的子集#xff08;幂集#xff09;。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例输入
示例 1#xff1a; 输入#xff1a;nums [1, 2, 3…子集
[78]子集I
题目描述
给你一个整数数组 nums 数组中的元素 互不相同 。返回该数组所有可能的子集幂集。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例输入
示例 1 输入nums [1, 2, 3] 输出[[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]] 示例 2 输入nums [0] 输出[[], [0]] 题解
这道题目考察的是如何获取一个数组的幂集核心思想是幂运算。
public ListListInteger subsets(int[] nums) {ListListInteger ans new ArrayList();int n nums.length;for (int i 0; i (1 n); i) {ListInteger subset new ArrayList();for (int j 0; j n; j) {if ((i (1 j)) ! 0) {subset.add(nums[j]);}}ans.add(subset);}return ans;
}这段代码难点在于第7行的条件判断不容易想到下面解释一下
i 是从 0 到 2^n - 1 的整数它的二进制表示中每一位对应着一个元素是否包含在子集中。例如 i 0 时二进制是 000表示空集[]。 i 1 时二进制是 001表示只包含第 0 个元素[1]。 i 2 时二进制是 010表示只包含第 1 个元素[2]。 i 3 时二进制是 011表示包含第 0 个和第 1 个元素[1,2]。 i 4时二进制是 100表示只包含第二个元素 [3]。 i 5时二进制是 101表示包含第 0 个和第 2 个元素[1,3]。 i 6时二进制是 110表示包含第 1 个和第 2 个元素[2,3])。 i 7时二进制是 111表示包含所有元素 ([1,2,3]) 观察上面我们就能看出来遇到二进制是 1 的情况就把那个元素加到一个子列表里面。
我们判断i的第j位是不是 1可以用位运算实现i (1 j)) ! 0
[90]子集II
题目描述
给你一个整数数组 nums 其中可能包含重复元素请你返回该数组所有可能的 子集幂集。
解集 不能 包含重复的子集。返回的解集中子集可以按 任意顺序 排列。
示例输入
示例 1 输入nums [1, 2, 2] 输出[[], [1], [1, 2], [2], [2, 2], [1, 2, 2]] 示例 2 输入nums [0] 输出[[], [0]] 题解
和上面相比就是增加了对重复元素的检查如果重复就不要加入最终要返回的列表了。
需要注意的是题目中像[1, 2]和[2, 1]认为是相同的所以对subset要排个序再检查。
public ListListInteger subsetsWithDup(int[] nums) {ListListInteger ans new ArrayList();int n nums.length;for (int i 0; i (1 n); i) {ListInteger subset new ArrayList();for (int j 0; j n; j) {if ((i (1 j)) ! 0) {subset.add(nums[j]);}}subset.sort(Comparator.naturalOrder());if (! ans.contains(subset)) {ans.add(subset);}}return ans;
}但这个方法比较耗时间可以接着想怎么通过位运算改进他。
比如我们看这个 nums [1, 2, 2]
1 2 20 0 0 []
0 0 1 [1]
0 1 0 [2]
0 1 1 [1, 2]
1 0 0 [2]
1 0 1 [2, 1]
1 1 0 [2, 2]
1 1 1 [1, 2, 2]我们注意到
[2]这个子集出现了两次对应的是
0 1 0 [2]
1 0 0 [2][1, 2]这个子集也出现了两次对应的是
0 1 1 [1, 2]
1 0 1 [2, 1]那么怎么去重复呢
有两种情况
第一种就是占据了开头类似于这种 101
第二种就是没有占据开头类似于这种 0100对应 [2]这个子集
除了第一位其他位的 1 的前边一定是 0。
所以的话我们的条件是看出现了重复数字并且当前位是 1 的前一个的二进位。
public ListListInteger subsetsWithDup(int[] num) {Arrays.sort(num);ListListInteger lists new ArrayList();int subsetNum 1 num.length;for (int i 0; i subsetNum; i) {ListInteger list new ArrayList();boolean illegal false;for (int j 0; j num.length; j) {//当前位是 1if ((i j 1) 1) {//当前是重复数字并且前一位是 0跳过这种情况if (j 0 num[j] num[j - 1] (i (j - 1) 1) 0) {illegal true;break;} else {list.add(num[j]);}}}if (! illegal) {lists.add(list);}}return lists;}
