(PAT)1084 Broken Keyboard(哈希表)-蒲公英云

(PAT)1084 Broken Keyboard(哈希表)

忘是亡心i 2022-05-10 04:42 287阅读 0赞

On a broken keyboard, some of the keys are worn out. So when you type some sentences, the characters corresponding to those keys will not appear on screen.

Now given a string that you are supposed to type, and the string that you actually type out, please list those keys which are for sure worn out.

Input Specification:

Each input file contains one test case. For each case, the 1st line contains the original string, and the 2nd line contains the typed-out string. Each string contains no more than 80 characters which are either English letters [A-Z] (case insensitive), digital numbers [0-9], or _ (representing the space). It is guaranteed that both strings are non-empty.

Output Specification:

For each test case, print in one line the keys that are worn out, in the order of being detected. The English letters must be capitalized. Each worn out key must be printed once only. It is guaranteed that there is at least one worn out key.

Sample Input:

7_This_is_a_test
_hs_s_a_es

Sample Output:

解题思路:

构建一个哈希表,将各字符的ASCII值作为键码传入到哈希表中,并标记这个键值标签下的ASCII值为true或为false

第一次输入将所有字符都标记为true

第二次输出将所有字符都标记为false,这样剩下的标记为true的字符就表示没有正常输出的字符

最后输出标记为true的字符即可

代码:

#include <iostream>
#include <string>
using namespace std;
int main() {
    string strinput;   //输入字符串
    string stroutput;  //输出字符串
    bool hashTable[258] = { false };  //记录输入和输出操作
    int hashIndex[258] = { 0 };
    int index = 0;
    cin >> strinput;
    cin >> stroutput;
    for (auto &x : strinput) {
        if (isalpha(x)) {
            x = toupper(x);   //转为大写
        }
        int code = (int)x;  //char类型到int类型
        hashTable[code] = true;   //表示进行了一次敲击
        hashIndex[index] = code;
        index++;
    }
    for (auto &y : stroutput) {
        if (isalpha(y)) {
            y = toupper(y);   //转为大写
        }
        int code = (int)y;
        hashTable[code] = false;
    }
    for (int code = 0; code < index; ++code) {  //遍历操作
        if (hashTable[hashIndex[code]]==true) {   //敲打过的
            char bet = char(hashIndex[code]);    //将ACSCII码转为字符
            cout << bet;
            hashTable[hashIndex[code]] = false;
         }
    }
    return 0;
}