「PAT乙级真题解析」Basic Level 1033 旧键盘打字 (问题分析+完整步骤+伪代码描述+提交通过代码)
题目设定了一个场景: 有个键盘某些键坏了, 要你模拟这个键盘输入某段文本, 然后输出会被打印出来的内容。 **实质上, 这个题目是给定了一段文本, 然后给定了一个集合(键盘损坏的键集; 以及组合键规则, 如shift+t = T), 要求找出给定文本中不在集合中的内容, 并输出内容**。 **所以重点在于「查找当前字符是否在无法输出的字符集合中」的过程/逻辑.**
#算法#数据结构#需求分析#pat考试#c语言
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
问题分析
题目设定了一个场景: 有个键盘某些键坏了, 要你模拟这个键盘输入某段文本, 然后输出会被打印出来的内容。 实质上, 这个题目是给定了一段文本, 然后给定了一个集合(键盘损坏的键集; 以及组合键规则, 如shift+t = T), 要求找出给定文本中不在集合中的内容, 并输出内容。
所以重点在于「查找当前字符是否在无法输出的字符集合中」的过程/逻辑.
判断当前字符是否是在无法输出的字符集合中
- 无法输出的字符集合包括:
- 题设给定的字符串内容组成的集合
- 如果题设集合中含有"+"表示"Shift 上档键", 则所有的大写字母也要纳入该字符集合中
- 字符集的存储方式
- 可以使用编程语言原生的集合类型,
- 如果没有集合类型, 如C语言. 可以使用数组进行存储;
完整描述步骤
- 获取题设给定数据: 损坏的键盘字符集, 应该输入的文本
- 构建无法输出的字符集合:
- 将题设给定的字符集合放入无法输出的字符集合;
- 检查是否存在代表上档键的"+"字符, 如果有, 则将全部大写字母也放入无法输出的字符集合
- 将题设给定的字符集合中的英文字母(题设只给大写形式)对应的小写英文字母放入集合中
- 遍历要输出的文本, 对于每个字符进行检查: 如果该字符不在无法输出的字符集合中, 则输出该字符.
伪代码描述
- get input: broken_keys, should_input_content;
- build no-to-output-char-set = {broken_keys};
- if '+' in broken_keys: no-to-output-char-set += {A, B, C, ..., Z};
- for char in broken_keys: if 'A' <= char <= 'Z': add lower case of char into no-to-output-char-set
- for char in should_input_content: if char not in no-to-output-char-set: print(char)
完整提交代码
/*
# 问题分析
题目设定了一个场景: 有个键盘某些键坏了, 要你模拟这个键盘输入某段文本, 然后输出会被打印出来的内容。
实质上, 这个题目是给定了一段文本, 然后给定了一个集合(键盘损坏的键集; 以及组合键规则, 如shift+t = T),
要求找出给定文本中不在集合中的内容, 并输出内容。
所以重点在于「查找当前字符是否在无法输出的字符集合中」的过程/逻辑.
# 判断当前字符是否是在无法输出的字符集合中
- 无法输出的字符集合包括:
1. 题设给定的字符串内容组成的集合
2. 如果题设集合中含有"+"表示"Shift 上档键",
则所有的大写字母也要纳入该字符集合中
- 字符集的存储方式
- 可以使用编程语言原生的集合类型,
- 如果没有集合类型, 如C语言. 可以使用数组进行存储;
# 完整描述步骤
1. 获取题设给定数据: 损坏的键盘字符集, 应该输入的文本
2. 构建无法输出的字符集合:
- 将题设给定的字符集合放入无法输出的字符集合;
- 检查是否存在代表上档键的"+"字符, 如果有, 则将全部大写字母也放入无法输出的字符集合
- 将题设给定的字符集合中的英文字母(题设只给大写形式)对应的小写英文字母放入集合中
3. 遍历要输出的文本, 对于每个字符进行检查:
如果该字符不在无法输出的字符集合中, 则输出该字符.
# 伪代码描述
1. get input: broken_keys, should_input_content;
2. build no-to-output-char-set = {broken_keys};
3. if '+' in broken_keys:
no-to-output-char-set += {A, B, C, ..., Z};
4. for char in broken_keys:
if 'A' <= char <= 'Z':
add lower case of char into no-to-output-char-set
5. for char in should_input_content:
if char not in no-to-output-char-set:
print(char)
*/
# include<stdio.h>
# define MAX_AMOUNT 100001
int main()
{
int broken_flags[256] = {0};
char broken_chars[MAX_AMOUNT];
char pressed_keys[MAX_AMOUNT];
gets(broken_chars);
gets(pressed_keys);
for (int i = 0; broken_chars[i]; i++)
{
broken_flags[(int)broken_chars[i]] = 1;
if (broken_chars[i] == '+')
{
for (char c = 'A'; c <= 'Z'; c++){
broken_flags[(int)c] = 1;
}
} else if (broken_chars[i] >= 'A' && broken_chars[i] <= 'Z'){
broken_flags[(int)broken_chars[i] + 32] = 1;
}
}
for (int i = 0; pressed_keys[i]; i++)
{
if (broken_flags[(int)pressed_keys[i]] == 0){
printf("%c", pressed_keys[i]);
}
}
printf("\n");
return 0;
}