面试题:单词翻转(代码简洁&效率)-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

面试题:单词翻转(代码简洁&效率)

简介:

作者:陈太汉

单词翻转问题是个大公司常考的一个面试题,在网上看了不少实现方法,感觉都有瑕疵,在下今天又无聊一次,自己写了两种实现方式
一个是简洁版,一个是效率版
简洁版当然是简洁明了,思路清晰,很容易看懂,但是效率上有待改进,等改进之后发现发现就不是那么好理解了,所以就有了效率版,
个人还是主张简洁版,它看起来实在是舒服,让我很是满意。
为什么说简洁版效率有瑕疵呢?就是因为方法InvertWord的参数是值传递,就会不断的有变量构造和析构,
效率版就是解决这个问题,改为引用传递,但是引用传递又产生了另一些问题。看一下代码,你会懂的。

//将一句话翻转
// 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 }
复制代码

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章