当前位置：首页 > article >正文

每日一题（三）：压缩字符串（行程长度编码）

article 2025/1/14 10:16:19

目录

一、题目

科普部分（题目背景）

Run-length encoding(行程长度编码)

二、题目分析

（一）明确需求

（二）分析思路

三、将思路转换为程序

C++代码

C代码

四、总结

一、题目

实现一个算法来压缩字符串。压缩要求如下：

1.需要判断压缩是否能够节省空间，仅在压缩后的字符串比原字符串短时进行压缩。

2.压缩的格式是将连续相同字符替换为字符 + 数字形式，例如 "AAABCCDDDD" 变为 "A3BC2D4"。

输入描述：

输入一行，表示要压缩的字符串，长度不超过500。字符串中一次性重复字符不超过9个。

输出描述：

输出一行。若输入的字符串可压缩，则输出压缩后的字符串，否则输出 NO。

科普部分（题目背景）

在讲这道题之前，博主先进行一个知识科普：

Run-length encoding(行程长度编码)

行程长度编码是一种用于压缩字符串中某一些重复一遍又一遍的长字符序列。大体意思便是，用重复的字符加上重复数替代一长串有序的重复的字符。为了表明或者是指示这些经过行程长度编码进行处理的字符串，我们会在它们的开头加上一个提示符号（flag）。例如：一部分DNA的序列是“GGGGGAAAAAACCCCC”。使用行程长度编码和提示符号（flag）“#”，它可以表示为“#G5#A6#C5”。

通过对行程长度编码的介绍，我想大家都看出来了，本次的题目的本质就是对行程长度编码的使用和扩展。唯一不同的便是本题没有加上提示符号。

二、题目分析

（一）明确需求

根据题目要求，我们需要设计一个算法来实现对字符串的压缩。需要特别注意的是题目要求中说了要对压缩是否能够节省空间进行判断。也就是说一次性重复字符数至少要超过2，才能进行压缩。

其次根据描述，我们这次需要设置一个大小为500的字符数组来接收输入数据，为了便于输出我们也需要使用同样大小的字符数组进行输出。（通过增加部分空间复杂度，来提升时间复杂度）

（二）分析思路

为了解决这一问题，对于要进行压缩的字符数组，我们可以使用两个变量a、b来标识数组下标，a代表的下标指向第一个重复的字符，b代表的下标从该位置开始向前遍历，每遍历到一个重复字符，进行一次计数。如果遍历到的是不同的字符，则令a=b。同时在另一个字符数组中记录相应信息。

那么我们因该如何进行记录呢？根据计数值来进行判断，如果用count变量来代表字符重复的个数，首先我们将可能重复的字符放入字符数组，然后按上面形式进行遍历，最终当count为1时代表只有一个字符，这时不用管；当count为2时代表有两个一样的字符，则在下一个位置重复记录上一字符（代表不需要压缩，因为不能减少空间）；当count大于2时，则将下一个位置记录为重复的个数。

三、将思路转换为程序

使用C与C++模拟实现：

C++代码

#include <iostream>
#include <string.h>
using namespace std;
int main()
{
    char str1[500] = { 0 };
    char str2[500] = { 0 };
    cin >> str1;
    int len1 = strlen(str1);
    int x = 0;
    int a = 0;
    int b = 0;
    while (a <= len1)
    {
        int count = 0;
        while (str1[b] == str1[a])
        {
            b++;
            count++;
        }
        str2[x++] = str1[a];
        if (count > 2)
        {
            str2[x++] = count + '0';
        }
        else if (count == 2)
        {
            str2[x++] = str1[a];
        }
        a = b;
    }
    int len2 = strlen(str2);
    if (len1 == len2)
    {
        cout << "NO";
    }
    else
    {
        cout << str2;
    }
    return 0;
}

C代码

#include <stdio.h>
#include <string.h>

int main()
{
    char str1[500] = { 0 };
    char str2[500] = { 0 };
    scanf("%s", str1);
    int len1 = strlen(str1);
    int x = 0;
    int a = 0;
    int b = 0;
    while (a <= len1)
    {
        int count = 0;
        while (str1[b] == str1[a])
        {
            b++;
            count++;
        }
        str2[x++] = str1[a];
        if (count > 2)
        {
            str2[x++] = count + '0';
        }
        else if (count == 2)
        {
            str2[x++] = str1[a];
        }
        a = b;
    }
    int len2 = strlen(str2);
    if (len1 == len2)
    {
        printf("NO");
    }
    else
    {
        printf("%s", str2);
    }
    return 0;
}