LeetCode 046 Permutations
2024-08-28 04:26:44
题目要求: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]
.
分析:
参考网址:http://www.cnblogs.com/panda_lin/archive/2013/11/12/permutations.html
可以使用STL的next_permutation函数。
不使用的话,要递归生成全排列。
① 生成[2, 3]的全排列[2, 3]和[3, 2],然后把1加上去生成[1, 2, 3]和[1, 3, 2]。
② 交换1和2的位置,生成[1, 3]的全排列[1, 3]和[3, 1],然后把2加上去生成[2, 1, 3]和[2, 3, 1]。
③在第二步的基础上交换2和3的位置,生成[2, 1]的全排列[2, 1]和[1, 2],然后把3加上去生成[3, 2, 1]和[3, 1, 2]。
① [1, 2, 3] [1, 3, 2]
② [2, 1, 3] [2, 3, 1]
③ [3, 2, 1] [3, 1, 2]
代码如下:
class Solution {
public:
vector<vector<int> > permute(vector<int> &num) { vector<vector<int>> result;
sort(num.begin(), num.end()); //STL next_permutation
do{
result.push_back(num);
}while(next_permutation(num.begin(), num.end())); return result; }
};
class Solution {
public:
void internalPermute(vector<int> &num, int index, vector<int> &perm, vector<vector<int> > &result) {
int size = num.size(); if (size == index) {
result.push_back(perm);
}
else {
for (int i = index; i < size; ++i) {
swap(num[index], num[i]);
perm.push_back(num[index]);
internalPermute(num, index + 1, perm, result);
perm.pop_back();
swap(num[index], num[i]);
}
}
} vector<vector<int> > permute(vector<int> &num) {
vector<vector<int> > result;
vector<int> perm; internalPermute(num, 0, perm, result); return result;
}
};
最新文章
- H5基于iScroll实现下拉刷新,上拉加载更多
- UITabBarController 更改tabbariteam上的选中图片
- Java 中的值传递和参数传递
- 撤销git reset soft head操作
- linux安装pip报错
- NPN&;PNP
- 转载 deep learning:八(SparseCoding稀疏编码)
- ZOJ 3927 Programming Ability Test
- git团队合作开发流程
- Python字符处理
- hihocoder——1041国庆出游(搜索)
- linux 文件传输 SCP
- Intellij IDEA 中如何查看maven项目中所有jar包的依赖关系图(转载)
- 使用nginx作为webservice接口代理
- Hue中hive(hive cli)查询结果中显示列名,不带表名
- web.xml关于spring的讲解
- DAY6-Flask项目
- bzoj 2752
- C语言—第二次作业
- 881. Boats to Save People