LeetCode(78)Subset
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], [] ]
분석은 다음과 같습니다.
이 문제는 주어진 집합 (중복 원소가 없음) 의 모든 하위 집합을 찾아내는 데 매우 흥미롭다.
첫 번째 사고 방향은 교체된다.이 안에 또 한 가지 일을 똑똑히 생각해야 한다. 결과는non-desceding 순서를 요구하는 것이다. 교체할 때 어떻게 이 점을 실현할 수 있을까?너는 서브집합을 생성할 때마다 이 서브집합을 수조로 삼아 정렬할 수 있다.하지만 매번 순서를 정하는 데는 시간이 걸린다.그래서 다른 방법을 생각해 볼 수 있어요.만약 원 집합을 정렬한다면, 교체할 때 원 집합의 정렬 후의 순서에 따라 하위 집합을 점차적으로 생성할 것이다.이렇게 하면 곧 많아지고 코드의 양도 적어진다.나는 처음에 매우 2의 코드를 썼는데 제출한 후에 leetcode 홈페이지에 코드의 양을 50% 줄이고 시간을 90% 줄이는 좋은 코드가 하나 있었다.
구체적인 사고방식은 다음과 같다.
초기 상태: []
0번, S[0]:[],[1] 가입
1회 가입 S[1]: [],[1],[2],[1,2]
1회 가입 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])과 함께 S[1]의 결과(즉[],[1],[1],[1,2])를 구성한다.
S의 모든 요소를 현재 집합에 넣을 때까지 이 과정을 반복합니다.
두 번째 사고 방향은 차례차례 돌아간다.생각이 비교적 간단하다.
세 번째 사고 방향은 수학적 측면에서 볼 때 원 집합에 n개의 원소가 있다고 가정하면 원 집합의 자 집합의 개수는 2의 n차방으로 2^n으로 기록된다.0~2^n-1에서 2^n 개수에 대응한다.이 2^n 개수는 2진법으로 표시하면 모두 n자리가 있는 것을 발견할 수 있다.한 명당 0을 찾거나 1을 찾습니다.만약에 i위가 0을 취하면 원 집합의 i번째 요소가 현재 새로 생성된 하위 집합에 나타나지 않고 반대로 i위가 1을 취하면 원 집합의 i번째 요소가 현재 새로 생성된 하위 집합에 나타난다.이 사고방식은 비트 조작을 통해 실현할 수 있다.
코드는 다음과 같습니다.
// 40ms ， ，leetcode 。 S , j vector ， vector 。
class Solution {
public:
vector<vector<int> > subsets(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){ // while(j-->0) ， 。 ， 。 。
res.push_back(res[j]);
res.back().push_back(S[i]);
}
}
return res;
}
};// 628ms ， 。。。。
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > res_vec_vec;
set<set<int> > res_set_set;
set<set<int> >::iterator res_set_it;
int length=(int)S.size();
if(length==0)
return res_vec_vec;
set<int> small_set;
res_set_set.insert(small_set); //inset"[]" as a start.
for(int i=0;i<length;i++){
set<set<int> > tmp_res_set=res_set_set;
for(res_set_it=res_set_set.begin();res_set_it!=res_set_set.end();res_set_it++){
for(int k=0;k<(int)length;k++){ //bug1 for(int k=0;i<(int)length;k++){
set<int> tmp_small_set=*res_set_it;
tmp_small_set.insert(S[k]);
tmp_res_set.insert(tmp_small_set);
}
}
res_set_set.swap(tmp_res_set);
}
for(res_set_it=res_set_set.begin();res_set_it!=res_set_set.end();res_set_it++){
set<int> tmp_small_set=*res_set_it;
vector<int> tmp_vec;
for(set<int>::iterator it=tmp_small_set.begin();it!=tmp_small_set.end();it++){
tmp_vec.push_back(*it);
}
res_vec_vec.push_back(tmp_vec);
}
return res_vec_vec;
}
};// 52ms
class Solution {
public:
set<set<int> > subsets_(vector<int> &S, int i){
if(i==-1){
set<int> set_tmp;
set<set<int> > set_set_tmp;
set_set_tmp.insert(set_tmp);
return set_set_tmp;
}
set<set<int> > set_set_tmp = subsets_(S,i-1); //
set<set<int> > set_set_out = subsets_(S,i-1);
set<set<int> >::iterator set_set_it=set_set_tmp.begin();
for(set_set_it=set_set_tmp.begin();set_set_it!=set_set_tmp.end();set_set_it++){
set<int> set_tmp=*set_set_it;
set_tmp.insert(S[i]);
set_set_out.insert(set_tmp);
}
return set_set_out;
}
vector<vector<int> > subsets(vector<int> &S) {
int length=(int)S.size();
vector<vector<int>> res;
set<set<int>> tmp;
if(length==0)
return res;
length--;
tmp=subsets_(S,length);
for(set<set<int> >::iterator it=tmp.begin();it!=tmp.end();it++){
set<int> small_set=*it;
vector<int> small_vec;
// std::cout<<std::endl;
for(set<int>::iterator small_it=small_set.begin();small_it!=small_set.end();small_it++){
small_vec.push_back(*small_it);
// std::cout<<"*small_it="<<*small_it<<"\t";
}
res.push_back(small_vec);
}
return res;
}
};// 2 n leetcode 40ms
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
vector< vector<int> > result;
sort(S.begin(), S.end());
// Loop from 0 to 2^n - 1
for (int x = 0; x < (1 << S.size()); ++x) {
vector<int> sln;
for (int i = 0; i < S.size(); ++i)
// If the i-th least significant bit is 1, then choose the i-th integer
if (x & (1 << i))
sln.push_back(S[i]);
result.push_back(sln);
}
return result;
}
};
소결:
(1) 전자증과 후자증에 관하여.앞의 교체판 중 하나로 전자증과 후자증 조작부호를 보았다.양자의 차이는?
int i = 0, j;
j = ++i; // j = 1 , i = 1:prefix yields incremented value
j = i++; // j = 1 , i = 2:postfix yields unincremented value오른쪽 값: 값 부여 작업에 사용할 수 있는 오른쪽이지만 왼쪽 값에는 사용할 수 없습니다.오른쪽 값은 읽기만 하고 쓸 수 없습니다.
후방 조작부호는 1을 추가하지 않은 값을 조작의 결과로 되돌려야 하기 때문에 조작수의 원래 값을 저장해야 하기 때문에 비교적 복잡한 유형에 대해 이런 추가 작업은 더욱 큰 대가를 들일 수 있다.선행 조작부호를 많이 사용하는 것을 권장합니다.
(2) 비트 조작 시뮬레이션 2의 N 차방 버전에서 비트 조작에 사용되었다.
if (x & (1 << i))이 말의 뜻은 무엇입니까?우선 i와 x를 이해한다.i는 입력 집합 S의 i위를 대표하고 x는 수치 범위가 0~2^n-1인 숫자를 대표한다.만약 x의 i위가 0이라면, 입력 집합의 요소 S[i]는 현재 하위 집합에 나타나고, 그렇지 않으면 나타나지 않습니다.이 말은 S[i]의 i위가 1인지 아닌지를 판단하는 것이다.그리고 이 말은 밑에 이렇게 써도 등가할 수 있어요.
if (( x >> i ) & 1)참고 자료:
(1) http://discuss.leetcode.com/questions/253/subsets
(2) http://www.cnblogs.com/maxwellp/archive/2012/02/11/2346844.html
update: 2014- 12-17
사고방식은 위의 교체판 1과 유사하여 속도가 매우 빠르다.16ms
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
std::sort(S.begin(), S.end());
vector<vector<int> > final(1);
for (int i = 0; i < S.size(); ++i) {
int length = final.size();
for (int j = 0; j < length; ++j) {
//std::cout<<"j="<<j<<std::endl;
vector<int> temp = final[j];
temp.push_back(S[i]);
final.push_back(temp);
}
}
return final;
}
};
update: 2014-12-17
사고방식은 위의bit 조작판, 16ms와 유사하다.나는 아직 x&(1
// : bit operation
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
std::sort(S.begin(), S.end());
vector<vector<int> > final;
vector<int> every;
int total = pow(2, S.size());
int j = 0;
for (int i=0; i < total; ++i) {
int current = i;
while(current>0) {
if (current & 1) {
every.push_back(S[j]);
}
current = current>>1;
j++;
}
final.push_back(every);
every.clear();
j = 0;
}
return final;
}
};
update: 2015-03-24
반복판 첫 번째 버전,result와 tmp 두 개의vector로 뒤집기
//10ms
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end());
vector<vector<int> > result(1);
vector<vector<int> > tmp;
for (int i = 0; i < S.size(); ++i) {
int length = result.size();
tmp.assign(result.begin(), result.end());
for (int j = 0; j < length; ++j) {
tmp.push_back(result[j]);
tmp.back().push_back(S[i]);
}
result.swap(tmp);
}
return result;
}
};교체판 두 번째 버전은 사실result라는 1개의vector만으로 충분하다.
//9ms
class Solution {
public:
vector<vector<int> > subsets(vector<int> &S) {
sort(S.begin(), S.end());
vector<vector<int> > result(1);
for (int i = 0; i < S.size(); ++i) {
int length = result.size();
for (int j = 0; j < length; ++j) {
result.push_back(result[j]);
result.back().push_back(S[i]);
}
}
return result;
}
};DFS 재귀속
class Solution {
public:
// void print_vector(vector<int> v) {
// for (int i=0; i < v.size(); ++i) {
// std::cout<<v[i]<<"\t";
// }
// std::cout<<std::endl;
// }
void helper(vector<int> &S, vector<int> &every, vector<vector<int> > &final, int begin, int end) {
for (int i = begin; i < end; ++i) {
every.push_back(S[i]);
final.push_back(every);
helper(S, every, final, i + 1, end);
every.pop_back();
}
}
vector<vector<int> > subsets(vector<int> &S) {
vector<vector<int> > final(1);
vector<int> every;
sort(S.begin(), S.end());
int start = 0;
helper(S, every, final, start, (int)S.size());
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에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
