面試題:單詞翻轉(代碼簡潔&效率)

作者：陳太漢

單詞翻轉問題是個大公司?？嫉囊粋€面試題,在網上看了不少實現方法，感覺都有瑕疵，在下今天又無聊一次，自己寫了兩種實現方式
一個是簡潔版，一個是效率版
簡潔版當然是簡潔明了，思路清晰，很容易看懂，但是效率上有待改進，等改進之后發現發現就不是那么好理解了，所以就有了效率版，
個人還是主張簡潔版，它看起來實在是舒服，讓我很是滿意。
為什么說簡潔版效率有瑕疵呢？就是因為方法InvertWord的參數是值傳遞，就會不斷的有變量構造和析構，
效率版就是解決這個問題，改為引用傳遞，但是引用傳遞又產生了另一些問題?？匆幌麓a，你會懂的。

//將一句話翻轉
// I  am a student--> student a am I
//先每個單詞翻轉，再整句話翻轉

簡潔版

1 #include<iostream>
2 #include<string>
3  usingnamespace std;
4
5  class InvertWords{
6 public:
7 InvertWords(string* wo):words(wo){}
8 void Invert()
9 {
10 int len=words->size();
11 int beg=-1;
12 //翻轉整個字符串
13 InvertWord(beg,len);
14 //翻轉每個單詞
15 for(int i=0;i<len;i++)
16 {
17 if(words->at(i)=='')
18 {
19 InvertWord(beg,i);
20 beg=i;
21 }
22 }
23 }
24
25 private:
26 void InvertWord(int beg,int end)
27 {
28 char tmp;
29 while(++beg<--end)
30 {
31 tmp=words->at(beg);
32 words->at(beg)=words->at(end);
33 words->at(end)=tmp;
34 }
35 }
36 string* words;
37 };

效率版

1 #include<iostream>
2 #include<string>
3 usingnamespace std;
4
5 class InvertWords{
6 public:
7 InvertWords(string* wo):words(wo){}
8 void Invert()
9 {
10 int len=words->size();
11 int beg=-1,k;
12 //翻轉整個字符串
13 InvertWord(beg,len);
14 //由于方法InvertWord的參數為引用類型，beg和len的值都被修改了，所以要還原他們的值
15 beg=-1;
16 len=words->size();
17 //翻轉每個單詞
18 for(int i=0;i<len;i++)
19 {
20 k=i;//k的作用就是保存現場，為了還原i到當前值
21 if(words->at(i)=='')
22 {
23 InvertWord(beg,i);
24 i=k;//還原i
25 beg=i;
26 }
27 }
28 }
29
30 private:
31 void InvertWord(int& beg,int& end)
32 {
33 char tmp;
34 while(++beg<--end)
35 {
36 tmp=words->at(beg);
37 words->at(beg)=words->at(end);
38 words->at(end)=tmp;
39 }
40 }
41 string* words;
42 };

測試代碼

1 int main()
2 {
3 string s=" i am a student " ;
4 InvertWords *rw=new InvertWords(&s);
5 rw->Invert();
6 cout<<s<<endl;
7 int a=0;
8 cin>>a;
9 return0;
10 }