java - 压缩和解压缩字符串

Answer 1

至少，一个简单的反向扫描确实为编码部分提供了一个（看似）好的解决方案。我正在从右到左进行一次扫描，并用出现计数覆盖字符串的部分。

char * enc(char * ip)
{
    int r,op;
    int l=strlen(ip);
    r=l-1;
    char curr;
    op=r;
    int curr_count=1,mod_curr_count;
    while(r>=0)
    {
        curr=ip[r];

        while(ip[--r]==curr)
        {

            curr_count++;
        }
        if(curr_count!=1)
        {
            while(curr_count)
            {
            mod_curr_count=curr_count%10;
            ip[op--]=(char)(mod_curr_count+48);
            curr_count/=10;
            }
            ip[op--]=curr;
            curr_count=1;

        }
        else
        {
        ip[op--]=curr;
        }
    }

    ip=ip+op+1;
    return ip;
}

输入： aaaaaaaaaaabbbfffffffffffffffqqqqqqqqqqqqqqqqqccccpoii

输出： a12b3f15q18c4poi2

Answer 2

To do an in-place encoding, the encoded string must never be longer than the original string. Suppose we assume the following encoding rules:

• No numeric digits in the original string (so no count delimiter characters are needed)
• A run length of 1 is never explicitly coded (so abc remains abc)

I believe that with these assumptions, a run-length encoding is not ambiguous and will never be longer than the string itself. Then the following algorithm (pseudocode) should do the job of encoding in place:

currentChar ← string[0]
nextOutputPos ← 1
nextReadPos ← 1
count ← 1
while (nextReadPos < length of string) {
    nextChar ← string[nextReadPos++];
    if (nextChar == currentChar) {
        count++;
    } else {
        if (count > 1) {
            write (count as a string) to string at position nextOutputPos
            nextOutputPos ← nextOutputPos + (length of count as a string)
        }
        string[nextOutputPos++] ← currentChar ← nextChar;
    }
}

At the end, the encoded string is contained in the half-open range [0, nextOutputPos) of string.

Answer 3

这是 Java 中使用正则表达式的一种可能性：

String str = "aaabbbc";  // string to be encoded

StringBuilder sb = new StringBuilder();  // to hold encoded string

for (String s : str.split("(?<=(.))(?!\\1)")) {
    sb.append(s.charAt(0));
    if (s.length() > 1) // only append length if it's > 1
        sb.append(s.length());
}

System.out.println(sb.toString());

a3b3c