主题：【原创】如何REVERSE一个C STRING? -- 老成都
家园 递归解法 如果P或者P+1为0，直接返回
否则递归处理P+1;
然后用循环将P依次后移1位，直到遇到0为止
返回P
- 复 递归解法
家园 code出来了,谢谢帮忙,CODE在内, void reverse(char *p)
{
if(p[0]=='\0') return;
if(p[1]=='\0') return;
if(p[2]!='\0') reverse(p+1);
while(p[1]!='\0') {
p[0]=p[0]+p[1];
p[1]=p[0]-p[1];
p[0]=p[0]-p[1]; //switch.
p++;
}
}
调试已经通过,
"然后用循环将P依次后移1位，直到遇到0为止" 我费了好一会儿才明白.
家园 这比用一个临时变量，记住长度效率差多了 void reverse(char *p)
{
int cnt = 0;
// calculate length
while (p[cnt] != 0) ++cnt;
while ((cnt>>1) > 0)
{
// switch first and the last
*p ^= p[cnt-1] ^= *p ^=p[cnt-1];
p++;
// cuz p moved forward, we have to minus 2
cnt -= 2;
}
}
您老看看，算长度，n, 交换位置1/2n，总共O(n)。只用一个临时变量。
递归算法，
1）要是N很大，stack就爆掉了，
2）而且每次调用函数，必须push ebp,调整ebp，压入参数，还要记住retern addr, jump回来，clean stack。浪费无数。
3）时间复杂度上，递归算法是O(n^2)
就为省一个临时变量。
现实生活中，谁要这么写程序，真可以直接fire了。出这种题的也应该fire，纯粹误导。
本帖一共被 1 帖 引用 (帖内工具实现)家园 这道明显是brain teaser，又不是编程题，限制条件列得 明明白白，谁叫你优化时间空间了啊？不许用临时变量和额外函数的意义，不在于节省空间，而在于测试你在极端条件下能不能跳出陈腐框框，独辟蹊径。测试的是创造力。有规定说面试不许出智力题了吗？又有规定说智力题不许借用编程的语境了吗？
家园 花一个!问题是俺们这些老蓝领反应已经很慢了, 做这种题拼不过刚毕业的PHD.
我那朋友有三个面食碰到了这题,头一个面食没做出这题,后面两个都做出来了(从河上抄的答案),不过他还是没拿到OFFER.我其实知道他干活还可以,在华为时是某ROUTER的开发主力.
这就是IT残酷的一面,你永远得和很年轻的人竟争.
家园 把 int cnt 换成 char *end, 然后 while ((cnt>>1) > 0) 换成 while (end > p) 是不是更直观一些呢？
家园 有道理！花 用个char *end记住末尾更直观！
家园 这个当然是工作过的人的标准答案,没另外用个 数组,俺给99分,可惜俺没资格面食别人.
俺不给100分的原因是俺不喜欢SWAP的那部分,对公司里的菜鸟来说不易读.写成多行不要紧,好读,编译器自己会优化的:)
家园 Does it really work? Does your code really work?
Which compiler are you using and on which platform, Windows? Unix?
I tried your code using Visual C++ 6.0 on Windows and got an access violation for the following line as expected:
p[0] = p[0] + p[1];
Bigbug
家园 I test it already.Notice: you need to pass a char[], you can not pass "hello the world" directly, you need to scan a string to a char buffer.
My environment is gcc/Linux.
Do you kown the difference for "char *p="hello the world" and the "char p[100]"?
My test code is something like
"
main()
{
char str[100],
scan("%s",str);
printf("original:%s\n",str);
reverse(str);
printf("reversed:%s\n",str);
}
"
It works fine. I guess you pass "hello the world" directly into the reverse function.
家园 这个方法好。花
家园 各路高手们,帮帮忙啊?俺挨个送花:),发言就有花! 家园 找了一下,网上的答案大多是错的.