「PAT乙级真题解析」Basic Level 1078 字符串压缩与解压 (问题分析+完整步骤+伪代码描述+提交通过代码)
- 题设要求按照给定的方式对字符串进行压缩,以及对给定压缩字符串按照约定进行解压。 - 关于如何压缩的方式, 题设已经给出, 所以仍然是模拟压缩的过程.
#算法#数据结构#需求分析#pat考试#c语言
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
PAT (Basic Level) Practice 1078 字符串压缩与解压
问题分析
- 题设要求按照给定的方式对字符串进行压缩,以及对给定压缩字符串按照约定进行解压。
- 关于如何压缩的方式, 题设已经给出, 所以仍然是模拟压缩的过程.
如何压缩
- 题设要求将连续重复的字符转为
{字符个数}{字符}的格式。 - 所以我们需要知道连续字符重复出现结束的位置以及出现的次数, 然后进行转换。
- 为此,我们记录当前重复出现的字符以及已经重复出现的次数。
- 然后在当前字符和记录的次数不一致时, 说明此时需要进行转换输出了, 输出已经记录的字符数目和字符。
- 需要注意处理最后一部分重复出现的字符(比如:
"aaacc"需要保证最后一部分字符"cc"也被压缩成"2c")。
如何解压
- 由于字符范围是英文字符和空格。所以出现数字的时候必然是提示重复次数。
- 于是解压时需要提取出数字部分组成重复次数, 然后提取数值部分后面的字符作为重复字符进行输出。
- 开始遍历前或输出上次重复出现字符后, 先初始化重复次数为0, 然后如果检查到当前字符为数字, 则重复次数更新为原值*10 + 当前数字
- 如果当前字符不是数字, 则说明需要进行输出, 输出与"重复次数"相同个数的字符。
完整描述步骤
- 获取输入: 操作类型, 文本
- 如果要求进行压缩操作, 则对文本进行压缩:
- 初始化记录器:
- 重复次数 = 1;
- 重复字符 = 文本的第一个字符;
- 遍历文本中第二个字符开始的字符:
- 如果当前字符等于当前重复字符:
- 重复次数 += 1;
- 否则:
- 输出"{重复次数}{重复字符}"
- 如果当前字符等于当前重复字符:
- 遍历结束, 输出"{重复次数}{重复字符}"
- 初始化记录器:
- 如果要求进行解压操作, 则对文本进行解压:
- 初始化记录器:
- 重复次数 = 0;
- 遍历文本中第一个字符开始的字符:
- 如果当前字符是字符形式的数字:
- 重复次数 = 重复次数 * 10 + 字符代表的数字;
- 否则:
- 如果重复次数 = 0, 输出当前字符后继续下一次遍历(continue或者用else)
- 否则, for i in range(重复次数):
- 输出当前字符
- 重复次数 = 0
- 如果当前字符是字符形式的数字:
- 遍历结束, 输出"{重复次数}{重复字符}"
- 初始化记录器:
伪代码描述
-
get input: operation_type, content
-
if operation_type == 'C':
- init recorder:
- amount = 0;
- last_char = '\0';
- for index, char in content:
- if index == 0:
- amount = 1;
- last_char = char;
- else:
- if char == last_char:
- amount += 1;
- else:
- if amount == 1:
- print(char);
- else:
- print(amount + char);
- last_char = char;
- amount = 1;
- if amount == 1:
- if char == last_char:
- if index == 0:
- init recorder:
-
if operation_type == 'D':
- init recorder:
- amount = 0;
- for char in content:
- if '0' <= char <= '9':
- amount = amout * 10 + int(char)
- else if amount == 0:
- print(char)
- else:
- for time in range(amount):
- print(char)
- amount = 0;
- for time in range(amount):
- if '0' <= char <= '9':
- init recorder:
注意事项
- 以下代码由于使用了C语言的 fgets读取用户输入, 所以content的'\0'有一个'\n', 所以检查到'\n'会输出最后一部分字符, 不需要在遍历之后再输出一次"{重复次数}{重复字符}"
完整提交代码
/*
# 问题分析
- 题设要求按照给定的方式对字符串进行压缩,以及对给定压缩字符串按照约定进行解压。
- 关于如何压缩的方式, 题设已经给出, 所以仍然是模拟压缩的过程.
## 如何压缩
- 题设要求将连续重复的字符转为`{字符个数}{字符}`的格式。
- 所以我们需要知道连续字符重复出现结束的位置以及出现的次数, 然后进行转换。
- 为此,我们记录当前重复出现的字符以及已经重复出现的次数。
- 然后在当前字符和记录的次数不一致时, 说明此时需要进行转换输出了, 输出已经记录的字符数目和字符。
- 需要注意处理最后一部分重复出现的字符(比如: `"aaacc"`需要保证最后一部分字符`"cc"`也被压缩成`"2c"`)。
## 如何解压
- 由于字符范围是英文字符和空格。所以出现数字的时候必然是提示重复次数。
- 于是解压时需要提取出数字部分组成重复次数, 然后提取数值部分后面的字符作为重复字符进行输出。
- 开始遍历前或输出上次重复出现字符后, 先初始化重复次数为0, 然后如果检查到当前字符为数字, 则重复次数更新为原值*10 + 当前数字
- 如果当前字符不是数字, 则说明需要进行输出, 输出与"重复次数"相同个数的字符。
# 完整描述步骤
1. 获取输入: 操作类型, 文本
2. 如果要求进行压缩操作, 则对文本进行压缩:
- 初始化记录器:
- 重复次数 = 1;
- 重复字符 = 文本的第一个字符;
- 遍历文本中第二个字符开始的字符:
- 如果当前字符等于当前重复字符:
- 重复次数 += 1;
- 否则:
- 输出"{重复次数}{重复字符}"
- 遍历结束, 输出"{重复次数}{重复字符}"
3. 如果要求进行解压操作, 则对文本进行解压:
- 初始化记录器:
- 重复次数 = 0;
- 遍历文本中第一个字符开始的字符:
- 如果当前字符是字符形式的数字:
- 重复次数 = 重复次数 * 10 + 字符代表的数字;
- 否则:
- 如果重复次数 = 0, 输出当前字符后继续下一次遍历(continue或者用else)
- 否则, for i in range(重复次数):
- 输出当前字符
- 重复次数 = 0
- 遍历结束, 输出"{重复次数}{重复字符}"
# 伪代码描述
1. get input: operation_type, content
2. if operation_type == 'C':
- init recorder:
- amount = 0;
- last_char = '\0';
- for index, char in content:
- if index == 0:
- amount = 1;
- last_char = char;
- else:
- if char == last_char:
- amount += 1;
- else:
- if amount == 1:
- print(char);
- else:
- print(amount + char);
- last_char = char;
- amount = 1;
3. if operation_type == 'D':
- init recorder:
- amount = 0;
- for char in content:
- if '0' <= char <= '9':
- amount = amout * 10 + int(char)
- else if amount == 0:
- print(char)
- else:
- for time in range(amount):
- print(char)
- amount = 0;
# 注意事项
1. 以下代码由于使用了C语言的 fgets读取用户输入, 所以content的'\0'有一个'\n',
所以检查到'\n'会输出最后一部分字符, 不需要在遍历之后再输出一次"{重复次数}{重复字符}"
*/
# include<stdio.h>
# include<string.h>
char content[1010];
void compress_string(){
fgets(content, 1010, stdin);
content[strlen(content)] = 0;
int amount;
char last_char = '\0';
for (int i = 0; content[i]; i++){
if (i == 0){
last_char = content[i];
amount = 1;
continue;
} else if (content[i] == last_char){
amount++;
} else {
if (amount == 1){
printf("%c", last_char);
} else {
printf("%d%c", amount, last_char);
}
last_char = content[i];
amount = 1;
}
}
printf("\n");
}
void depress_string(){
fgets(content, 1010, stdin);
content[strlen(content)] = 0;
int amount = 0;
for (int i = 0; content[i]; i++){
if (content[i] >= '0' && content[i] <= '9'){
amount = amount * 10 + (content[i] - '0');
} else if (amount == 0) {
printf("%c", content[i]);
} else {
for(int j = 0; j < amount; j++){
printf("%c", content[i]);
}
amount = 0;
}
}
}
int main(){
char operation_type;
scanf("%c", &operation_type);
getchar();
if (operation_type == 'C'){
compress_string();
} else {
depress_string();
}
return 0;
}