a***e
发帖数: 413 | 1 Given a collection of numbers that might contain duplicates, return all
possible unique permutations.
For example,
[1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].
不清楚为什么这个答案会引起Output Limit Exceeded
而把if (i>k&&num[i]==num[k])
改成一个
bool noswap(int k, int i, const vector num){
for (int j=k;j
if (num[j]==num[i]){
return true;
}
}
return false;
}
就被accept了。请问如何能提高解决这一类问题的能力呢？感觉工作中很少，几乎用不
到这些东西啊。。。。。以前也没系统学过cs的课。多谢多谢！
vector > permuteUnique(vector &num) {
vector > ret;
int n = num.size();
perm(num,0,n-1,ret);
return ret;
}
void perm(vector num, int k, int n, vector> &ret)
{
if (k==n)
{
ret.push_back(num);
}
else
{
for (int i=k;i<=n;i++)
{
if (i>k&&num[i]==num[k])
continue;
else
{
int t = num[i];
num[i] = num[k];
num[k] = t;
perm(num, k+1, n, ret);
}
}
}
} | T*******e
发帖数: 4928 | | a***e
发帖数: 413 | 3 再问一下 ， 对于无重复的permutation, 这个答案好理解。但怎么改来处理有重复数
的问题呢？
Given a collection of numbers, return all possible permutations.
For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].
vector > permute(vector& num) {
sort(num.begin(), num.end());
vector> result;
vector path;
dfs(num, path, result);
return result;
}
private:
void dfs(const vector& num, vector &path,vector > &
result) {
if (path.size() == num.size()) {
result.push_back(path);
return;
}
for (auto i : num) {
auto pos = find(path.begin(), path.end(), i);
if (pos == path.end()) {
path.push_back(i);
dfs(num, path, result);
path.pop_back();
}
}
} |
|
