当前位置: 代码迷 >> 综合 >> PAT 乙级 1078 字符串压缩与解压
  详细解决方案

PAT 乙级 1078 字符串压缩与解压

热度:6   发布时间:2023-12-28 03:00:29.0

文本压缩有很多种方法,这里我们只考虑最简单的一种:把由相同字符组成的一个连续的片段用这个字符和片段中含有这个字符的个数来表示。例如 ccccc 就用 5c 来表示。如果字符没有重复,就原样输出。例如 aba 压缩后仍然是 aba

解压方法就是反过来,把形如 5c 这样的表示恢复为 ccccc

本题需要你根据压缩或解压的要求,对给定字符串进行处理。这里我们简单地假设原始字符串是完全由英文字母和空格组成的非空字符串。

输入格式:

输入第一行给出一个字符,如果是 C 就表示下面的字符串需要被压缩;如果是 D 就表示下面的字符串需要被解压。第二行给出需要被压缩或解压的不超过 1000 个字符的字符串,以回车结尾。题目保证字符重复个数在整型范围内,且输出文件不超过 1MB。

输出格式:

根据要求压缩或解压字符串,并在一行中输出结果。

输入样例 1:

C
TTTTThhiiiis isssss a   tesssst CAaaa as

输出样例 1:

5T2h4is i5s a3 te4st CA3a as

输入样例 2:

D
5T2h4is i5s a3 te4st CA3a as10Z

输出样例 2:

TTTTThhiiiis isssss a   tesssst CAaaa asZZZZZZZZZZ

一开始的想法便是遍历字符串,之后根据C与D进行分类。

先说C,C是压缩字符,即遍历字符串,若 碰见s[i]与s[i+1]相等,即更新计数变量,使得字符被正确地统计,统计完成后若s[i]!=s[i+1]则要将计数变量count与字符存进新的字符数组中。输出字符数组时,count为1是便不必输出。

D是释放字符,同样也是遍历字符串,先读取数字,将对应的字符存入数组中。若遇见了字符不是数字的,则停止读取数字,将数字计算出来。同时在待输出的字符数组内,通过for循环记录下字符。若数字为0时,即只有1个字符。将这些按要求存完后,将其输出。

但存在较大的问题,测试点4错误以及测试点5段错误。似乎发现了一点可以改进的地方,即对于字符串这一连续的读取,不同于数组这些间断的读一个输出一个,而是连续读连续输出,所以,是否可以在一个for循环内读取字符,然后每读取一个或几个便给予相应的反应(即输出)?

在一个for循环内读取字符的想法如下,定义一个计数的count,在for循环内count++,当某个字符不等于其后一个字符时,需要停止count的增加,将count与这个字符同时输出。如果count等于1时则不输出。关于解压,一开始的想法是将数字的 字符存入某个字符数组中,后由string类函数的影响决定存放在一个string类的字符串c中,初始化为“”。若出现一个数字字符便添加,若是字母字符,用reverse(c.begin(),c.end())函数将字符串倒置。通过for循环读字符串,记录下数字,最后相加得出结果。若字符串c是空串,即没有字符,计算得出的数字为0,将0赋值为1即可。

可能是重新开了一个字符串会导致内存超限,直接输出可解决问题。

代码如下:

#include <bits/stdc++.h>using namespace std;int main()
{char a;cin>>a;getchar();string b;getline(cin,b);int l=b.length();int i,j,cishu,sum;int count=0;string c="";if(a=='C'){count=0;for(i=0;i<l;i++){count++;if(b[i]!=b[i+1]){if(count!=1){cout<<count;}cout<<b[i];count=0;}}}//相当于压缩else if(a=='D'){for(i=0;i<l;i++){if(b[i]>='0'&&b[i]<='9'){c+=b[i];}else if(b[i]<'0'||b[i]>'9'){reverse(c.begin(),c.end());cishu=1;sum=0;for(j=0;j<c.length();j++){sum+=((int)c[j]-(int)'0')*cishu;cishu=cishu*10;}if(sum==0){sum=1;}for(j=0;j<sum;j++){cout<<b[i];}c="";}}}//相当于解压return 0;
}