C++ 初级面试问题:仅使用字符指针压缩字符序列的功能

Question

前

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

char* Compress (char * text);

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

例如，如果输入文本在传递给 Compress 函数后为"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] != ''; ++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] = '';
            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 的值是否正确？

就内存泄漏而言，是的，您确实需要删除每个分配。但是在每次迭代时重新分配内存是不必要的，而且速度非常慢。事实上，似乎不需要任何动态分配(参见弗拉德的回答(。