GESP7级C++考试语法知识（四、哈希表（10、综合应用模版大全）

🏆 第十课：《哈希王国终极挑战——综合应用训练》

一、毕业考试来了！

1、经过前面的学习。

你已经认识了哈希家族的成员：

unordered_map

和

unordered_set

2、同学们学会了：

✅ 统计次数

✅ 判断存在

✅ 查重问题

✅ Two Sum

3、今天。

程序王国举行一年一度的：

🏆 哈希王国勇士认证考试

4、国王宣布：

谁能通过所有挑战，

谁就是正式的哈希勇士！

今天我们不学新知识。

而是把前面所有知识串起来。

第一关：动物统计中心

1、森林里举行动物大会。

参加的动物：

狗 猫 狗 兔 狗 猫

2、国王问：

每种动物来了几次？

3、思考

这是什么题？

4、是不是：

统计出现次数

5、立刻想到：

unordered_map<string,int>

6、解法

unordered_map<string,int> cnt;

7、每来一个动物：

cnt[name]++;

8、统计过程：

狗 → 3 猫 → 2 兔 → 1

9、核心代码

unordered_map<string,int> cnt; string name; while(cin>>name) { cnt[name]++; }

10、口诀

统计次数不用想， unordered_map登场。 看到一个加一次， cnt[x]最擅长。

第二关：失踪宝石调查

1、仓库：

红宝石 蓝宝石 钻石 黄金

2、问题：

钻石存在吗？ 珍珠存在吗？

3、思考

这是：

判断是否存在

想到：

count()

4、解法

unordered_set<string> s;

5、登记：

s.insert("钻石");

6、查询：

s.count("钻石")

返回：

1

说明：

存在

7、核心代码

if(s.count(x)) { cout<<"存在"; } else { cout<<"不存在"; }

第三关：谁是冒名顶替者？

1、进入城堡的人：

Tom Jack Mike Tom

2、问题：

谁重复进入了？

3、思考

这是：

查重问题

想到：

unordered_set

4、解法

unordered_set<string> s;

5、核心代码：

if(s.count(name)) { cout<<"重复"; } else { s.insert(name); }

运行过程：

Tom Jack Mike Tom ← 已经见过

发现：

Tom

重复。

第四关：金币配对挑战

1、金币编号：

2 7 11 15

目标：

9

问题：

哪两个数字加起来等于9？

2、思考

这是：

Two Sum

核心公式：

need = target - x;

3、解法

unordered_set<int> s;

4、核心代码：

for(int x:a) { if(s.count(target-x)) { cout<<"找到"; } s.insert(x); }

运行：

看到2 需要7 没有 记录2

看到7 需要2 有！

成功。

第五关：统计不同数字

1、输入：

1 5 2 1 3 5 5 2

2、问题：

有多少种数字？

1 2 3 5

答案：

4种

3、哈希做法

unordered_set<int> s;

4、每个数字：

s.insert(x);

重复自动消失。

5、最后：

cout<<s.size();

输出：

4

第六关：谁出现次数最多？

1、输入：

1 5 2 1 3 5 5 2

2、统计：

1 → 2 2 → 2 3 → 1 5 → 3

问题：

谁出现最多？

3、解法

（1）先统计：

unordered_map<int,int> cnt;

（2）然后遍历：

int mx=0; int ans=0; for(auto p:cnt) { if(p.second>mx) { mx=p.second; ans=p.first; } }

（3）答案：

5

（4）出现：

3次

第七关：黑名单系统

1、黑名单：

1001 1002 1003

2、有人进入：

1002

3、问题：

是不是坏人？

4、解法

建立：

unordered_set<int> black;

5、查询：

if(black.count(id))

6、结果：

是黑名单用户

第八关：访问记录系统

1、网页访问记录：

Tom Jack Tom Mike Tom

2、问题：

Tom访问过吗？

3、答案：

visit.count("Tom")

4、结果：

存在

第九关：哈希表选谁？

1、比赛时的疑惑：

不知道用：

unordered_map

还是：

unordered_set

记住下面这个表。

2、哈希选择宝典

3、一眼判断技巧

如果题目出现：

数字→次数 姓名→分数 学号→姓名

想到：

unordered_map

4、如果题目出现：

是否存在 是否重复 是否出现过 多少种不同元素

想到：

unordered_set

哈希勇士毕业考试

请判断下面题目用什么。

第一题

统计每个数字出现次数

答案：

unordered_map<int,int>

第二题

判断用户是否注册

答案：

unordered_set<string>

第三题

找重复数字

答案：

unordered_set<int>

第四题

统计不同单词数量

答案：

unordered_set<string>

第五题

统计学生成绩

答案：

unordered_map<string,int>

哈希王国最终总结

经过十节课。

你已经掌握：

第一阶段：哈希原理

✅ 哈希表是什么

✅ 哈希函数

✅ 哈希冲突

第二阶段：C++中的哈希表

✅ unordered_map

✅ 统计次数

✅ 判断存在

✅ unordered_set

第三阶段：经典应用

✅ 查重问题

✅ Two Sum

✅ 综合应用

哈希勇士必背模板

统计次数

unordered_map<int,int> cnt; cnt[x]++;

判断存在

if(s.count(x)) { }

查重

if(s.count(x)) { // 重复 } else { s.insert(x); }

Two Sum

if(s.count(target-x)) { // 找到答案 }

统计不同元素

unordered_set<int> s; s.insert(x); cout<<s.size();

哈希王国毕业口诀

哈希表，真神奇， 查找速度天下第一。 统计次数用Map， 出现几次全记下。 判断存在用Set， 重复元素全识别。 Two Sum找搭档， target减它最漂亮。 学会哈希不用怕， 百万数据也拿下！

🏆 恭喜你！

你已经正式获得：

《哈希王国初级勇士证书》

从“会用哈希表”，升级为“真正理解哈希思想的算法高手”！🚀🏆