题目一
permutations
题目描述
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].
题二解析:
这是很经典的全排列问题,本题的解法很多。因为这里的所有数都是相异的,故笔者采用了交换元素+DFS的方法来求解。
class Solution {
public:
vector<vector<int>> res;
vector<vector<int> > permute(vector<int> &num) {
// 采用前后元素交换的办法,dfs解题
solve(num,);
return res;
}
void solve(vector<int> &num, int n)
{
// 将当前数组加到结果集中
if(n==num.size())
{
res.push_back(num);
return;
}
// 将当前位置的数跟后面的数交换,并搜索解
for(int i=n;i<num.size();++i)
{
swap(num[n],num[i]);
solve(num,n+);
swap(num[n],num[i]);
}
}
};
有重复数字的全排列数
题二描述:
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],
[2,1,1]
]
思路:
这里我们先考虑一下,它与第二题唯一的不同在于:在DFS函数中,做循环遍历时,如果与当前元素相同的一个元素已经被取用过,则要跳过所有值相同的元素。
举个例子:对于序列<1,1,2,3>。在DFS首遍历时,1 作为首元素被加到list中,并进行后续元素的添加;那么,当DFS跑完第一个分支,遍历到1 (第二个)时,这个1 不再作为首元素添加到list中,因为1 作为首元素的情况已经在第一个分支中考虑过了。
为了实现这一剪枝思路,有了如下的解题算法。
解题算法:
1. 先对给定的序列nums进行排序,使得大小相同的元素排在一起。
2. 新建一个used数组,大小与nums相同,用来标记在本次DFS读取中,位置i的元素是否已经被添加到list中了。
3. 根据思路可知,我们选择跳过一个数,当且仅当这个数与前一个数相等,并且前一个数未被添加到list中。
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) {
vector<vector<int>> res;
vector<int> temp;
vector<bool> used(num.size(),false);
sort(num.begin(),num.end());
solve(num,temp, used, res);
return res;
}
void solve(vector<int> &num,vector<int> &cur, vector<bool> &used, vector<vector<int>> &res)
{
if(cur.size()==num.size())
{
res.push_back(cur);
return;
}
for(int i=;i<num.size();++i)
{
if(used[i])
continue;
if(i>&&num[i]==num[i-]&&!used[i-])
continue;
used[i]=true;
cur.push_back(num[i]);
solve(num,cur,used,res);
cur.pop_back();
used[i]=false;
}
}
};