请教leetcode Subsets II - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

请教leetcode Subsets II

请教leetcode Subsets II# JobHunting - 待字闺中

f*m2012-07-13 07:07

1 楼

碰上类似的问题，除了用set,总是搞不定。谢谢指教。要排序和用prev吗？
Given a collection of integers that might contain duplicates, S, return all
possible subsets.
Note:
Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example,
If S = [1,2,2], a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

h*32012-07-13 07:07

2 楼

我觉的你要把leetcode上所有的题都问一遍。

f*m2012-07-13 07:07

3 楼

没有搜到合适的答案，自己又不会做，能有什么别的办法呢？

a*22012-07-13 07:07

4 楼

排序啊，相邻比较

f*m2012-07-13 07:07

5 楼

请问能show一下code吗？
非常感谢。
我写了一个，不过没有通过online judge.
void SubsetII(vector & I, int start, vector &A, vector
> &ret, int level) {
if(level == I.size()) {
ret.push_back(A);
return;
}
int i = start;
int prev = -1;
if (I[i] != prev) {
A.push_back(I[i]);
SubsetII(I, i + 1, A, ret, level + 1);
A.pop_back();
prev = I[i];
}
SubsetII(I, i + 1, A, ret, level + 1);
}
vector > subsetsWithDup(vector &S) {
vector > ret;
vector A;
sort(S.begin(), S.end());
SubsetII(S, 0, A, ret, 0);
return ret;
}

j*22012-07-13 07:07

6 楼

有人给个正解吗？

int>

【在 f*********m 的大作中提到】

: 请问能show一下code吗？
: 非常感谢。
: 我写了一个，不过没有通过online judge.
: void SubsetII(vector & I, int start, vector &A, vector
: > &ret, int level) {
: if(level == I.size()) {
: ret.push_back(A);
: return;
: }
: int i = start;

a*y2012-07-13 07:07

7 楼

why dont you just check if(find(ret.begin(), ret.end(), A) == ret.end()) and
then add into the vector

int>

【在 f*********m 的大作中提到】

e*s2012-07-13 07:07

8 楼

Bad performance

and

【在 a*******y 的大作中提到】

: why dont you just check if(find(ret.begin(), ret.end(), A) == ret.end()) and
: then add into the vector
:
: int>

R*12012-07-13 07:07

9 楼

刚写了一个可以work的，但是感觉效率很低
还是实现了一个find的function
class Solution {
public:
vector > subsetsWithDup(vector &S) {
vector myset = S;
sort (myset.begin(), myset.end());
return subset (myset);
}

vector< vector > subset (vector &S) {
vector < vector > res;
vector < vector > imediate;
vector < vector >::iterator it;
vector temp;
int lastdigit, pre;
if (S.size() == 1) {
res.insert(res.end(),temp);
temp.insert(temp.end(),S[0]);
res.insert(res.end(),temp);
return res;
}else if (S.size() > 1) {
lastdigit = S.back();
S.pop_back();
pre = S.back();
imediate = subset(S);
res = imediate;
if (pre != lastdigit){
for (it = imediate.begin(); it < imediate.end(); it++) {
temp = *it;
temp.insert(temp.end(),lastdigit);
res.insert(res.end(),temp);
}
}else{
for (it = imediate.begin(); it < imediate.end(); it++) {
temp = *it;
temp.insert(temp.end(),lastdigit);
if ( !vectorFind(res,temp) ){
res.insert(res.end(),temp);
}
}
}
}else{
return res;
}
}

bool vectorFind (vector < vector > &S, vector &target) {
vector< vector >::iterator it;
for (it = S.begin(); it < S.end(); ++it) {
if (*it == target) return true;
}
return false;
}
};

j*22012-07-13 07:07

10 楼

这个是不是还是先产生解再检查是否已经产生过？正解应该是不产生重复解吧（就像
permutation的问题一样）

【在 R******1 的大作中提到】

: 刚写了一个可以work的，但是感觉效率很低
: 还是实现了一个find的function
: class Solution {
: public:
: vector > subsetsWithDup(vector &S) {
: vector myset = S;
: sort (myset.begin(), myset.end());
: return subset (myset);
: }
:

R*12012-07-13 07:07

11 楼

对的是在插入vector之前先检查是否产生过
开始是想不产生重复解的，但是程序是recursive的，混起来之后有点儿乱，就偷懒了
一下
有什么办法可以不用先生成再check的吗

【在 j********2 的大作中提到】

: 这个是不是还是先产生解再检查是否已经产生过？正解应该是不产生重复解吧（就像
: permutation的问题一样）

p*22012-07-13 07:07

12 楼

我写了一个你看看对不对。好久没做题了，感觉有些生疏。
ArrayList> all = new ArrayList>();

void dfs(int[] num, int start, ArrayList al)
{
all.add(new ArrayList(al));
int prev=-1;
for(int i=start;i{
if(num[i]!=prev)
{
al.add(num[i]);
dfs(num,i+1,al);
al.remove(al.size()-1);
prev=num[i];
}
}
}

public ArrayList> subsetsWithDup(int[] num)
{
all.clear();
Arrays.sort(num);
ArrayList al=new ArrayList();
dfs(num,0,al);
return all;
}

Y*f2012-07-13 07:07

13 楼

这个是对的，该怎么理解呢？

);

【在 p*****2 的大作中提到】

: 我写了一个你看看对不对。好久没做题了，感觉有些生疏。
: ArrayList> all = new ArrayList>();
:
: void dfs(int[] num, int start, ArrayList al)
: {
: all.add(new ArrayList(al));
: int prev=-1;
: for(int i=start;i: {
: if(num[i]!=prev)

p*v2012-07-13 07:07

14 楼

我的思路是用一个类似于binary tree的图来做的，
开始时只有0 （empty set），然后左边不加新元素，右边加，
遇到重复就在现有set的基础上加1至cnt+1个，因为我这里的cnt
是从0开始的，程序中就是从0到cnt loop的。
希望能帮助你理解
vector > subsets2(vector &s) {
vector > results;
if (s.empty()) return results;
results.push_back(vector());//init with an empty set
int cnt;
sort(s.begin(), s.end());
for (size_t i=0; i//compute this first because it will increase during the loop
size_t limit=results.size();
cnt=0;
while (i+cntcnt++;//compute how many dups
for (size_t sz=0; szvector v = results[sz];
for (int ii=0; ii<=cnt; ++ii) {
v.push_back(s[i]);
results.push_back(v);
}
}
}
return results;
}

all

【在 f*********m 的大作中提到】

: 碰上类似的问题，除了用set,总是搞不定。谢谢指教。要排序和用prev吗？
: Given a collection of integers that might contain duplicates, S, return all
: possible subsets.
: Note:
: Elements in a subset must be in non-descending order.
: The solution set must not contain duplicate subsets.
: For example,
: If S = [1,2,2], a solution is:
: [
: [2],

H*e2012-07-13 07:07

15 楼

我也贴一个我做的，大数据测试60ms
我的写了一个子函数，可以生成大小为m的 subset，subset不会因为duplicate
element重复，然后主函数循环调用子函数
class Solution {
public:
vector > subsetsWithDup(vector &S) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector > subsets;
if(S.size()==0)
return subsets;
sort(S.begin(),S.end());
int len=S.size();
int * a=new int[len];

for(int i=0;ia[i]=S[i];
}
stack s;
for(int i=0;i<=len;i++){
subset(a,len,i,0,s, subsets);
}
return subsets;
}
void subset(int * a, int n, int m, int k, stack & s, vectorint> > &subsets){
if(m==0){
//save current subset
vector * curSubset = new vector();
while(!s.empty()){
curSubset->push_back(s.top());
s.pop();
}
int len=curSubset->size();
for(int i=len-1;i>=0;i--){
s.push(curSubset->at(i));
}
//make sure subset is non-descending order
sort(curSubset->begin(),curSubset->end());
subsets.push_back(*curSubset);
}
if(n - k +1 < m )
return;
for(int i=k;iif(i > k && a[i]==a[i-1]){
continue;
}
s.push(a[i]);
subset(a,n,m-1,i+1, s, subsets);
s.pop();
}
}
};
这个题刚好是我选的一门课的作业题，老师给个参考答案：
一种是我这种用stack帮助枚举，另一种解法就是二爷给的用DFS解
时间复杂度，子函数是O(m*Cnm),不可能做的更好了

E*U2012-07-13 07:07

16 楼

C++ iterative solution, 请指教:
class Solution {
public:
vector > subsetsWithDup(vector &S) {
vector v;
vector > result;
result.push_back(v);
sort(S.begin(), S.end());
int b = S[0] == 0 ? 1 : 0;
int begin = 0;
int size = 0;
for (int& a : S)
{
int i = (a == b) ? size : 0;
size = result.size();
for (; i < size; ++i)
{
v = result[i];
v.push_back(a);
result.push_back(v);
}
b = a;
}
return result;
}
};