【剑指Offer面试题】九度OJ1369：字符串的排列

分类：剑指OFFER

题目链接地址： ?pid=1503 题目1369：字符串的排列时间限制：1 秒内存限制：32 兆特殊判题：否提交：2839解决：708 题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入：每个测试案例包括1行。输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。输出：对应每组数据,按字典序输出所有排列。样例输入： abc BCA 样例输出： abc acb bac bca cab cba ABC ACB BAC BCA CAB CBA

思路分析

一看到全排序，我就想到了STL源码分析里的next_permutation函数。next_permutation是求出下一个排列组合。下一个排列组合：对序列 {a, b, c}，每一个元素都比后面的小，按照字典序列，固定a之后，a比bc都小，，c比b大，它的下一个序列即为{a, c, b}。可以参考【STL】next_permutation的原理和使用

int main(){char s[20];int n;while (scanf(“%s”, s) == 1) {n = strlen(s);sort(s, s + n);while (true) {puts(s);if(!next_permutation(s+0, s + n)) {break;}}}return 0;}

当然自己写一个next_permutation最好：

;void my_swap(char &x, char &y){char ch;ch = x;x = y;y = ch;}void my_reverse(char s[], int ll, int rr){if (ll >= rr) {return;}int i;for (i = ll; i < ll + rr – i; ++i) {my_swap(s[i], s[ll + rr – i]);}}bool my_next_permutation(char s[], int n){int i, j;for (i = n – 1; i > 0; –i) {if (s[i – 1] < s[i]) {break;}}if (i == 0) {return false;}–i;for (j = n – 1; j > i; –j) {if (s[i] < s[j]) {my_swap(s[i], s[j]);break;}}my_reverse(s, i + 1, n – 1);return true;}int main(){char s[20];int n;while (scanf(“%s”, s) == 1) {n = strlen(s);sort(s, s + n);while (true) {puts(s);if(!my_next_permutation(s, n)) {break;}}}return 0;}

上一篇【剑指Offer面试题】九度OJ1503：二叉搜索树与双向链表

顶0踩0

突然之间失去了语言。那才是真正的寂寞，

相关文章：

你感兴趣的文章：

标签云：