C++ Junior面试题：仅用char指针压缩字符序列的函数

Question

前几天我在面试，我要实现以下功能：

char* Compress (char * text);

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

例如，如果输入文本为“11112222333344411”，在将其传递给 Compress 函数后，returned 值为：“12341”，或者如果文本输入为："aaAbbBBcCCa" -- -> return：aAbBcCa

我不确定我在这里是否正确地完成了所有操作（使用内存处理），所以任何建议都很好。我每次都删除 temp 的值是否正确？此外，如果有更简单的方法来实现此功能（当然不使用标准库函数），我将非常高兴看到它。

#include <iostream>

char* Compress(char* text) {

    char* temp;
    char* _compText;

    int size = 1;

    _compText = nullptr;

    for (size_t i = 0; text[i] != '[=11=]'; ++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] = '[=11=]';
            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

Does my code have memory leak?

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

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

Am I doing it right that I delete the value of temp everytime?

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

Answer 2

函数最初实现不正确。

函数的类型是

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

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

可以按照演示程序中所示定义函数。

#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';
}

它的输出是

或者函数也可以这样看

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)
      |                                ~~^~~~~~~~

而您的函数 returns nullptr 用于空字符串。这看起来逻辑上不一致。而且这个功能效率很低。:)

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

C++ Junior面试题：仅用char指针压缩字符序列的函数

C++ Junior interview question: function to compress a character sequence with only char pointers

c++

function

compression

definition

c-strings