关于算法-数据结构:PAT甲级1022-Digital-Library

44次阅读

共计 1729 个字符,预计需要花费 5 分钟才能阅读完成。

题目粗心:

给出 N 本书的编号、书名、作者、关键词(可能有多个)、出版社及出版年份,并给出 M 个查问,每个查问给出书名、作者、关键词(单个)、出版社及出版年份中的一个,要求输入满足该给出信息的所有书的编号。

算法思路:

咱们应用 unordered_map<string,vector<int>> hashToID[6]保留 5 个关键字查问对应的所有已知的 id,1 到 5 别离示意 title,author,keyword,publisher,publish_year 与书籍 id 的对应. 在输出的时候,咱们对于每一个输出的字符串依据其输出程序建设不同的类别到 id 的映射,比方第一个输出的字符串 s 肯定是 book title,那么就将 id 增加到hashToID[1][s] 中,顺次类推,惟一不同的是解决 keywords 的状况,这里应用了 deal 函数来解决,将每一个字符增加到 s 中,遇到空格阐明是一个 word,就建设该 word 与 id 的映射, 不过得记得解决最初一个 word(在循环外部无奈解决)。在最初输入的时候,咱们应用 tag 记录查问的类别,s 为查问的关键字,如果 hashToID[tag].find(s)==hashToID[tag].end(),阐明以后类别中没有该关键字,就输入Not Found, 否则输入hashToID[tag][s] 的每一个 id 号。

以后这种写法应该是耗时最短的了,并且代码量也较小。

留神点:

1、id 号固定为 7 位,所以输入得保留 7 位有效数字,测试点 3 和 4 考查,如果应用 string 就不会有这个问题。
2、getline 的输出前得应用 getchar()承受回车,不然就会出错。

提交后果:

AC 代码:

#include <cstdio>
#include <unordered_map>
#include <vector>
#include <iostream>
#include <algorithm>


using namespace std;

unordered_map<string,vector<int>> hashToID[6];

// 解决 keywords
void deal(const string& keywords,int id){
    string s;
    for (char keyword : keywords) {if(keyword!=' '){s += keyword;} else {hashToID[3][s].push_back(id);
            s = "";
        }
    }
    // 解决最初一个 keyword
    hashToID[3][s].push_back(id);
}

int main(){
    int N;
    scanf("%d",&N);
    int id;
    string s;
    for (int i = 0; i < N; ++i) {scanf("%d",&id);// 首先输出 id
        getchar();// 承受回车
        getline(cin,s);// 输出 book title
        hashToID[1][s].push_back(id);
        getline(cin,s);// 输出 name of an author
        hashToID[2][s].push_back(id);
        getline(cin,s);// 输出 keywords
        deal(s,id);
        getline(cin,s);// 输出 name of a publisher
        hashToID[4][s].push_back(id);
        getline(cin,s);// 输出 year
        hashToID[5][s].push_back(id);
    }
    // 开始查问
    scanf("%d",&N);
    int tag;
    for (int k = 0; k < N; ++k) {scanf("%d:",&tag);
        getline(cin,s);
        printf("%d: %s\n",tag,s.c_str());
        if(hashToID[tag].find(s)==hashToID[tag].end()){printf("Not Found\n");
        } else {sort(hashToID[tag][s].begin(),hashToID[tag][s].end());
            for(auto &item:hashToID[tag][s]){printf("%07d\n",item);
            }
        }
    }
    return 0;
}

正文完
 0