「PAT乙级真题解析」Basic Level 1029 旧键盘 (问题分析+完整步骤+伪代码描述+提交通过代码)
题目给定两行文字, 第一行是应该输入的文字, 第二行是实际被输入的文字, 我们需要对比两行的文字, 找出应该被输入但是没有被输入的文字, 即两行文字相差的文字. 由于没有被输入是因为键盘坏掉, 所以如果两个文字在实际文本中出现, 但是它们之间的文字没有在文本中出现, 则它们之间的文字就是缺失的。
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
问题分析
题目给定两行文字, 第一行是应该输入的文字, 第二行是实际被输入的文字, 我们需要对比两行的文字, 找出应该被输入但是没有被输入的文字, 即两行文字相差的文字. 由于没有被输入是因为键盘坏掉, 所以如果两个文字在实际文本中出现, 但是它们之间的文字没有在文本中出现, 则它们之间的文字就是缺失的。
如何找到缺失的文字
方案一: 利用输入文本的顺序性
由于文本输入是有顺序性的, 换句话说, 两行文本本应该完全一样(如果键盘没有坏), 则如果哪个位置上的文字不一样, 则这个位置本应该出现的文字就是缺失的. 而现在位置上的出现的文字一定可以在本应出现的文本中该位置的后面找到对应. 所以, 我们只要从头开始对比相同位置的文字, 如果文字不一样, 就意味着找到了一个缺失文字. 找到缺失文字之后, 需要先让本应该出现的文本的查找位置后移(可以理解为位置校准) 重复上述步骤查找完两个文本之后, 就可以找出完全缺失的文字
方案二: 直接统计频率
正如我们一开始想的, 缺失的文字指的是本应该出现但是没有出现的文字, 从频率上来讲, 就是出现频率在两行文本中存在差异的文字。 所以我们只要统计第一行和第二行文本中出现了哪些文字以及文字频率, 然后找出两组频率的差异即可. 进一步地, 由于键盘坏掉, 文字其实只有"出现"和"不出现"两种情况, 所以我们只需要统计第二行文本哪些文字出现过, 然后回过头来对比应该出现的文本, 如果一个文字在因该出现的文本中, 但是没有出现在第二行的统计数据中, 则这个文字就是缺失的
完整描述步骤
- 获取两行文本
- 统计第二行文本出现过的字符, 出现的字符在对应的统计器中进行标记
- 检查第一行文本的每个字符是否在统计器中被统计到, 如果没有被统计到, 则就是缺失字符.
- 输出缺失字符.(每个字符只输出一次)
伪代码
- get input
- init array as recorder
- for char in second content: set flag of char in recorder as 1
- for char in first content: if flag of char in recorder is 0, then this char is missing char, save it.
- print all missing chars
- record the has been printed char and not print repeatedly.
完整提交代码
/*
# 问题分析
题目给定两行文字, 第一行是应该输入的文字, 第二行是实际被输入的文字,
我们需要对比两行的文字, 找出应该被输入但是没有被输入的文字, 即两行文字相差的文字.
由于没有被输入是因为键盘坏掉, 所以两个文字在实际文本中出现, 但是他们之间的文字没有在文本中出现, 则它们之间的文字就是缺失的。
## 如何找到缺失的文字
### 方案一: 利用输入文本的顺序性
由于文本输入是有顺序性的, 换句话说, 两行文本本应该完全一样(如果键盘没有坏),
则如果哪个位置上的文字不一样, 则这个位置本应该出现的文字就是缺失的.
而现在位置上的出现的文字一定可以在本应出现的文本中该位置的后面找到对应.
所以, 我们只要从头开始对比相同位置的文字, 如果文字不一样, 就意味着找到了一个缺失文字.
找到缺失文字之后, 需要先让本应该出现的文本的查找位置后移(可以理解为位置校准)
重复上述步骤查找完两个文本之后, 就可以找出完全缺失的文字
### 方案二: 直接统计频率
正如我们一开始想的, 缺失的文字指的是本应该出现但是没有出现的文字, 从频率上来讲, 就是出现频率在两行文本中存在差异的文字。
所以我们只要统计第一行和第二行文本中出现了哪些文字以及文字频率, 然后找出两组频率的差异即可.
进一步地, 由于键盘坏掉, 文字其实只有"出现"和"不出现"两种情况,
所以我们只需要统计第二行文本哪些文字出现过, 然后回过头来对比应该出现的文本,
如果一个文字在因该出现的文本中, 但是没有出现在第二行的统计数据中, 则这个文字就是缺失的
# 完整描述步骤
1. 获取两行文本
2. 统计第二行文本出现过的字符, 出现的字符在对应的统计器中进行标记
3. 检查第一行文本的每个字符是否在统计器中被统计到, 如果没有被统计到, 则就是缺失字符.
4. 输出缺失字符.(每个字符只输出一次)
# 伪代码
1. get input
2. init array as recorder
3. for char in second content:
set flag of char in recorder as 1
4. for char in first content:
if flag of char in recorder is 0,
then this char is missing char, save it.
5. print all missing chars
- record the has been printed char and not print repeatedly.
*/
# include<stdio.h>
char lower_to_upper(char ori){
if (ori >= 'a' && ori <= 'z')
return (char)((int)ori - 32);
return ori;
}
int main(){
char first_content[81];
char second_content[81];
scanf("%s\n%s", first_content, second_content);
int flags[256] = {0};
for (int i = 0; second_content[i]; i++){
int char_flag_position = (int)second_content[i];
flags[char_flag_position] = 1;
}
for (int i = 0; first_content[i]; i++){
int char_flag_position = (int)first_content[i];
char conveted_char = lower_to_upper(first_content[i]);
int conveted_char_flag_position = (int)conveted_char;
if (flags[char_flag_position] == 0 && flags[conveted_char_flag_position] == 0){
flags[char_flag_position] = 1;
flags[conveted_char_flag_position] = 1;
printf("%c", conveted_char);
}
}
return 0;
}