C++初级面试题: function to compress a character sequence with only char pointers

Question

前几天我参加了一次工作面试，我需要实现以下功能:

char* Compress (char * text);

规则还不允许您使用标准库函数，如 strlen、strcpy、string 等...因此该函数必须压缩给定的字符序列。

例如，如果输入文本为“11112222333344411”，则将其传递给压缩函数后，返回值为:“12341”，或者如果文本输入为:“aaAbbBBcCCa” ---> 返回:aAbBcCa

我不确定我在这里是否正确执行了所有操作(使用内存处理)，因此任何建议都会很棒。我每次都删除 temp 的值是否正确？另外，如果有一种更简单的方法来实现这个函数(当然不使用标准库函数)我会很高兴看到它。

#include <iostream>

char* Compress(char* text) {

    char* temp;
    char* _compText;

    int size = 1;

    _compText = nullptr;

    for (size_t i = 0; text[i] != '\0'; ++i)
    {
        if (text[i] != text[i + 1]) {

            ++size;

            temp = _compText;

            _compText = new char[size];

            for (size_t j = 0; j < size-2; ++j)
            {
                _compText[j] = temp[j];
            }

            _compText[size-2] = text[i];
            _compText[size-1] = '\0';
            delete[] temp;
        }

    }

    return _compText;
}

int main()
{
    char t[] = "111122222233333444444555555111";

    char* compedT;

    std::cout << "Before:\n";

    std::cout << t;

    compedT = Compress(t);

    std::cout << "\nAfter: \n";

    std::cout << compedT;

    delete[] compedT;

    return 0;
}

Answer 1

该函数最初实现不正确。

函数的类型是

char* Compress (char * text);
                ^^^^^^^

即它的参数不是const char *，这意味着该函数应该就地更新源字符串并返回指向其第一个字符的指针。无需动态分配内存来执行任务。

可以按照演示程序中所示的方式定义该函数。

#include <iostream>

char * Compress( char *s )
{
    for ( char *p = s, *q = s; *q; )
    {
        if ( *++q != *p ) *++p = *q;
    }

    return s;
}

int main()
{
    char s[] = "11112222333344411";

    std::cout << Compress( s ) << '\n';
}

它的输出是

12341

或者该函数也可以如下所示

char * Compress( char *s )
{
    for ( char *p = s, *q = s; *q; )
    {
        if ( ( *++q != *p ) and ( ++p != q ) ) *p = *q;
    }

    return s;
}

对于您的函数实现，您应该阅读警告，例如

warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |             for (size_t j = 0; j < size-2; ++j)
      |                                ~~^~~~~~~~

并且您的函数返回空字符串的 nullptr 。这看上去在逻辑上是不一致的。而且这个功能效率很低。:)

并且不要使用以下划线开头的名称。