一个面试题: reverse words in place with O(n) time
将输入的字符串中的单词从后到前重排如:输入"Somewhere i belong."
输出"Belong.i Somewhere"
请高手展示代码
[此贴子已经被HJin于2007-7-26 0:03:15编辑过]
我还是先问一下，为什么输出的第一个B变成大写了，而后面的S没有变成小写，具体规则是什么？
[此贴子已经被作者于2007-7-23 1:15:41编辑过]
2007-07-22 17:28
2007-07-23 01:09
2007-07-23 14:52
2007-07-23 17:57
2007-07-25 21:19
2007-07-25 21:48
/*---------------------------------------------------------------------------
File name: ReverseWords.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/25/2007 09:05:10
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762
Modification history:
===========================================================================
1. I wrote this function a few years ago. Fully test it before delivering it
to your client.
2. I removed comments to force you study the code instead of copy it.
3. Good luck!
*/
#include <stdio.h>
#include <string.h>
void strsrev(char* p, char* r)
{
char t;
while(p<r)
{
t = *p;
*p++ = *r;
*r-- = t;
}
}
/**
Reverse words in place.
O(n) algorithm.
*/
void wordrev(char* s)
{
char*b =s, *e = s+strlen(s)-1;
if(!s)
return;
strsrev(b, e);
b=e=s;
while(*b)
{
while(*b && *b == ' ')
++b;
e = b;
while(*e && *e != ' ')
++e;
strsrev(b, e-1);
b=e;
}
}
int main()
{
char s[100] = "Somewhere i belong.";
wordrev(s);
*s &= 0xDF;
printf("%s\n", s);
return 0;
}
[此贴子已经被作者于2007-7-26 0:07:08编辑过]
2007-07-26 00:05
/*---------------------------------------------------------------------------
File name: ReverseWords.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/25/2007 09:05:10
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762
Modification history:
===========================================================================
1. I wrote this function a few years ago. Fully test it before delivering it
to your client.
2. I removed comments to force you study the code instead of copy it.
3. Good luck!
*/
#include <stdio.h>
#include <string.h>
void strsrev(char* p, char* r)
{
char t;
while(p<r)
{
t = *p;
*p++ = *r;
*r-- = t;
}
}
/**
Reverse words in place.
O(n) algorithm.
*/
void wordrev(char* s)
{
char*b =s, *e = s+strlen(s)-1;
if(!s)
return;
strsrev(b, e);
b=e=s;
while(*b)
{
while(*b && *b == ' ')
++b;
e = b;
while(*e && *e != ' ')
++e;
strsrev(b, e-1);
b=e;
}
}
int main()
{
char s[100] = "Somewhere i belong.";
wordrev(s);
*s &= 0xDF;
printf("%s\n", s);
return 0;
}
红字部分看的不是很懂啊，当第一次循环结束后，b和e应该都指向.belong中的l的位置吧。然后执行while(*b && *b == ' ') ++b;语句，b能指向i吗?
还有e刚执行完第一次循环后，不是也指向l吗，如何在第二次调用strsrev(b, e-1);时，指向i呢？
2007-08-01 22:18
/*---------------------------------------------------------------------------
File name: ReverseWords.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/25/2007 09:05:10
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762
Modification history:
===========================================================================
1. I wrote this function a few years ago. Fully test it before delivering it
to your client.
2. I removed comments to force you study the code instead of copy it.
3. Good luck!
*/
#include <stdio.h>
#include <string.h>
void strsrev(char* p, char* r)
{
char t;
while(p<r)
{
t = *p;
*p++ = *r;
*r-- = t;
}
}
/**
Reverse words in place.
O(n) algorithm.
*/
void wordrev(char* s)
{
char*b =s, *e = s+strlen(s)-1;
if(!s)
return;
strsrev(b, e);实现字符串倒序
b=e=s;
while(*b)
{
while(*b && *b == ' ')
++b;用于跳出多余的空格
e = b;
while(*e && *e != ' ')
++e;e指向空格
strsrev(b, e-1);将一个单词倒序
b=e;
}
}
int main()
{
char s[100] = "Somewhere i belong.";
wordrev(s);
*s &= 0xDF;首字符大写
printf("%s\n", s);
return 0;
}
比较精炼的程序，没有用到栈，对了，这个首字符大写是我猜的，哪里有写？经验不足啊！
[此贴子已经被作者于2007-8-2 12:29:06编辑过]
2007-08-02 12:26
2007-08-02 12:41
