[C++] 移除字符串中的所有空格字符(今天的面试题)

陪她去流浪 桃子 2017年02月10日 编辑 阅读次数:4166

今天面试遇到的题。

原题大概:用 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';
}

真是尴尬,囧。

标签:C++ · 字符串