[C++]LeetCode: 64 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],
  []
]

在上一道题 Subsets基础上,允许出现集合中包含重复数字,以集合{1,2,2}为例子,画出二叉树

Answer 1: DFS解法

思路:分析二叉树,我们知道处理第三个元素2时,因为前面已经出列一次2,所以第三层中,我们只在添加过2的结合{1,2}和{2}再添加2,而没有在集合{1},{}中添加2(画叉的那些分支),假设下面还有一个2,我们将只会在第四层包含两个2的集合{12,2}和{2,2}中添加2,其他都不添加。因此DFS, 如果当前处理的数字,在前面出现了k次(原集合S中),那么我们要处理的集合中必须包含k个该元素。否则会出现重复的集合。

技术分享

Attention:

1. 首先要计算当前元素在原集合中出现了几次,计算k.这个首先可以先定位到第一个和S[ileaf]相同数字的位置,再做差得到重复次数。

<span style="font-size:14px;"> //fstname指向第一个和S[ileaf]相同数字的位置
        int fstname = ileaf;
        do{
            fstname--;
        }while(S[fstname] == S[ileaf]);
        fstname++;
        
        int sameNum = ileaf - fstname; //重复数字个数,不包含S[ileaf]本身</span>


2. 判断该子集中是否包含k个重复元素,由于子集是有序排列,所以直接定位到子集中对应的第一个出现重复数字的位置,判断是否等于S[ileaf]。如果相同,说明从这个位置开始,有k个该重复元素在该子集中。

<span style="font-size:14px;">//如果本轮处理不包含重复数字,或者当前处理的数字前面出现了k次,并且要处理的集合中包含k个该元素。加入S[ileaf]
        if(sameNum == 0 || (tmpres.size() >= sameNum && tmpres[tmpres.size() - sameNum] == S[ileaf]))
        {
            tmpres.push_back(S[ileaf]);
            subsetsWithDup_helper(S, ileaf + 1, tmpres, ret);
            tmpres.pop_back();
        }</span>

AC Code:

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        vector<vector<int>>  ret;
        if(S.size() == 0) return ret;
        vector<int> tmpres;
        sort(S.begin(), S.end());
        subsetsWithDup_helper(S, 0, tmpres, ret);
        return ret;
    }
    
private:
    void subsetsWithDup_helper(vector<int>& S, int ileaf, vector<int>& tmpres, vector<vector<int>>& ret)
    {
        if(ileaf == S.size())
        {
            ret.push_back(tmpres);
            return;
        }
        
        //fstname指向第一个和S[ileaf]相同数字的位置
        int fstname = ileaf;
        do{
            fstname--;
        }while(S[fstname] == S[ileaf]);
        fstname++;
        
        int sameNum = ileaf - fstname; //重复数字个数,不包含S[ileaf]本身
        //如果本轮处理不包含重复数字,或者当前处理的数字前面出现了k次,并且要处理的集合中包含k个该元素。加入S[ileaf]
        if(sameNum == 0 || (tmpres.size() >= sameNum && tmpres[tmpres.size() - sameNum] == S[ileaf]))
        {
            tmpres.push_back(S[ileaf]);
            subsetsWithDup_helper(S, ileaf + 1, tmpres, ret);
            tmpres.pop_back();
        }
        
        subsetsWithDup_helper(S, ileaf + 1, tmpres, ret);
        
        return;
    }
};

Answer 2:

思路分析:

处理一个元素,分两种情况:

1)如果当前处理的元素没有出现过,则把前面得到的所有集合加上该元素,集合数翻倍。

2)如果当前处理的元素出现过,那么我们只把上一轮处理过的集合加上该元素(即上一轮添加了当前重复数字的集合)。比如,添加第二个2时,我们只把上一轮添加过2的集合{1,2}、{2}再添加一个2到结果中,其他集合不懂,{1}和{}是从上一层直接继承下来的,不做处理。由于我们是顺序添加集合到ret中的,所以处理过的集合总是排在ret的后面位置。

Attention:

1. 需要维护两个变量,上一次处理的数字,即将要进行操作的子集数量。

<span style="font-size:14px;">//如果本次处理数字和上次不重复,更新这两个变量
            if(S[i] != last)
            {
                last = S[i];
                opResNum = ret.size();
            }</span>
2.如果本次处理元素重复,将不更新opResNum,则 ret.size() - opResNum不等于0,我们只处理后面的res.size() - opResNum个集合。

<span style="font-size:14px;">//如果出现重复数字,本次处理的集合数和上次一样,即只处理上次处理过的集合。resSize - opResNum,如果opResNum不等于res.size(),则只处理上次处理过的集合。由于迭代是顺序添加的,所以上次处理过的集合一定排在ret的末尾res.size() - opResNum个。
            int retSize = ret.size();
            for(int j = retSize - 1; j >= retSize - opResNum; j--)
            {
                ret.push_back(ret[j]);
                ret.back().push_back(S[i]);
            }</span>

AC Code:

class Solution {
public:
    vector<vector<int> > subsetsWithDup(vector<int> &S) {
        int len = S.size();
        sort(S.begin(), S.end());
        vector<vector<int>> ret(1);
        //上一个处理的数字,即将要进行操作的子集数量
        int last = S[0], opResNum = 1;
        
        for(int i = 0; i < S.size(); i++)
        {
            //如果本次处理数字和上次不重复,更新这两个变量
            if(S[i] != last)
            {
                last = S[i];
                opResNum = ret.size();
            }
            
            //如果出现重复数字,本次处理的集合数和上次一样,即只处理上次处理过的集合。resSize - opResNum,如果opResNum不等于res.size(),则只处理上次处理过的集合。由于迭代是顺序添加的,所以上次处理过的集合一定排在ret的末尾res.size() - opResNum个。
            int retSize = ret.size();
            for(int j = retSize - 1; j >= retSize - opResNum; j--)
            {
                ret.push_back(ret[j]);
                ret.back().push_back(S[i]);
            }
        }
        
        return ret;
    }
};



郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。