程序员面试100题(算法)之翻转句子中单词的顺序

 

方法一：

[cpp] view plaincopy

1. // 程序员面试100题(算法)之翻转句子中单词的顺序   
2.   
3. #include "stdafx.h"     
4. #include<iostream>     
5.   
6. using namespace std;    
7.   
8. void reverse(char* begin, char* end)    
9. {    
10.     if ((begin == NULL) || (end == NULL))    
11.         return ;  
12.   
13.     char temp;  
14.     while (begin < end)    
15.     {    
16.         temp = *begin;  
17.         *begin = *end;  
18.         *end = temp;   
19.         ++begin;    
20.         --end;    
21.     }    
22. }   
23.     
24. char *reverseSentence(char *pData)    
25. {    
26.     if(NULL == pData)    
27.         return NULL;    
28.     
29.     char *begin = pData;    
30.     char *end = pData;    
31.     
32.     while(*end != '\0')    
33.     {    
34.         end++;    
35.     }    
36.     
37.     end--;    
38.     //reverse the overall sentence     
39.     reverse(begin, end);    
40.     
41.     //reverse each word in the reversed sentence     
42.     begin = pData;    
43.     end = pData;    
44.     
45.     while(*begin != '\0')    
46.     {    
47.         if(*begin == ' ')    
48.         {    
49.             begin++;    
50.             end++;    
51.             continue;    
52.         }    
53.     
54.         if(*end == ' ' || *end == '\0')    
55.         {    
56.             end--;    
57.             reverse(begin, end);    
58.             end++;    
59.             begin = end;    
60.         }    
61.         else    
62.         {    
63.             end++;    
64.         }    
65.     }    
66.     
67.     return pData;    
68. }    
69.     
70. int _tmain(int argc, _TCHAR* argv[])    
71. {    
72.     char sentence[] = "I am in China today!! I am very happy!!!!";    
73.     char *newSentence = NULL;    
74.   
75.     newSentence = reverseSentence(sentence);    
76.     cout << newSentence << endl;  
77.   
78.     return 0;    
79. }    

方法二：（用异或实现反转）

[cpp] view plaincopy

1. #include "stdafx.h"   
2. #include <iostream>   
3. #include <cstring>     
4.   
5. using namespace std;  
6.     
7. void Reverse(char* b, char* e)    
8. {    
9.     if ((b == NULL) || (e == NULL))    
10.         return ;    
11.   
12.     while (b < e)    
13.     {    
14.         *b ^= *e;    
15.         *e ^= *b;    
16.         *b ^= *e;    
17.         ++b;    
18.         --e;    
19.     }    
20. }    
21.     
22. void WordReverse(char* s)    
23. {    
24.     if (s == NULL)    
25.         return;   
26.   
27.     Reverse(s, s + strlen(s) - 1);    
28.   
29.     char* b = s;    
30.     char* e = s;    
31.     while(*e)    
32.     {    
33.         if (*e == ' ')    
34.         {    
35.             Reverse(b, e - 1);    
36.             ++e;    
37.             b = e;    
38.         }    
39.         else    
40.             ++e;    
41.     }    
42.   
43.     Reverse(b, e - 1);    
44. }    
45.   
46. int _tmain(int argc, _TCHAR* argv[])  
47. {  
48.     char my[] = "I am a student";    
49.     Reverse(my, my + strlen(my) - 1);    
50.     cout << my << endl;    
51.   
52.     char my2[] = "I    am   a   student   ";    
53.     WordReverse(my2);    
54.     cout << my2 << endl;    
55.   
56.     return 0;  
57. }  

 附：

1、递归逆置字符串

[cpp] view plaincopy

1. char *recurReverse(char* s, int left, int right)  
2. {  
3.     if(left >= right)  
4.         return s;  
5.   
6.     char c = s[left];  
7.     s[left] = s[right];  
8.     s[right] = c;  
9.   
10.     recurReverse(s, left + 1, right - 1);  
11. }  

2、普通的字符串逆置，申请新的空间，然后逆序复制过去。

[cpp] view plaincopy

1. char *commonReverse(char* s)    
2. {    
3.     if(NULL == s)  
4.     {  
5.         return NULL;  
6.     }  
7.   
8.     char *end = s;  
9.   
10.     while(*end != '\0')  
11.     {  
12.         end++;  
13.     }  
14.   
15.     end--;  
16.     char *newStr = (char*)malloc(sizeof(char) * (strlen(s) + 1));  
17.     char *str = newStr;  
18.   
19.     while(end != s)  
20.     {  
21.         *newStr = *end;  
22.         end--;  
23.         newStr++;  
24.     }  
25.   
26.     *newStr = *end;  
27.     *(++newStr) = '\0';  
28.   
29.     return str;  
30. }