首页 > 其他 > 详细

leetcode -day31 Subsets I II

时间:2014-06-22 17:07:40      阅读:431      评论:0      收藏:0      [点我收藏+]
1、


Subsets

Given a set of distinct integers, 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,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

分析:想到的方法是首先进行排序,从头到尾一次选择要不要该元素,可以递归实现,如下代码。

class Solution {
public:
    vector<vector<int> >*  v;
    vector<vector<int> > subsets(vector<int> &S) {
    
        v = new vector<vector<int> >();
        //先排序
        sort(S.begin(),S.end());

        vector<int> res;
        generate(res, S, 0);
        return *v;
    }
    //对每一个元素有放与不放两种选择
    void generate(vector<int> res, vector<int> &S, int i)
    {
        if(i == S.size())
        {
            v->push_back(res);
            return;
        }
        else
        {
            generate(res, S, i+1);//不放当前元素
            res.push_back(S[i]); //放入当前元素
            generate(res, S, i+1);
        }
    }
};

2、Subsets II

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],
  []
]

分析:此题和上题类似,就是有了重复元素,想法也是先进行排序,排序后,从头到尾遍历,记录每个元素的个数,每个子集中有0-i个指定元素(一共i个),代码如下:

class Solution {
public:
    vector<vector<int> >*  v;
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
    
        v = new vector<vector<int> >();
        //先排序
        sort(S.begin(),S.end());

        vector<int> res;
        generate(res, S, 0,0,0);
        return *v;
    }
    //pre: 排序后前一个元素 num: 前一个元素出现的次数
    void generate(vector<int> res, vector<int> &S, int i,int pre,int num)
    {
        if(i == S.size())
        {   
            v->push_back(res);
            for(int j=1; j<=num; ++j){
                res.push_back(pre); //放入之前元素
                v->push_back(res);
            }
            return;
        }
        else if(pre != S[i] || num < 1 ) //与之前元素不同或者是首次
        {
            if(num < 1){
                generate(res,S,i+1,S[i],1);
            }else{
                generate(res, S, i+1,S[i],1);//放入0个元素
                for(int j=1; j<=num; ++j){
                    res.push_back(pre); 
                    generate(res, S, i+1,S[i],1);//放入i个元素后从当前位置开始
                }
            }
        }else{
            pre = S[i];
            generate(res, S, i+1,pre,num+1);
        }
    }
};


leetcode -day31 Subsets I II,布布扣,bubuko.com

leetcode -day31 Subsets I II

原文:http://blog.csdn.net/kuaile123/article/details/32137611

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!