LeetCode(90)Subset 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], [] ]
분석은 다음과 같습니다.
이전 문제와 기본적으로 마찬가지로 이 문제의 입력 집합 중의 요소가 중복될 수 있기 때문에 출력된 하위 집합에서 중복을 필터해야 한다.중복된 결과를 먼저 얻고 set 또는hash 필터로 (0(N) 공간 복잡도 사용)
내 코드:
첫 번째 버전, 먼저 교체하고 다시 필터링 버전
//
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
int length=(int)S.size();
vector<vector<int>> res(1);
if(length==0)
return res;
std::sort(S.begin(), S.end());
for(int i=0;i<S.size();++i){
int j=(int)res.size();
while(--j>=0){
res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
set<vector<int> > filter_set;
for(int i=0;i<res.size();++i)
filter_set.insert(res[i]);
res.clear();
for(set<vector<int> >::iterator it=filter_set.begin();it!=filter_set.end();it++)
res.push_back(*it);
return res;
}
};
두 번째 버전, 먼저 귀속된 다음에 다시 버전을 여과한다
//
class Solution {
public:
set<vector<int> > subsets_(vector<int> &S, int i){
if(i==-1){
vector<int> set_tmp;
set<vector<int> > set_set_tmp;
set_set_tmp.insert(set_tmp);
return set_set_tmp;
}
set<vector<int> > set_vec_tmp = subsets_(S,i-1);
set<vector<int> > set_vec_out = set_vec_tmp;
set<vector<int> >::iterator set_vec_it=set_vec_tmp.begin();
for(set_vec_it=set_vec_tmp.begin();set_vec_it!=set_vec_tmp.end();set_vec_it++){
vector<int> vec_tmp=*set_vec_it;
vec_tmp.push_back(S[i]);
std::sort(vec_tmp.begin(),vec_tmp.end());
set_vec_out.insert(vec_tmp);
}
return set_vec_out;
}
vector<vector<int> > subsetsWithDup(vector<int> &S) {
int length=(int)S.size();
vector<vector<int>> res;
set<vector<int>> tmp;
if(length==0)
return res;
length--;
tmp=subsets_(S,length);
for(set<vector<int> >::iterator it=tmp.begin();it!=tmp.end();it++){
vector<int> small_vec=*it;
res.push_back(small_vec);
}
return res;
}
};제3판
나는 아직 잘 이해하지 못했다. set를 사용하지 않고hash를 사용하지 않고 직접 필터를 하지 않는다. 홈페이지에서 본 답은 다음과 같다.
// set hash
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> path;
vector<vector<int> > result;
sort(S.begin(), S.end());
sub(S, 0, path, result);
return result;
}
void sub(vector<int> &s, int begin, vector<int> &path, vector<vector<int> > &result) {
result.push_back(path);
for (int i = begin; i < s.size(); ++i) {
if (i != begin && s[i] == s[i - 1]) continue;
path.push_back(s[i]);
sub(s, i + 1, path, result);
path.pop_back();
}
}
};참고 자료:
(1) http://discuss.leetcode.com/questions/253/subsets
update: 2014 - 12 - 17
LeetCode(79) Subset의 중복된 요소가 없는 교체판의 사고방식에서 회고하는 사고방식은 다음과 같다.
제목: If S =[1,2,3], return a solution of: [[3],[1],[2],[1,2,3],[1,3],[1,2],[]
먼저 S를 정렬합니다.
다음에subset의 생성을 진행합니다.
초기 상태: []
0회, S[0]에 가입, 획득: [],[1]
1회, S[1] 가입, 획득: [],[1],[2],[1,2]
2회, S[2]에 가입하여 획득: [],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]
위에서 볼 수 있듯이,
0차 -> 1차, S[1]를 S[0]의 모든 subset에 넣고 새로운subset(즉[2],[1,2])을 형성한 다음 이 새로운subset을 이전 S[0] 당시의 오래된 subset(즉[],[1])과 함께 새로운 결과(즉[],[1],[2],[1,[1,2])를 구성한다.
1차 -> 2차, S[2]를 S[1]의 모든 subset에 넣고 새로운 subset(즉 [3],[1,3],[2,3],[1,2,3])을 형성한 다음 이 새로운 subset을 이전 S[1]의 오래된 subset(즉 [],[1],[2],[1,2])과 함께 새로운 결과(즉 [],[1],[2],[1,[1,2],[3],[1,3],[1,3],[1,2])를 구성한다.
만약 문자열 S를 길이가 더 긴 문자열로 입력한다면, 위의 과정을 반복하여 S의 모든 요소를 현재의 집합에 넣을 때까지 합니다.
그리고 중복 버전의 교체 버전을 다시 봅시다.
If S = [1,2,2], a solution is: [[2],[1],[1,2],[2,2],[1,2],[]] 먼저 S를 정렬합니다.
다음에subset의 생성을 진행합니다.
0번, S[0]를 입력하고 획득: [],[1]
1회, S[1]를 기입하여 획득: [],[1],[2],[1,2]
두 번째, S[2]를 입력하여 획득: [],[1],[2],[1,2],[2,2],[1,2]
중복 입력이 있는 상황에서
0번째, 중복 입력이 없기 때문에 중복 버전이 없는 경우와 같습니다.
첫 번째는 중복 입력이 없기 때문에 중복 버전이 없는 것과 같다.
두 번째는 반복 입력(2차 S[2]=1차 S[1]=2)이 있기 때문에 새로 생성된 부분(2차 녹색)은 1차 새로 생성된 부분(1차 빨간색)에서만 생성할 수 있고 0차에서 생성할 수 없습니다.
다음,this_로layer 현재 생성 부분을 기록합니다. 다음에 중복 입력이 나타나면this_layer는 새로운 부분을 생성합니다.
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
std::sort(S.begin(), S.end());
vector<vector<int> > final(1);
vector<vector<int> > this_layer;
vector<int> every;
int len = 0;
for (int i = 0; i < S.size(); ++i) {
if (i>0 && S[i] == S[i-1]) {
vector<vector<int> > this_layer_swap;
for (int j = 0; j < this_layer.size(); ++j) {
every = this_layer[j];
every.push_back(S[i]);
final.push_back(every);
this_layer_swap.push_back(every);
}
this_layer = this_layer_swap;
} else {
len = final.size();
this_layer.clear();
for (int j = 0; j < len; ++j) {
every = final[j];
every.push_back(S[i]);
final.push_back(every);
this_layer.push_back(every);
}
}
}
return final;
}
};업데이트: 2015-03-24 불필요한 중간 변수vector
//14ms
class Solution {
public:
vector<vector<int> > subsetsWithDup(vector<int> &S) {
std::sort(S.begin(), S.end());
vector<vector<int> > final(1);
vector<vector<int> > this_layer;
vector<vector<int> > next_layer;
int len = 0;
for (int i = 0; i < S.size(); ++i) {
if (i>0 && S[i] == S[i-1]) {
next_layer.clear();
for (int j = 0; j < this_layer.size(); ++j) {
final.push_back(this_layer[j]);
final.back().push_back(S[i]);
next_layer.push_back(final.back());
}
this_layer.swap(next_layer);
} else {
len = final.size();
this_layer.clear();
for (int j = 0; j < len; ++j) {
final.push_back(final[j]);
final.back().push_back(S[i]);
this_layer.push_back(final.back());
}
}
}
return final;
}
};이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
