本文主要是介绍[leetcode] 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].
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() functionint 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：
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() functionN = num.size();ret.clear();perm(num, 0);return ret;}
};思路3
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,7int 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() functionint 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;}
};思路四
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() functionvector<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;}
};这篇关于[leetcode] permutations的讨论的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
