c++ - 使用 C++ 的就地字符串压缩问题

Question

嗨，我正在尝试解决这个面试问题:

String Compression: Implement a method to perform basic string compression using the countsof repeated characters. For example, the string "aabcccccaaa" would become "a2b1c5a3". If the"compressed" string would not become smaller than the original string, your method should returnthe original string. You can assume the string has only uppercase and lowercase letters (a - z).

通过创建一个新字符串或打印结果很容易解决这个问题，但我正在尝试提出一个就地解决方案。基本上，我使用的是 string::erase()和 string::insert()功能。首先，我计算出现的字符数并将其存储在 int 中。变量 count ，然后如果一个数字被重复，我只需删除它并插入 count那里的值(value)。如果没有重复一个字符，那么我只需插入 1，因为默认值 count设置为 1。这是代码:

string stringCompression(string A) {
    int index = 0; char character = ''; int count = 1; string convertInt = ""; int initial_index = 0, length = A.length();
    do {
        character = A[index];
        initial_index = index;
        index++;
        while (A[index] == character)
        {
            count++;
            index++;
        }
        convertInt = to_string(count);
        if (count == 1)
        {
            A.insert(index, convertInt);
            index++;
        }
        else
        {
            A.erase((initial_index+1), (index-1));
            A.insert(initial_index+1, convertInt);
            index = initial_index + 2;
            count = 1;
        }
    } while (A[index]!='\0');
    return A;
}

int main()
{
    cout << stringCompression("aabcccccaaa");
}

输出:

a2b1c5

预期结果为 "a2b1c5a3" .但最后一组3 a ' 没有出现，我尝试调试它。根据我得到的值，这段代码应该可以工作。但奇怪的是，当我调试时， erase()函数自动删除最后 3 个 a的即使 Index 的值和 initial_index似乎是正确的。有人可以解释为什么会这样吗？

Answer 1

主要问题:错误使用erase()
这是一个非常讨厌的问题: string::erase() 有几个签名。有一个带有迭代器的表单，您可以在其中为要删除的区域提供开始和结束迭代器。你想用这个。
但实际上，您不使用迭代器，而是使用位置。有职位，erase()使用起始位置和 长度 .所以不要只删除 4 d如您所料，在位置 5 和 9 之间，它将从位置 5 开始删除 9 个字符。所以基本上，在您的示例中，它会删除​​字符串的其余部分。
简单地纠正它:

        A.erase((initial_index+1), count-1);

其他不相关的问题
问题2:要压缩的字符串可能为空!
所以而不是 do...while(...);假设总是有第一个字符的循环，使用普通 while(...)...环形。
问题3:压缩，而不是扩展。要求里面有!
你忽略了这个要求:

if the "compressed" string would not become smaller than the original string, your method should return the original string.

如果您尝试使用不可压缩的字符串来编写代码，则会得到更长的字符串:

stringCompression("abcde")    --->  "a1b1c1d1e1"

如果你想遵守，你不应该添加 count对于任何非重复字符。
您的 if...else...将简化为:

    if (count > 1)
    {
        convertInt = to_string(count);
        A.erase((initial_index+1), count-1);
        A.insert(initial_index+1, convertInt);
        index = initial_index + convertInt.length();
        count = 1;
    }

问题 4:永远不要超过字符串的长度
C++ 字符串不是 C 字符串 : 你不能在一个字符结束后访问它来检查它是否为空!顺便说一句，不能保证 c++ 字符串以空字符结尾。此外，一个字符串可以完美地包含一个非终端的空字符。
因此，对于 while 循环，您始终需要检查 inde 是否在界限内。最后，你得到:

string stringCompression(string A) {
    int index = 0; char character = ' '; int count = 1; string convertInt = ""; int initial_index = 0, length = A.length();
    while (index <A.length()) {
        character = A[index];
        initial_index = index;
        index++;
        while (index<=A.length() && A[index] == character)
        {
            count++;
            index++;
        }
        if (count > 1)
        {
            convertInt = to_string(count);
            A.erase((initial_index+1), count-1);
            A.insert(initial_index+1, convertInt);
            index =  initial_index+convertInt.length()+1;
            count = 1;
        }
    } 
    return A;
}

Online demo
杂项备注

如果您转换字符串，请始终动态获取长度，因为您在函数开头获得的长度很快就会过时；-)

删除和插入将复制每个尾随字符两次。考虑到您不再膨胀字符串，更好的方法是只删除必须删除的内容，并用计数替换剩余的字符。您将性能翻倍。*