c++ - 计算 RLE 压缩字符串所需的空间

Question

我正在编写面试工作簿并正在做这个问题:使用重复字符的计数实现一个函数来压缩字符串(aabcccccaaa 将变为 a2blc5a3)。如果“压缩”不小于原始字符串，则返回原始字符串。

我找到的解决方案首先计算压缩字符串的大小。我试过通过这个辅助函数进行跟踪，但不理解这一行的逻辑。 任何帮助破译都会很棒!:

大小 = 大小 + 1 + std::to_string(count).length();

count 是一个整数，表示重复字符的数量 在 C++11 中，to_string 允许您将 append int 附加到字符串。所以，A+1 就是 A1。

更好的解决方案:

int countCompression(const string& str)
{
    if (str.length() == 0)
        return 0;

    char prev = str[0];
    int size = 0;
    int count = 1;

    for (int i = 1; i < str.size(); i++)
    {
        // Repeated char
        if (str[i] == prev)
            count++;
        // Unique char
        else
        {
            prev = str[i];
            size = size + 1 + std::to_string(count).length();
            count = 1;
        }
        //cout << "The size in iteration " << i << " is now " << size << endl;
    }
    size = size + 1 + std::to_string(count).length();
    //cout << "The final size is: " << size << endl;
    return size;
}

顺便说一句，我写了这个解决方案，但它之后会检查大小。我认为这会浪费空间:

#include <iostream>
#include <string>

std::string compress(const std::string &str)
{
    std::string comp;
    char prev = str[0];
    int count = 1;
    for (int i = 1; i < str.size(); i++)
    {
        if (prev == str[i])
            count++;
        else
        {
            comp += prev;
            comp += std::to_string(count);
            prev = str[i];
            count = 1;
        }
    }
    comp += prev;
    comp += std::to_string(count);
    if (comp.size() > str.size())
        return comp;
    else
        return str;
}

Answer 1

size = size + 1 + std::to_string(count).length();

此行将重复字符本身的 size 递增 1(a、b、c、等)加上指定字符重复次数的数字 count 的字符串表示形式的 length()。

因此:

对于aa，size加2:

size = size + 1 + to_string(2).length()

对于 b，size 加 2:

size = size + 1 + to_string(1).length()

对于ccccc，大小加2:

size = size + 1 + to_string(5).length()

对于aaa，size加2:

size = size + 1 + to_string(3).length()

所以最终压缩后的size是8.

话虽如此，试试这个实现:

std::string compress(const std::string& str)
{
    std::string::size_type len = str.length();
    if (len > 1) // compressed size is 2 chars minimum
    {
        std::ostringstring compressed;

        char ch, prev = str[i];
        int count = 1;

        for (int i = 1; i < len; ++i)
        {
            ch = str[i];
            if (ch == prev) {
                // Repeated char
                ++count;
            }
            else {
                // Unique char
                compressed << prev << count;
                prev = ch;
                count = 1;
            }
        }

        // output the final pending char count
        compressed << prev << count;

        std::string result = compressed.str();
        if (result.length() < len)
            return result;
    }

    return str;
}

或者:

std::string::size_type compressSize(const std::string& str)
{
    std::string::size_type len = str.length();
    if (len > 1) // compressed size is 2 chars minimum
    {
        std::string::size_type size = 0;

        char ch, prev = str[i];
        int count = 1;

        for (int i = 1; i < len; ++i)
        {
            ch = str[i];
            if (ch == prev) {
                // Repeated char
                ++count;
            }
            else {
                // Unique char
                size += (1 + std::to_string(count).length());
                prev = ch;
                count = 1;
            }
        }

        // output the final pending char count
        size += (1 + std::to_string(count).length());

        if (size < len)
            return size;
    }

    return len;
}

std::string compress(const std::string& str)
{
    std::string::size_type len = str.length();

    if (compressSize(str) >= len)
        return str;

    std::ostringstring compressed;
    char ch, prev = str[i];
    int count = 1;

    for (int i = 1; i < len; ++i)
    {
        ch = str[i];
        if (ch == prev) {
            // Repeated char
            ++count;
        }
        else {
            // Unique char
            compressed << prev << count;
            prev = ch;
            count = 1;
        }
    }

    // output the final pending char count
    compressed << prev << count;

    return compressed.str();
}

或者:

bool canCompress(const std::string& str)
{
    std::string::size_type len = str.length();
    if (len <= 1) // compressed size is 2 chars minimum
        return false;

    std::string::size_type size = 0;

    char ch, prev = str[i];
    int count = 1;

    for (int i = 1; i < len; ++i)
    {
        ch = str[i];
        if (ch == prev) {
            // Repeated char
            ++count;
        }
        else {
            // Unique char
            size += (1 + std::to_string(count).length());
            if (size >= len) {
                return false;
            }
            prev = ch;
            count = 1;
        }
    }

    // output the final pending char count
    size += (1 + std::to_string(count).length());

    return (size < len);
}

std::string compress(const std::string& str)
{
    if (!canCompress(str))
        return str;

    std::ostringstring compressed;

    char ch, prev = str[i];
    int count = 1;

    std::string::size_type len = str.length();
    for (int i = 1; i < len; ++i)
    {
        ch = str[i];
        if (ch == prev) {
            // Repeated char
            ++count;
        }
        else {
            // Unique char
            compressed << prev << count;
            prev = ch;
            count = 1;
        }
    }

    // output the final pending char count
    compressed << prev << count;

    return compressed.str();
}