游程长度编码（RLE）解题报告

这个问题要求我们实现一种简单的游程长度编码（RLE），将输入字符串按照特定规则转换为编码形式。让我们详细分析解题思路和代码实现。

编码规则理解

根据题目描述，编码规则可以总结为：

1. 连续重复字符序列（2-9个相同字符）：

   • 编码为两位字符：第一位是重复次数（2-9），第二位是重复的字符本身。
   • 例如：AAAAA（5个A）编码为5A。

2. 连续重复字符序列（超过9个相同字符）：

   • 先编码前9个字符为9X，剩余部分继续按规则处理。
   • 例如：AAAAAAAAAA（10个A）编码为9A1A。

3. 无连续重复字符的序列：

   • 编码格式为1 + 转义后的原序列 + 1。
   • 若原序列中包含字符1，则需转义为11。
   • 例如：123编码为11231，A1B编码为1A11B1。

解题思路

代码实现的核心思路是遍历输入字符串，识别连续重复字符序列和非连续重复字符序列，并按照规则进行编码：

1. 遍历输入字符串：使用指针i遍历字符串中的每个字符。
2. 统计连续重复字符：对于每个字符，统计其连续重复次数cnt。
3. 处理连续重复字符：
   • 若重复次数cnt >= 2，按规则1或规则2编码。
   • 若重复次数cnt == 1，按规则3编码。
4. 处理字符1的转义：在非连续重复序列中，遇到字符1时将其转义为11。

代码分析

以下是完整的代码实现：

#include <stdio.h>
#include <string.h>
using namespace std; // 保留，尽管这里主要使用C标准库

int main()
{
    char str[10000];
    int len, i, cnt, s, e;
    while(fgets(str, sizeof(str), stdin) != NULL)
    {
        // 移除行末的换行符
        len = strlen(str);
        if (len > 0 && str[len-1] == '\n') {
            str[--len] = '\0';
        }
        
        i = s = e = 0;
        while(1)
        {
            cnt = 1;
            // 统计当前字符连续重复的次数（最多9次）
            while(i + cnt < len && str[i] == str[i+cnt] && cnt < 10)
                cnt++;
                
            if(i >= len)
            {
                // 处理序列末尾的1
                if(e)
                    printf("1");
                break;
            }
            else if(cnt != 1)
            {
                // 处理连续重复字符序列
                s = 0;
                if(e)
                {
                    printf("1");
                    e = 0;
                }
                printf("%d%c", cnt, str[i]);
            }
            else
            {
                // 处理非连续重复字符
                e = 1;
                if(!s)
                {
                    printf("1");
                    s = 1;
                }
                printf("%c", str[i]);
                // 转义字符1
                if(str[i] == '1')
                    printf("%c", str[i]);
            }
            i += cnt;
        }
        printf("\n");
    }
 
    return 0;
}

关键部分解析

1. 输入处理：

   • 使用fgets读取输入行，避免gets函数的缓冲区溢出风险。
   • 移除行末的换行符，确保其不参与编码。

2. 连续重复字符统计：

   • 内层while循环统计当前字符连续重复的次数cnt，最多统计到9次。

3. 状态变量：

   • s：标记是否已输出非连续序列的起始标记1。
   • e：标记是否处于非连续序列中。

4. 编码处理：

   • 当cnt >= 2时，直接输出cnt和重复字符。
   • 当cnt == 1时，输出起始标记1，然后输出字符本身，若字符为1则再输出一个1进行转义。

这个实现通过一次遍历高效地完成了编码任务，时间复杂度为O(n)，其中n是输入字符串的长度。