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<vector<int> > permute(vector<int> #
这个题大眼一看就是思路一大坨,这里做一个整理吧
思路1
比较直观的想法就是递归咯~~ 在num中拿出1个数字放在第一个,然后剩下的数字做一个全排列,最早接触这个问题的时候我就是这么写的
class Solution { public: vector<vector<int> > permute(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function int N = num.size(); vector<vector<int> > ret; if(N == 1){ ret.push_back(num); return ret; } vector<vector<int> > post; vector<int> cur; vector<int> tmp; for(int i = 0; i < N; i++){ cur = num; cur.erase(cur.begin()+i); post = permute(cur); for(int j = 0; j < post.size(); j++){ tmp = post[j]; tmp.insert(tmp.begin(), num[i]); ret.push_back(tmp); } } return ret; } };
思路2:
建立一棵树,比如说
1234
1234 2134 3214 4231 //就是swap(1,1) swap(1,2) swap(1,3) swap(1,4)
|
234 324 432
|
34 43
然后捏,就用DFS遍历一下,叶子节点就是我们想要的啦
class Solution { vector<vector<int> > ret; int N; public: void perm(vector<int> &num, int i){ if( i == N){ ret.push_back(num); } for(int j = i; j < N; j++){ swap(num[i], num[j]); perm(num, i + 1); swap(num[j], num[i]); } } vector<vector<int> > permute(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function N = num.size(); ret.clear(); perm(num, 0); return ret; } };
思路3
stl的algorithm里面其实是有next permutation的算法的,那其实用next permutation的方法也是一个不错的选择
next permutation的算法就是。。。swap + reverse。。。
class Solution { public: void nextPermutation(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function //5,4,7,5,3,2 // | | // i j //5,5,7,4,3,2 //5,5,2,3,4,7 int i = num.size()-1; while(i > 0 && num[i-1] >= num[i] ){ i--; } int j = i; while(j < num.size() && num[j] > num[i-1]) j++; if(i == 0){ reverse(num.begin(), num.end()); }else{ swap(num[i-1], num[j-1]); reverse(num.begin() + i, num.end()); } } int factorial(int n){ return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n; } vector<vector<int> > permute(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function int N = num.size(); vector<vector<int> > ret; ret.push_back(num); for(int i = 1; i < factorial(N); i++){ nextPermutation(num); ret.push_back(num); } return ret; } };
思路四
我觉得思路4是一个很常规的思路,很多把recursive的code改成iterative的code都会用到这样的方法,其实呢,它的本质就是把N个for改成while的方法。介个方法在编程之美里面的“电话号码”那一节提到过,不明白的童鞋可以去看一看,我觉得第一次想写粗来还是很难的,不过多写几个,就会很熟练啦
对应介个题目的思路捏就是。。。举个例子来说吧
如果我想求1,2,3,4的全排列
偶的思路就是建一个特殊的数,它的进位方法是 3, 2, 1, 0
所以,这个数的++过程就是
0000 -> 0010 -> 0100 -> 0110 ->0200 -> 0210 ->
1000 -> 1010 -> 1100 -> 1110 ->1200 -> 1210 ->
2000 -> 2010 -> 2100 -> 2110 ->2200 -> 2210 ->
3000 -> 3010 -> 3100 -> 3110 ->3200 -> 3210
哇哈哈哈,刚好是24个!
然后捏? b0 b1 b2 b3就代表在当前剩下的数字中选择第bi个
哇!好复杂。。。
比如0210
0: 在1234中选择第0个,就是1
2: 在234中选择滴2个,就是4
1: 在23中选择第1个,就是3
0: 在2中选择第0个,就是2
所以0210对应点就素 1432
class Solution { public: int factorial(int n){ return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n; } void plusp(vector<int> &p, const vector<int> &bound){ int i = p.size()-1; while(i >= 0){ if(p[i] < bound[i]){ p[i]++; break; }else{ p[i] = 0; i--; } } } vector<vector<int> > permute(vector<int> &num) { // Start typing your C/C++ solution below // DO NOT write int main() function vector<vector<int> > ret; vector<int> ori_num = num; vector<int> tmp = num; int N = num.size(); vector<int> p(N, 0); vector<int> bound = num; for(int i = 0; i < N; i++){ bound[i] = N - 1 - i; } for(int i = 0; i < factorial(N); i++){ num = ori_num; for(int j = 0; j < N; j++){ tmp[j] = num[p[j]]; num.erase(num.begin() + p[j]); } ret.push_back(tmp); plusp(p, bound); } return ret; } };
转载:http://blog.csdn.net/tuantuanls/article/details/8717262