将字符串s倒置的各种方法:说什么微软面试题,其实在K&R书上早
发布时间:2020-12-13 23:13:25 所属栏目:百科 来源:网络整理
导读:缘由 这道题总是以微软的面试题闪现在各位眼前,我觉得这样不好,总是面试题,面试题的,功利性太强。忘了面试、笔试吧,我就是享受编程的过程。 这道题在K&R的书上有,无论是例子的方式,还是问题的方式,倒不是这个倒置问题一定要作为一个题出现,而是实
缘由这道题总是以微软的面试题闪现在各位眼前,我觉得这样不好,总是面试题,面试题的,功利性太强。忘了面试、笔试吧,我就是享受编程的过程。 这道题在K&R的书上有,无论是例子的方式,还是问题的方式,倒不是这个倒置问题一定要作为一个题出现,而是实际在项目中需要。
最简单的方法
用将第一个和最后一个交换,然后第一个+1,最后一个减1,直到在中间相遇停止即可。
代码如下: /* * 这是最简单的方法也最容易想到的方法 * 将第一个和最后一个元素逐一对调 *K&R P51 */ void reverseV1(char s[]) { int c,i,j;//实际上用int类型的c和用char类型的c都可以,但是书中为什么如此? for(i=0,j=strlen(s)-1;i<j;i++,j--){ c=s[i]; s[i]=s[j]; s[j]=c; } } 自己所写的递归
我自己写了一个,但是感觉效果不是特别好,调用myStrReverse传入数组即可:
void myreverse(char *new,char *old,int length) { if(*(old+1)!=' '){ myreverse(new,(old+1),length-1); } *(new+length-1)=*old; } /* * 这是我自己写的,确实完成了要求,但是使用了额外的空间,就是与所求数组一样长的空间 * 而且也算是使用了递归 */ void myStrReverse(char *old){ int length=sizeof(old)/sizeof(char); char new[length+1]; new[length+1]=' '; myreverse(new,old,length); strcpy(old,new); } 别人写的优秀的递归
我写的太烂了。
// 对字符串s在区间left和right之间进行逆序,递归法 void recursionReverse( char* s,int left,int right ) { if(left >= right) return s ; char t = s[left] ; s[left] = s[right] ; s[right] = t ; recursionReverse(s,left + 1,right - 1) ; } int main(){ char s[]="abcd"; recursionReverse(s,strlen(s)-1); printf("%sn",s); } 使用异或节省空间
这个让我很受教。
/** * 不使用任何外部变量即完成两个字符(或者整数)的交换,这是一个经典问题 * */ char* reverseV2(const char* str) { char *tmp=(char *) malloc(tmp + strlen(str)+1);//如果是C++的话,这里倒是可以用new关键字 strcpy(tmp,str); char* ret = tmp; char* p = tmp + strlen(str) - 1; while (p > tmp) { *p ^= *tmp; *tmp ^= *p; *p ^= *tmp; --p; ++tmp; } return ret; } 类似的方法还有使用加减
真的让人感到很神奇啊,我真的要找个人把
为什么可以这样问清楚!!!
char* reverseV2a(const char* str) { char *tmp=(char *) malloc(tmp + strlen(str)+1);//如果是C++的话,这里倒是可以用new关键字 strcpy(tmp,str); char* ret = tmp; char* p = tmp + strlen(str) - 1; while (p > tmp) { *p = *p + *tmp; *tmp = *p - *tmp; *p = *p - *tmp; --p; ++tmp; } return ret; } 最复杂的方法
这个方法很没有意思,我个人觉得,把问题弄得如此复杂,调reverseV3传入数据,即可完成倒置。
static void swap(char *a,char *b,size_t n) { while (n--) { *a ^= *b;//最好调试着看 *b ^= *a;//这样的做法有点高端哦 *a ^= *b;// a++; b++; } } void my_memrev(char *s,size_t n) { switch (n) { case 0: case 1: break; case 2: //2和3情况一样 case 3: swap(s,s + n - 1,1); break; default: my_memrev(s,n / 2); my_memrev(s + ((n + 1) / 2),n / 2); swap(s,s + ((n + 1) / 2),n / 2); break; } } /************************************************************************/ /* 这是一种非常复杂的方法,极力不推荐 */ /************************************************************************/ void reverseV3(char *s) { char *p; for (p = s; *p; p++) ; my_memrev(s,(size_t)(p - s));//这样也能得到数组长度?两个char指针想减 } 其他问题总结:strcpy的段错误问题
下段代码要发生段错误,为什么:
int main(){ char s[]="abcd"; char *tmp; strcpy(tmp,s); } 答: char * str = (char *) malloc(100); 异或的方式交换两个字符或数字异或的方式交换两个字符,可以节省空间,没有使用额外的一个字符就让两个字符发生了置换,这样的做法同样适用于数字: int main(){ char a='a'; char b='b'; a ^= b; b ^= a; a ^= b; printf("a:%c b:%c",a,b); }打印结果: a:b b:a
但是我还是没有搞清其原理。
参考:除了我自己的总结以外,还有这位同志的总结非常好:
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |