PAT乙级1033 || 旧键盘打字（详解，C/C++示例，测试点分析）

Posted on In

旧键盘打字

题目描述

旧键盘上坏了几个键，于是在敲一段文字的时候，对应的字符就不会出现。现在给出应该输入的一段文字、以及坏掉的那些键，打出的结果文字会是怎样？

输入格式

输入在 2 行中分别给出坏掉的那些键、以及应该输入的文字。其中对应英文字母的坏键以大写给出；每段文字是不超过 $10^5$ 个字符的串。可用的字符包括字母 [a-z, A-Z]、数字 0-9、以及下划线 _（代表空格）、,、.、-、+（代表上档键）。题目保证第 2 行输入的文字串非空。
注意：如果上档键坏掉了，那么大写的英文字母无法被打出。

输出格式

在一行中输出能够被打出的结果文字。如果没有一个字符能被打出，则输出空行。

输入样例

1
2
7+IE.
7_This_is_a_test.

输出样例

1
_hs_s_a_tst

问题解决

解题思想

下面的代码1与代码2大同小异。代码1没有’’充分’’运用散列，其只把大小写字母和数字’’充分’’进行散列，其它几个字符进行了单独处理，充分利用了空间，代码不简洁。代码2进行了完全散列，因为这些字符的ASCII码不会超过128，故将字符散列数组开到128，这样就简化了代码，这种方式更优。

定义字符散列数组str_hash[]，初始化为0，读入第一行字符串，对每一个字符（坏掉的键）c，将str_hash[c]置为1；读入第二行字符串，对该字符串的每一个字符，先检查其是否能输出，若相应的键已坏掉，则跳过输出，进行下一次判断。

坑点提醒

题目保证第 2 行输入的文字串非空，但没保证第1行输入的文字串非空，因此若第1行输入为空时要有相应的处理，否则将导致测试点2不通过。若第1行文字串的输入用如下形式：

1
scanf("%s",str);

则当第1行为空时，由于%s不能读入回车，其会跳过第1行直接将第2行的内容读入str[]。此处我们可采用如下方式来读入，这样第1行为空时也不会影响到下一行，当然还有很多其它方式。

1
2
3
for(int i = 0; (c = getchar()) != '\n'; i++){
    str[i] = c;
}

代码示例（C/C++）

代码1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
//此法没有'充分'利用散列，但节省空间
#include <cstdio>
#define MAXLEN 100001
using namespace std;
int main()
{
    int str_hash[41] = {0};//字符散列，标记该字符对应的键是否坏掉，
                           //可用字符最多67个，大小写英文字母不区分剩41个
    char str[67];
    char c;
    for(int i = 0; (c = getchar()) != '\n'; i++){//此处不要用%s直接读入字符串，%s不能读入回车，第一行为空时不能读入，从而导致str[]错误读入第二行
        str[i] = c;	
    }
    for(int i = 0; str[i] != '\0'; i++){//标记坏掉的键
        int temp;
        if(str[i] >= '0'&&str[i] <= '9'){//数字
            temp = str[i] - '0';//数字字符转换为数值
        }
        else if(str[i] >= 'a'&&str[i] <= 'z'){//小写字母
            temp = str[i] - 'a' + 10;//小写字母转换为数值
        }
        else if(str[i] >= 'A'&&str[i] <= 'Z'){//大写字母
            temp = str[i] - 'A' + 10;//大写字母转换为数值
        }
        else if(str[i] == '_'){
            temp = 36;
        }
        else if(str[i] == ','){
            temp = 37;
        }
        else if(str[i] == '.'){
            temp = 38;
        }
        else if(str[i] == '-'){
            temp = 39;
        }
        else if(str[i] == '+'){
            temp = 40;
        }
        str_hash[temp] = 1;
    }
    char str1[MAXLEN];
    scanf("%s",str1);
    for(int i = 0; str1[i] != '\0'; i++){
        if(str1[i] >= 'A'&&str1[i] <= 'Z'){
            if(str_hash[40]||str_hash[str1[i] - 'A' + 10]){//若上挡键坏了或该大写字母键坏了
                continue;
            }
        }
        else if(str1[i] >= 'a'&&str1[i] <= 'z'){
            if(str_hash[str1[i] - 'a' + 10]){//若小写字母键坏了
                continue;
            }
        }
        else if(str1[i] >= '0'&&str1[i] <= '9'){
            if(str_hash[str1[i] - '0']){//数字键坏了
                continue;
            }
        }
        else if(str1[i] == '_'&&str_hash[36]){
            continue;
        }
        else if(str1[i] == ','&&str_hash[37]){
            continue;
        }
        else if(str1[i] == '.'&&str_hash[38]){
            continue;
        }
        else if(str1[i] == '-'&&str_hash[39]){
            continue;
        }
        printf("%c",str1[i]);
    }
    printf("\n");
    return 0;
}

代码2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//'充分'利用散列，代码较简洁
#include <cstdio>
#define MAXLEN 100001
using namespace std;
int main()
{
    int str_hash[128] = {0};//这些字符的ASCII码值不会超过128
    char str[67];//可用字符最多67个
    char c;
    for(int i = 0; (c = getchar()) != '\n'; i++){
        str[i] = c;
    }
    for(int i = 0; str[i] != '\0'; i++){//标记坏掉的键
        str_hash[str[i]] = 1;
    }
    char str1[MAXLEN];
    scanf("%s",str1);
    for(int i = 0; str1[i] != '\0'; i++){
        if(str_hash['+'] == 1){//下档键已坏
            if(str1[i] >= 'A'&&str1[i] <= 'Z'){//大写字母不输出
                continue;
            }
        }
        if(str1[i] >= 'A'&&str1[i] <= 'Z'){//大写字母
            if(str_hash[str1[i] + 32] == 1){//对应小写字母已坏
                continue;//大写字母不输出
            }
        }
        if(str1[i] >= 'a'&&str1[i] <= 'z'){//小写字母
            if(str_hash[str1[i] - 32] == 1){//对应大写字母已坏
                continue;//小写字母不输出
            }
        }
        if(str_hash[str1[i]] == 1){
            continue;
        }
        printf("%c",str1[i]);
    }
    printf("\n");
    return 0;
}

题目来源：PAT乙级1033
作者：CHEN, Yue
单位：浙江大学

稀罕作者