【歡迎關(guān)注微信公眾號：計算機(jī)黑科學(xué)大全呀酸，對話框回復(fù)：PAT乙級真題】獲取全部真題詳解及代碼示例
個人博客地址：https://mzwang.top
舊鍵盤
題目描述：
舊鍵盤上壞了幾個鍵，于是在敲一段文字的時候琼梆，對應(yīng)的字符就不會出現(xiàn)⌒杂現(xiàn)在給出應(yīng)該輸入的一段文字窿吩、以及實際被輸入的文字，請你列出肯定壞掉的那些鍵错览。
輸入格式：
輸入在 2 行中分別給出應(yīng)該輸入的文字纫雁、以及實際被輸入的文字。每段文字是不超過 80 個字符的串倾哺，由字母 A-Z（包括大先较、小寫）、數(shù)字 0-9悼粮、以及下劃線
_（代表空格）組成。題目保證 2 個字符串均非空曾棕。輸出格式：
按照發(fā)現(xiàn)順序扣猫，在一行中輸出壞掉的鍵。其中英文字母只輸出大寫翘地，每個壞鍵只輸出一次申尤。題目保證至少有 1 個壞鍵。
輸入樣例：
7_This_is_a_test _hs_s_a_es輸出樣例：
7TI題目來源：PAT乙級1029
作者：CHEN, Yue
單位：浙江大學(xué)
問題解決：
解題思想
本題設(shè)置了一個標(biāo)記數(shù)組str_hash[]衙耕，將字符0-9散列到數(shù)組str_hash[]下標(biāo)0-9昧穿，將字符A-Z或a-z散列到數(shù)組str_hash[]下標(biāo)10-35，對于散列之后對應(yīng)的下標(biāo)ha橙喘，str_hash[ha]為0表示散列前對應(yīng)的字符還未輸出时鸵；str_hash[ha]為1表示散列前對應(yīng)的字符已經(jīng)輸出，就不再重復(fù)輸出厅瞎；將下劃線單獨處理饰潜。注意下標(biāo)的移動問題，若a[i] != b[j]和簸，則a[i]一定是壞鍵彭雾，此時只需將i后移一位；若a[i] = b[j]锁保，則a[i]不是壞鍵薯酝，此時i與j都需要后移一位。由于某一字母是壞鍵時（無論大寫還是小寫字母）只需輸出大寫字母爽柒，只需將小寫字母轉(zhuǎn)換成大寫字母吴菠，然后再進(jìn)行散列即可。
易錯提醒
示例代碼中霉赡，若將第13行的while循環(huán)判斷條件改成：
while(a[i] != '\0'&&b[j] != '\0')
將導(dǎo)致最后一個測試點不通過橄务，因為實際輸入的文字串結(jié)束而應(yīng)該輸入的文字串未結(jié)束時，應(yīng)該輸入的文字串后面可能還會有一些壞鍵穴亏，由于循環(huán)已經(jīng)退出蜂挪，它們將不能輸出重挑，從而導(dǎo)致錯誤。
若將第37行的i后移去掉棠涮，改成如下形式代碼（i后移放到每一判斷條件內(nèi)部）：
#include <cstdio>
#define MAXN 81
using namespace std;
int main()
{
char a[MAXN],b[MAXN]; //a[]為應(yīng)該輸入的文字谬哀，b[]為實際輸入的文字
int str_hash[36] = {0}; //通過散列的方式標(biāo)記某一壞掉的鍵是否已輸出
int flag = 1; //單獨標(biāo)記下劃線是否已輸出(若下劃線為壞掉的鍵)
scanf("%s",a); //輸入應(yīng)該輸入的文字
getchar(); //吸收掉換行
scanf("%s",b); //輸入實際輸入的文字
int i = 0,j = 0;
while(a[i] != '\0'){ //注意此處的條件
if(a[i] != b[j]){
if(flag&&a[i] == '_'){ //'_'為壞鍵且還未輸出
printf("_");
flag = 0; //標(biāo)記'_'已輸出
i++; //應(yīng)輸入文字串的下標(biāo)后移一位
}
else if((a[i] >= 'a'&&a[i] <= 'z')
||(a[i] >= 'A'&&a[i] <= 'Z')){ //小寫或大寫字母
if(a[i] >= 'a'&&a[i] <= 'z'){ //若為小寫字母
a[i] -= 32; //轉(zhuǎn)換成大寫字母
}
int ha = a[i] - 55; //散列，'A'散列對應(yīng)下標(biāo)10
if(str_hash[ha] == 0){ //之前未輸出過
printf("%c",a[i]);
str_hash[ha] = 1; //輸出后標(biāo)記為1
}
i++; //應(yīng)輸入文字串的下標(biāo)后移一位
}
else if(a[i] >= '0'&&a[i] <= '9'){ //若為數(shù)字
int ha = a[i] - '0';
if(str_hash[ha] == 0){ //之前未輸出過
printf("%c",a[i]);
str_hash[ha] = 1; //輸出后標(biāo)記為1
}
i++; //應(yīng)輸入文字串的下標(biāo)后移一位
}
}
else{ //兩文字串對應(yīng)位置字符相同時严肪，則下標(biāo)同時后移一位
i++;
j++;
}
}
return 0;
}
將i++改至第18史煎，30及38行的位置，將導(dǎo)致倒數(shù)第二個測試點超時驳糯，因為一旦壞鍵為_且已輸出篇梭，再次遇到時將不能進(jìn)入判斷條件內(nèi)部，從而導(dǎo)致i不能得到更新酝枢，陷入死循環(huán)恬偷。
代碼示例（C/C++）
小提示：請將以下代碼保存為.cpp格式（C++程序）左右滑動代碼以查看完整代碼
#include <cstdio>
#define MAXN 81
using namespace std;
int main()
{
char a[MAXN],b[MAXN]; //a[]為應(yīng)該輸入的文字，b[]為實際輸入的文字
int str_hash[36] = {0}; //通過散列的方式標(biāo)記某一壞掉的鍵是否已輸出
int flag = 1; //單獨標(biāo)記下劃線是否已輸出(若下劃線為壞掉的鍵)
scanf("%s",a); //輸入應(yīng)該輸入的文字
getchar(); //吸收掉換行
scanf("%s",b); //輸入實際輸入的文字
int i = 0,j = 0;
while(a[i] != '\0'){ //注意此處的條件
if(a[i] != b[j]){
if(flag&&a[i] == '_'){ //'_'為壞鍵且還未輸出
printf("_");
flag = 0; //標(biāo)記'_'已輸出
}
else if((a[i] >= 'a'&&a[i] <= 'z')
||(a[i] >= 'A'&&a[i] <= 'Z')){ //小寫或大寫字母
if(a[i] >= 'a'&&a[i] <= 'z'){ //若為小寫字母
a[i] -= 32; //轉(zhuǎn)換成大寫字母
}
int ha = a[i] - 55; //散列帘睦，'A'散列對應(yīng)下標(biāo)10
if(str_hash[ha] == 0){ //之前未輸出過
printf("%c",a[i]);
str_hash[ha] = 1; //輸出后標(biāo)記為1
}
}
else if(a[i] >= '0'&&a[i] <= '9'){ //若為數(shù)字
int ha = a[i] - '0';
if(str_hash[ha] == 0){ //之前未輸出過
printf("%c",a[i]);
str_hash[ha] = 1; //輸出后標(biāo)記為1
}
}
i++; //應(yīng)輸入文字串的下標(biāo)后移一位
}
else{ //兩文字串對應(yīng)位置字符相同時袍患，則下標(biāo)同時后移一位
i++;
j++;
}
}
return 0;
}
