整理回顾一下Codingame上做过的一些编程题。先从散列表实现的一个题目MIME type开始。
https://www.codingame.com/ide/puzzle/mime-type
目标
MIME在多种互联网协议中被使用到，用来标识发送内容的媒体类型（html，图片，视频），通常通过文件的扩展名里面推测出来。
写个程序来检测文件名对应的MIME类型
规则：
- 预先提供了一个MIME类型到文件扩展名的关联表，还有一系列的文件名字，针对每个文件名，必须找到对应的MIME
- 文件扩展名是文件名字符串按照"."字符分割出来的子串中的最后一个子串（如果有的话）
- 扩展名不区分大小写，例如，TXT和txt一样看待。如果在关联表中找到了对应的MIME类型，则输出对应的类型，否则输出UNKNOWN
输入
Line 1: N 关联表的元素个数
Line 2: Q 待分析的文件名
随后的N行：每行一个文件扩展名及对应的MIME类型
之后的Q行：每行一个文件名
输出
针对Q行的每个文件名，输出对应的MIME类型。如果没有找到对应的类型，则输出UNKNOWN
限制
0 < N < 10000
0 < Q < 10000
C++ 题解
一个题解如下，运用C++ STL实现的散列表容器unordered_map来存入MIME类型到文件扩展名的关联表。这样查询的平均时间复杂度为O(1)。
#include <iostream>
#include <string>
#include <map> // red-black tree based
#include <unordered_map> // hashtable based
using namespace std;
string toupper(string str)
{
for (auto & c: str) c = toupper(c);
return str;
}
int main()
{
int N, Q;
cin >> N >> Q; cin.ignore();
// map<string, string> mime; logN runtime
std::unordered_map<string, string> mime; // constant runtime
for (int i = 0; i < N; i++)
{
string key, value;
cin >> key >> value; cin.ignore();
mime[toupper(key)] = value;
}
string str;
while (getline(cin, str))
{
auto pos = str.find_last_of("."); // search backward for "."
str = (pos == -1) ? "" : toupper(str.substr(pos +1));
cout << (mime.count(str) ? mime[str] : "UNKNOWN") << endl;
}
}
参考
https://stackoverflow.com/questions/9214353/hash-table-runtime-complexity-insert-search-and-delete
https://www.codingame.com/learn/hash-tables