posts - 71,  comments - 41,  trackbacks - 0

MS面试曾出过这样一道题目,将给定字符串按单词翻转,如,"This is Charles" -> "Charles is This"

方法一,需要额外缓冲区

 1 #include  < cstring >
 2 void  ReverseByWords( char   * s,  char  seperator)
 3 {
 4      int  iRevTokenScanner  =  strlen(s)  -   1 ;
 5      char   * buffer  =   new   char [iRevTokenScanner  +   2 ]();
 6      int  iWritePos  =   0 ;
 7      int  iWordEnd, iWordReadPos;
 8
 9      while  (iRevTokenScanner  >=   0 )
10      {
11          if  (s[iRevTokenScanner]  !=  seperator)
12          {
13             iWordEnd  =  iRevTokenScanner;
14             
15              while  (iRevTokenScanner  >=   0   &&   s[iRevTokenScanner]  !=  seperator)
16                 iRevTokenScanner -- ;
17             
18             iWordReadPos  =  iRevTokenScanner  +   1 ;
19
20              while  (iWordReadPos  <=  iWordEnd)
21                 buffer[iWritePos ++ =  s[iWordReadPos ++ ];
22         }

23          else
24          {
25             buffer[iWritePos ++ =  s[iRevTokenScanner -- ];
26         }
 
27     }

28
29     buffer[iWritePos]  =   ' \0 ' ;
30     strcpy(s, buffer);
31
32      if  (buffer)
33      {
34         delete [] buffer;
35         buffer  =   0 ;
36     }

37 }

方法二,个人比较prefer
 1void ReverseString(char *s, int start, int end)
 2{
 3    while (start < end)
 4    {
 5        if (s[start] != s[end])
 6        {
 7            s[start] ^= s[end];
 8            s[end] ^= s[start];
 9            s[start] ^= s[end];
10        }

11                
12        start++;
13        end--;
14    }

15}

16
17void ReverseByWords(char *s, int len, char seperator)
18{
19    int start = 0, end = 0;
20
21    ReverseString(s, start, len - 1);
22
23    while (end < len)
24    {
25        if (s[end] != seperator)
26        {
27            start = end;
28
29            while (end < len && s[end] != seperator)
30                end++;
31            end--;
32
33            ReverseString(s, start, end);
34        }

35        
36        end++;
37
38    }
//while
39}

等有空再回来作注释吧,现在挺忙的,先把code贴出来
posted on 2006-11-16 18:50 Charles 阅读(406) 评论(0)  编辑 收藏 引用 所属分类: 面试小算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2006年11月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

决定开始写工作日记,记录一下自己的轨迹...

常用链接

留言簿(4)

随笔分类(70)

随笔档案(71)

charles推荐访问

搜索

  •  

积分与排名

  • 积分 - 47992
  • 排名 - 455

最新评论

阅读排行榜

评论排行榜