今天面试遇到的题。
原题大概:用 C++ 完成下面的函数,实现移除字符串中的所有空格字符。(该字符串长度可能非常大,不应分配过多内存,且不应该出现过多大块大块的内存拷贝。)
原型:
void removeSpaces(char* str) { }
一开始觉得这题并没有什么难度,只是后来看到那个“大块大块的内存拷贝”,我实在没想到怎样的写法会出现上述情况。
把我搞得有点懵了,于是竟然写下了下面这个看似特别复杂、其实也特别复杂的代码:
void removeSpaces(char* str) { if(!str) return; char* p = str; char* q = str; while(*q) { if(*q != ' ') { if(p == q) { while(*p && *p != ' ') { p++; } q = p; } else { while(*q && *q != ' ') { *p++ = *q++; } } } else { while(*q && *q == ' ') { q++; } } } *p++ = '\0'; }
上面的代码能正常工作,并没有问题,但就是一慌之下,竟然写出了如此冗余的代码,感觉我写了那么多的字符串解析,协议解析,词法分析。。。真是没派上用场,尴尬。。。
后面面试官大哥提醒我,其实只需要一个循环就可以完成了,不需要这么多的 while。当时挺懵的,面试结束后,一想,还真是。我估计我当时是因为前面一些题答得不怎么好,影响了这个题的答题。
后面我再想,为什么当时我写得那么冗余,我估计是那块“大块大块”干扰了我。。。我看了第2个 while 处的代码,发现其只有一个作用:当字符串不包含空格时,能够避免内存拷贝,能达到更高的效率,再无其它优点。
面试官大哥期待的代码:
void removeSpaces(char* str) { size_t n = 0; for(size_t i = 0; str[i]; i++) { if(str[i] != ' ') { str[n++] = str[i]; } } str[n] = '\0'; }
真是尴尬,囧。