QQ面试题目，证答案！
char *p指向一个C-style字符串；要求实现把字符串反转！
问：
1：效率最佳？
2：空间最佳？
问题点数：0、回复次数：58Top
1 楼flyinger（风往北吹）回复于 2005-05-22 20:45:17 得分 0
1：我的思路是能不能只扫描一遍就解决问题呢；这可能就是最佳的思路！
2：我的思路是找出长度，然后让首尾对换不就可以了；Top
2 楼flyinger（风往北吹）回复于 2005-05-22 20:47:11 得分 0
第一种没有想到合适的算法Top
3 楼foochow（无聊,灌水......）回复于 2005-05-22 21:00:58 得分 0
1.第一个字符开始扫描,把字符串倒着赋值给另一个字符串char*q,最后p=q,.....输出P.
2.首尾对换...
不知道这样可不可以^_^Top
4 楼lbing7（向青润老大学习!!!）回复于 2005-05-22 21:03:35 得分 0
//p指向一个C形字符串
char *q = p;
int Leg = strlen(p);
char c;
for (int i = 1; i <= Leg/2; i++,p++)
{
c = *p;
*p = *p[Leg-i];
*p[Leg-i] = c;
}
这个行不/?
Top
5 楼foochow（无聊,灌水......）回复于 2005-05-22 21:04:03 得分 0
别丢我鸡蛋啊,Top
6 楼sunman1982（冥王星）回复于 2005-05-22 21:42:16 得分 0
上上楼的应该是空间最省的算法了吧……至于效率 再想想……Top
7 楼adie20018u8（阿呆）回复于 2005-05-22 21:47:10 得分 0
找长度就遍历了一遍字符串了,效率呀..Top
8 楼sunman1982（冥王星）回复于 2005-05-22 21:49:07 得分 0
所以才是空间最省的啊 只用了len+1个Top
9 楼cao12m（★草上飞★）回复于 2005-05-22 21:52:02 得分 0
意思不懂得? 是不是既要效率最佳还要空间最佳 可是二者是有冲突的 效率最佳:进栈出来
空间最佳: 首尾兑换不过这个好象用指针不好实现 要通过解析成数组方式存放才行Top
10 楼cppprogramlover（爱相随—）回复于 2005-05-22 22:00:05 得分 0
//p指向一个C形字符串
char *q = p;
int Leg = strlen(p);
char c;
for (int i = 1; i <= Leg/2; i++,p++)
{
c = *p;
*p = *p[Leg-i];
*p[Leg-i] = c;
}
这个行不/?
这个什么效率，strlen费时间Top
11 楼sunman1982（冥王星）回复于 2005-05-22 22:05:26 得分 0
楼上，这个是空间最省的代码……Top
12 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-05-22 22:08:46 得分 0
//p指向一个C形字符串
char *q = p;
int Leg = strlen(p);
char c;
for (int i = 1; i <= Leg/2; i++,p++)
{
c = *p;
*p = *p[Leg-i];
*p[Leg-i] = c;
}
这个行不/?
----------
偶也只会写个这样的^_^Top
13 楼c_nestor（）回复于 2005-05-22 22:22:35 得分 0
高效率的解法了？Top
14 楼zdy_8212（zdy_8212）回复于 2005-05-22 22:23:35 得分 0
给出两个指针，将*p1=&str,p2='\0' while(*p2++ = *p1++)
2.给一个指针，*p1=&str,len=length(str); while(p[len--]=p++);
没有测，修改吧。呵。。Top
15 楼yujianlina（）回复于 2005-05-22 22:47:06 得分 0
char *q = p;
int Len = strlen(p);
char *q1=null;
char c;
q1=Len+1;
while(q!=q1)
{c=*p;
*p=*q1;
*q1=c;
q++;q1--;
}
行不Top
16 楼jasonnbfan（）回复于 2005-05-22 23:33:41 得分 0
int num,str_len;
char s[]="I love you!";
str_len=strlen(s);
char *str_s=&s[0]; //字符串头位置
char *str_e=&s[len-1]; //字符尾位置
while(1)
{
count++;
if(str_e-str_s<=0) //比较位置
break;
num=abs(*str_s-*str_e); //处理2个字符的差,进行加减处理
*str_s>*str_e?(*str_s-=num,*str_e+=num):(*str_s+=num,*str_e-=num);
++str_s;
--str_e;
}
写了一个不知道行不行.Top
17 楼MagicCarmack（MagiC++）回复于 2005-05-23 02:43:36 得分 0
//p指向一个C形字符串
char *q = p;
int Leg = strlen(p);
char c;
for (int i = 1; i <= Leg/2; i++,p++)
{
c = *p;
*p = *p[Leg-i];
*p[Leg-i] = c;
}
这个行不/?
----------
偶也只会写个这样的Top
18 楼Jinhao（辣子鸡丁·GAME就这样OVER了）回复于 2005-05-23 04:09:39 得分 0
void reverse(char* fwd_ptr)
{
char* bk_ptr = fwd_ptr;
while(*bk_ptr++ != '\0');
bk_ptr -= 2;
int len = (bk_ptr - fwd_ptr + 1)>>1;
char temp;
for(;len--; --bk_ptr, ++fwd_ptr)
{
temp = *bk_ptr;
*bk_ptr = *fwd_ptr;
*fwd_ptr = temp;
}
}
我觉得这道题很怪异！Top
19 楼zeeeitch（小浩）回复于 2005-05-23 09:26:17 得分 0
char* fun(char* str, size_t len)
{
for ( int i=0;i<len/2;++i)
{
str[i]=str[i]^str[len-i-1];
str[len-i-1]=str[i]^str[len-i-1];
str[i]=str[i]^str[len-i-1];
}
return str;
}
Top
20 楼zeeeitch（小浩）回复于 2005-05-23 09:27:18 得分 0
char* fun(char* str, size_t len)
{
for (int i = 0; i < len / 2; ++i)
{
str[i] = str[i] ^ str[len - i - 1];
str[len - i - 1] = str[i] ^ str[len - i - 1];
str[i] = str[i] ^ str[len - i - 1];
}
return str;
}Top
21 楼tuxw（醉书生）回复于 2005-05-23 09:56:07 得分 0
char *p;
char *q = p;
while(*q)
q++;
q--;
while(q > p)
{
*p ^= *q ^= *p ^= *q;
p++;
q--;
}Top
22 楼xzgyb（老达摩）回复于 2005-05-23 09:58:32 得分 0
void
reverse( char * str )
{
if ( str )
{
char* end = str;
while ( *++end )
;
for ( --end; str < end; ++str, --end )
{
if ( *str != *end )
{
char tmp = *str;
*str = *end;
*end = tmp;
}
}
}
Top
23 楼zqpsswh（似水无痕）回复于 2005-05-23 10:02:35 得分 0
效率最佳
开辟一块足够大内存
*p=new char [1000]
p=p+1000;
p='\0'
while(*--p=*str++);
空间浪费严重@@
空间最佳
创建两个指针
扫描一次数组
fp指向开头
ep指向末尾
while(fp<ep)
{
char temp;
temp = *fp;
*fp=*ep;
*ep=temp;
fp++;
ep--;
}
Top
24 楼Shatty（西北游侠）回复于 2005-05-23 10:33:40 得分 0
各位厉害，顶！！！Top
25 楼jackyhubin（想吃三明治）回复于 2005-05-23 11:35:03 得分 0
1.取字符串长度，取到尾地址，输出时反向就行了，反正指针也就是找一个地址，这样可能最有效率
2.不知道要怎么整，空间怎么定义？Top
26 楼yuanyou（元友）回复于 2005-05-23 12:54:03 得分 0
一时想不到其它的了Top
27 楼ltc_mouse（野地芳菲）回复于 2005-05-23 13:58:11 得分 0
zqpsswh(似水无痕) 给出的，效率确实很高
不过new出的这个p怎么回收是个问题呀，有memory leak的高效率意义也不大...Top
28 楼du51（郁郁思扬）回复于 2005-05-23 14:54:54 得分 0
strrevTop
29 楼caiyujian（菜菜虫）回复于 2005-05-23 15:29:05 得分 0
呵呵！都是高手哈。。。。我是才来的！希望以后大家多多指教！Top
30 楼Wolf0403（废人：独活十年～心如刀割）回复于 2005-05-23 15:34:29 得分 0
zqpsswh(似水无痕) 的方法一：不仅空间浪费，而且，如果字符串长度大于 1000，还可能导致溢出
方法二：两个指针都多余。只要一个 size_t 保存一下 strlen 的结果就可以用数组操作的方式解决，还节省了 4bytes
应该有更好的办法。Top
31 楼tuxw（醉书生）回复于 2005-05-23 15:49:17 得分 0
得到 size_t 需要调用 strlen 函数，大概的算法也是用一个指针遍历字符串
和我前面的这段码时间消耗差不多，还要付出函数调用的开销
while(*q)
q++;
q--;
而用 size_t 来循环的话需要一个循环计数变量
每次根据循环变量计算地址也会带来效率的损失
没有使用两个指针操作来得快
while(q > p)
{
*p ^= *q ^= *p ^= *q;
p++;
q--;
}
Top
32 楼llf_hust（）回复于 2005-05-23 16:54:18 得分 0
void Invert(char *s)
{
if(*s)
Invert(s+1);
putchar(*s);
}Top
33 楼yunlang187（零度寂寞）回复于 2005-05-23 17:07:37 得分 0
!Top
34 楼garlandz（流星街★童虎）回复于 2005-05-23 18:41:11 得分 0
看STL里的代码。Top
35 楼c_nestor（）回复于 2005-05-23 20:44:43 得分 0
赞同醉书生的看法Top
36 楼aaasng（）回复于 2005-05-23 21:33:41 得分 0
内存条倒插Top
37 楼aaasng（）回复于 2005-05-23 21:33:56 得分 0
错了
Top
38 楼nlstone（天外流星）回复于 2005-05-23 22:13:36 得分 0
"内存条倒插"
绝!
1 由于题目未给出字串长度,所以new新空间直接保存字串的方案不可靠,最可靠的还是只有用堆栈来解,虽然效率相对差些,但一定可解出正确答案,而单纯地new空间来保存新字串不一定可解出正确答案(溢出)
2 显然只能首尾交换了,用一个size_t来保存长度和增加一个指针的空间消耗是一样的,考虑到效率,还是用指针的好Top
39 楼kobefly（科比--网络学习中）回复于 2005-05-23 22:58:46 得分 0
关于第一个问题，我也没想出好办法
但第2个，首位交换，但你们都用了一个temp的char
其实这个可以用c-style字符串的结束符'\0'来保存，作为临时变量的存储地址，这样就不要另开辟一个char了
个人意见Top
40 楼hcann（十年磨一贱~~~）回复于 2005-05-24 07:59:11 得分 0
上面的效率最佳问题，还是在c里嵌套汇编好...
组合语言，或许是最快的吧!Top
41 楼lonelyforest（一生所爱）回复于 2005-05-24 08:37:34 得分 0
直接用汇编不是更好吗？效率高，空间用的也少， 或者，直接用机器语言也好，那才叫好呢！Top
42 楼xawi2000（）回复于 2005-05-24 09:09:10 得分 0
char * fun(char *p)
{
char *q;
strcpy(q,p);
while(*q)
q++;
q--;
while(*p)
{
*q=*p;
p++;
q--;
}
}
不要骂我哟~~Top
43 楼xawi2000（）回复于 2005-05-24 09:09:44 得分 0
还掉了一句return q;Top
44 楼crasy1984（hunter）回复于 2005-05-24 10:11:37 得分 0
请问下,^=这个是什么运算符啊?Top
45 楼valetine（鸣人）回复于 2005-05-24 12:34:09 得分 0
位运算吧！Top
46 楼mostideal（三甲）回复于 2005-05-24 13:35:25 得分 0
呵呵，，还很热闹呀。。
继续。。Top
47 楼yangjundeng（天下无双）回复于 2005-05-24 18:02:50 得分 0
我能写好这个，也不见得我就能写好软件。Top
48 楼hj008（catch jjhou）回复于 2005-05-24 18:15:29 得分 0
我个人觉得时间最佳的方法就是再建立一个数组,然后把字符串倒着copy到里面去.
空间最佳吗?没想到什么特别好的办法.Top
49 楼itlive（好友(暂别ＶＢ版)）回复于 2005-05-24 18:36:49 得分 0
可以用异或的方法，具体的没想太好Top
50 楼alec626（月吻长河Blog:spaces.msn.com/filebase）回复于 2005-06-02 00:04:45 得分 0
腾讯又不做嵌入式，这点效率的提高没多大意思吧
依我看，代码的可读性、可维护性更重要！Top
51 楼viewpl（下了军令状，明年泡不到mm就提着向下小JJ回家叩见祖宗）回复于 2005-06-02 00:44:12 得分 0
面试题可以使用c++标准库吗
#include <iostream>
#include <stack>
#include <string>
int main(int argv, char * argc[])
{
using namespace std;
stack<char> stk;
char str[10];
strcpy(str, "12345");
cout << "Begin convert :\n";
cout << "str : " << str << endl;
char * lp = NULL;
lp = str;
int i = 0;
while((*lp != '\0')
&& (i < 10))
{
stk.push(*lp);
++lp;
++i;
}
i = 0;
while((!stk.empty())
&& (i < 10))
{
str[i] = stk.top();
stk.pop();
++i;
}
cout << "After convert :\n";
cout << "str : " << str << endl;
return 0;
}
Top
52 楼flyinger（风往北吹）回复于 2005-06-02 10:39:00 得分 0
面试失败,但是还是想知道答案!Top
53 楼cutestar（猪哥靓）回复于 2005-06-02 11:24:01 得分 0
把你能想到的解决方法先写出来，然后再到网上去找找（主要是找源代码，LINUX下的应该有），最后进行比较，很有可能1和2的答案是同一种算法。
得到结果固然重要，但解决问题的过程也是很重要的。
另外，在反转的同时要注意双字节的问题，如“C编程”，反转后为“程编C”(根据要求和算法定，但要考虑)。
Top
54 楼kurt8276（扑火蝶）回复于 2005-06-02 11:26:41 得分 0
用栈Top
55 楼jlkzzh（一阵风）回复于 2005-06-02 11:36:57 得分 0
只要注意
c-style字符串的结束符'\0'来保存
效率高要考虑其他变量
空间小要从本身出发Top
56 楼ywhimis（醉人）回复于 2005-06-02 11:48:30 得分 0
可以用 STL的算法吗?
string strtmp( szBuf );/*szBuf是C的字符串*/
reverse( strtmp.begin() , strtmp.end() );
strcpy( szBuf, strtmp.data() );Top
57 楼UnrealImagecoffee（micr - dev）回复于 2005-06-02 14:38:54 得分 0
可以用 STL的算法吗?
string strtmp( szBuf );/*szBuf是C的字符串*/
reverse( strtmp.begin() , strtmp.end() );
strcpy( szBuf, strtmp.data() );
// goodTop
58 楼wosirius（神经第六）回复于 2005-06-02 14:54:28 得分 0
markTop
