C++初级面试问题:只使用字符指针压缩字符序列的函数

Question

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

char* Compress (char * text);

规则还规定，不允许使用标准libary函数，如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。这在逻辑上似乎不一致。而且这个功能效率很低。)

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

Answer 2

我的代码有内存泄漏吗？

据我所见，没有；没有内存泄漏。

也就是说，使用裸的拥有指针很难发现内存泄漏。它们是一个糟糕的设计选择，特别是在将所有权转移到功能之外时。至少，函数声明附近应该有一个注释，应该记录调用方必须如何清理分配。如果需要动态数组，更好的解决方案是使用容器。

每次删除temp的值是正确的吗？

就内存泄漏而言，是的，您确实需要删除每个分配。但是，在每次迭代中重新分配内存是不必要的，而且非常缓慢。事实上，似乎不需要任何动态分配(见Vlad的答案)。