原题链接:http://oj.leetcode.com/problems/subsets-ii/
这道题跟Subsets一样是经典的NP问题--求子集。比Subsets稍微复杂一些的是这里的集合中可能出现重复元素,因此我们在求子集的时候要避免出现重复的子集。在Subsets中我们每次加进一个元素就会把原来的子集都加上这个元素,然后再加入到结果集中,但是这样重复的元素就会产生重复的子集。为了避免这样的重复,需要用个小技巧。
其实比较简单,就是每当遇到重复元素的时候我们就只把当前结果集的后半部分加上当前元素加入到结果集中,因为后半部分就是上一步中加入这个元素的所有子集,上一步这个元素已经加入过了,前半部分如果再加就会出现重复。所以算法上复杂度上没有提高,反而少了一些操作,就是遇到重复时少做一半,不过这里要对元素集合先排序,否则不好判断重复元素。同样的还是可以用递归和非递归来解,不过对于重复元素的处理是一样的。递归的代码如下:public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
if(num == null)
return null;
Arrays.sort(num);
ArrayList<Integer> lastSize = new ArrayList<Integer>();
lastSize.add(0);
return helper(num, num.length-1, lastSize);
}
private ArrayList<ArrayList<Integer>> helper(int[] num, int index, ArrayList<Integer> lastSize)
{
if(index == -1)
{
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> elem = new ArrayList<Integer>();
res.add(elem);
return res;
}
ArrayList<ArrayList<Integer>> res = helper(num,index-1,lastSize);
int size = res.size();
int start = 0;
if(index>0 && num[index]==num[index-1])
start = lastSize.get(0);
for(int i=start;i<size;i++)
{
ArrayList<Integer> elem = new ArrayList<Integer>(res.get(i));
elem.add(num[index]);
res.add(elem);
}
lastSize.set(0,size);
return res;
}
非递归的代码如下:public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
res.add(new ArrayList<Integer>());
if(num==null || num.length==0)
return res;
Arrays.sort(num);
int start = 0;
for(int i=0;i<num.length;i++)
{
int size = res.size();
for(int j=start;j<size;j++)
{
ArrayList<Integer> newItem = new ArrayList<Integer>(res.get(j));
newItem.add(num[i]);
res.add(newItem);
}
if(i<num.length-1 && num[i]==num[i+1])
{
start = size;
}
else
{
start = 0;
}
}
return res;
}
这种NP问题的重复处理在LeetCode有一定出现频率,比如还有Permutations
II也是这样的,其实本质就是当一个重复元素进来时忽略上一个元素已经有的结果,只考虑由重复元素所产生的新结果。
分享到:
相关推荐
subsets: 78 - permutation - combination sum: 39, 40, 216 - palindrome partitioning - regex - sudoku solver: 37 排序 - merge sort - quick sort - insertion sort - selection sort - counting sort 位操作 -...
leetcode写题闪退 #*的多少代表此题的有意思程度 有几题第一次写的时候思绪比较混乱: *****Regular Expression Matching 2014.10.29 对于Find Minimum in Rotated Sorted Array II 和 Find Minimum in Rotated ...
leetcode 1004 leetcode 题目分类 数组 哈希表 链表 堆 栈 队列 字符串 树 Trie BST 图 最小(大)堆 Two Points 滑动窗口 递归 回溯 动态规划 排序 拓扑排序 二分查找 数学 深度优先搜索 ...Subsets
此应用程序使用递归回溯的概念打印字符串的所有子集。 基本上,在这段代码中,我维护了一个数组,其中包含 0 和 1 的所有可能组合。 并且数组的长度等于字符串的长度。 现在,考虑到对于子集,要么选择字母,要么不...
leetcode安卓The_LeetCode_Awakens Notice Naming Rule 资料夹 请把题号(三码) 放在题目前面,并用"_" 隔开,题目中间有空格,请用“-” 隔开 (ex: 078_Subsets) 题号请参考 如果没有题号,就先省略 档案 Owner 整理...
分类子集Web应用程序 目录 国际化 会话存储 错误处理 快取 基本文件结构 后端 部署方式本地主机 配置React脚本 整合与依存关系 ... GET /subsets GET /subsets/{subsetId}/ GET /subsets/{subsetId}/vers
997 leetcode c 保持饥饿,保持愚蠢 我自己的 leetcode 纯 c 解决方案。 去做: 使用哈希表更新 ...78-subsets.c。 (完毕) 使用动态规划更新 qn 494-target-sum.c。 (完毕) 使用位操作更新 289-game-
,n} into four subsets N-J, j= 1,2,3,4, according to different external input ranges, we can conclude that the HONNs have exact 3(#N2) equilibrium points, 2(#N2) of them are locally stable and others ...
用于训练所有子集的python脚本
Subsets II Permutations Permutations II Combinations Letter Combinations of a Phone Number 广度优先搜索 Word Ladder Word Ladder II Surrounded Regions 总结 深度优先搜索 Additive Number Palindrome ...
关于Banach空间中的超弱紧子集和其等价性,程立新,程庆进,类比于Banach空间中的弱紧集和超自反空间中子集的性质,本文目的是讨论Banach空间中凸和非凸子集的超弱紧性质。作为结果,本文给出了超�
%SubSets SubSets(m,n) 返回一个 n 成员集的所有 m 维子集。 % Subsets(m,n,k) 从第 k 个成员开始。 % 这个例程递归地工作。 结果按列排列% 在矩阵中。
The CIFAR-10 and CIFAR-100 are labeled subsets of the 80 million tiny images dataset. They were collected by Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. The CIFAR-10 dataset The CIFAR-10 dataset...
3- All the dialect(方言的) regions should be represented in both subsets, with at least 1 male and 1 female speaker from each dialect. 4- The amount of overlap of text material in the two subsets...
var subsets = require ( 'subsets' ) ; var checks = 0 ; var sets = subsets ( [ 1 , 10 , 4 , 25 , 26 , 6 ] , function ( a , b ) { checks ++ ; return Math . abs ( a - b ) <= 3 ; } ) ; console . log ...
As single-layer feed-forward neural networks, extreme learning machine (ELM) has recently been used with success for the classification of hyperspectral images (HSIs). However, the results of pure ...
Banach空间的一致凸子集,程庆进,,本文在Banach空间中引入了一致凸集的概念,其可视作一致凸Banach空间的局部化概念,证明了每个一致凸集具有许多良好的性质,例如,每个有�
实施:C | C ++ | JS | PHP | Python | 去吧Ruby
指向matlab代码选择具有代表性的小插曲子集来调查道德判断的多个方面 该存储库包含 Kruepke 等人使用的 Matlab 代码。 (2018) 从 Knutson 等人创建的 ...个特征中的每一个选择一个标记为“低”、“中等/中性”和“高”...