mooc程序设计与算法(二)003:全排列
程序员文章站
2022-05-08 19:06:26
...
003:全排列
题目链接:http://cxsjsxmooc.openjudge.cn/2020t2springall/003/
思路
- n个字符的全排列 = 最左边元素 + (n-1)个元素的全排列
- 当元素只有一个,最左边元素的下标为n-1(下标0开始,也就是最左边元素为最后一个元素),输出s,结束
- 最左边元素要变化,依次和后面的元素交换,可以用到swap内置函数
- 扩展到第i个元素开始的全排列,就是第i个元素依次和它自己以及后面的元素交换,第i个元素以及它后面的元素个数为n
- 注意:不能以i==len-2为边界条件(len就是string的长度,最后一个元素的下标是len-1),这样的话,还剩下两个元素,也要全排列
- 因此,以i==len-1为边界条件,也就是string的最后一个元素(0开始)
- string和数组名不同,作为函数形参,实际上开辟了新的内存,在函数中,是对string的拷贝进行操作,每次swap之后,不用换回来
#include <iostream>
using namespace std;
void myFunc(string s, int i) {
int len = s.length();
if (i == len-1) {
cout << s << endl;
return;
}
for (int j = i; j < len; j++) {
swap(s[i], s[j]);
myFunc(s, i + 1);
}
return;
}
int main() {
string s;
cin >> s;
myFunc(s, 0);
}
上一篇: Maven的Eclipse插件安装
下一篇: 97. 约数之和(分治)