《Cracking the Coding Interview》——第9章：递归和动态规划—

《Cracking the Coding Interview》——第9章：递归和动态规划——题目5

2014-03-20 03:23

题目：给定一个字符串，输出其全排列。

解法：可以调用STL提供的next_permutation()，也可以自己写一个。对于这种看起来简单的题目，应该在能优化的地方，尽量想办法优化。在面试里如果大家都会做的题，你就得做的很好才能拉开差距，否则就等着thank you了。

代码：

 1 // 9.5 Print all permutations of a string.
 2 #include <algorithm>
 3 #include <cstdio>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 void countingSort(char s[], int n)
 8 {
 9     static int c[256];
10     
11     if (s == nullptr || n < 2) {
12         return;
13     }
14     
15     int i, j;
16     
17     memset(c, 0, 256 * sizeof(int));
18     for (i = 0; i < n; ++i) {
19         ++c[s[i]];
20     }
21     
22     n = 0;
23     for (i = 0; i < 256; ++i) {
24         for (j = 0; j < c[i]; ++j) {
25             s[n++] = i;
26         }
27     }
28     s[n] = 0;
29 }
30 
31 bool myNextPermutation(char s[], int n)
32 {
33     if (s == nullptr) {
34         return false;
35     }
36     
37     int i;
38     int ll, rr, mm;
39     char ch;
40     
41     for (i = n - 2; i >= 0; --i) {
42         if (s[i] < s[i + 1]) {
43             ll = i + 1;
44             rr = n - 1;
45             break;
46         }
47     }
48     
49     if (i < 0) {
50         return false;
51     }
52     
53     if (s[rr] > s[i]) {
54         ch = s[rr];
55         s[rr] = s[i];
56         s[i] = ch;
57     } else {
58         while (rr - ll > 1) {
59             mm = (ll + rr) / 2;
60             if (s[mm] > s[i]) {
61                 ll = mm;
62             } else {
63                 rr = mm;
64             }
65         }
66         ch = s[ll];
67         s[ll] = s[i];
68         s[i] = ch;
69     }
70     
71     ll = i + 1;
72     rr = n - 1;
73     for (i = ll; i < ll + rr - i; ++i) {
74         ch = s[i];
75         s[i] = s[ll + rr - i];
76         s[ll + rr - i] = ch;
77     }
78     return true;
79 }
80 
81 int main()
82 {
83     char s[100];
84     int len;
85     
86     while (scanf("%s", s) == 1 && (len = strlen(s)) > 0) {
87         countingSort(s, len);
88         do {
89             puts(s);
90         } while (myNextPermutation(s, len));
91     }
92     
93     return 0;
94 }