第十课《哈希王国终极挑战——综合应用训练》一、毕业考试来了1、经过前面的学习。你已经认识了哈希家族的成员unordered_map和unordered_set2、同学们学会了✅ 统计次数✅ 判断存在✅ 查重问题✅ Two Sum3、今天。程序王国举行一年一度的 哈希王国勇士认证考试4、国王宣布谁能通过所有挑战谁就是正式的哈希勇士今天我们不学新知识。而是把前面所有知识串起来。第一关动物统计中心1、森林里举行动物大会。参加的动物狗 猫 狗 兔 狗 猫2、国王问每种动物来了几次3、思考这是什么题4、是不是统计出现次数5、立刻想到unordered_mapstring,int6、解法unordered_mapstring,int cnt;7、每来一个动物cnt[name];8、统计过程狗 → 3 猫 → 2 兔 → 19、核心代码unordered_mapstring,int cnt; string name; while(cinname) { cnt[name]; }10、口诀统计次数不用想 unordered_map登场。 看到一个加一次 cnt[x]最擅长。第二关失踪宝石调查1、仓库红宝石 蓝宝石 钻石 黄金2、问题钻石存在吗 珍珠存在吗3、思考这是判断是否存在想到count()4、解法unordered_setstring s;5、登记s.insert(钻石);6、查询s.count(钻石)返回1说明存在7、核心代码if(s.count(x)) { cout存在; } else { cout不存在; }第三关谁是冒名顶替者1、进入城堡的人Tom Jack Mike Tom2、问题谁重复进入了3、思考这是查重问题想到unordered_set4、解法unordered_setstring s;5、核心代码if(s.count(name)) { cout重复; } else { s.insert(name); }运行过程Tom Jack Mike Tom ← 已经见过发现Tom重复。第四关金币配对挑战1、金币编号2 7 11 15目标9问题哪两个数字加起来等于92、思考这是Two Sum核心公式need target - x;3、解法unordered_setint 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 22、问题有多少种数字1 2 3 5答案4种3、哈希做法unordered_setint s;4、每个数字s.insert(x);重复自动消失。5、最后couts.size();输出4第六关谁出现次数最多1、输入1 5 2 1 3 5 5 22、统计1 → 2 2 → 2 3 → 1 5 → 3问题谁出现最多3、解法1先统计unordered_mapint,int cnt;2然后遍历int mx0; int ans0; for(auto p:cnt) { if(p.secondmx) { mxp.second; ansp.first; } }3答案54出现3次第七关黑名单系统1、黑名单1001 1002 10032、有人进入10023、问题是不是坏人4、解法建立unordered_setint black;5、查询if(black.count(id))6、结果是黑名单用户第八关访问记录系统1、网页访问记录Tom Jack Tom Mike Tom2、问题Tom访问过吗3、答案visit.count(Tom)4、结果存在第九关哈希表选谁1、比赛时的疑惑不知道用unordered_map还是unordered_set记住下面这个表。2、哈希选择宝典题目特征选择统计次数unordered_map姓名→分数unordered_map学号→姓名unordered_map数字→出现次数unordered_map判断存在unordered_set查重unordered_set不同元素个数unordered_set是否访问过unordered_set3、一眼判断技巧如果题目出现数字→次数 姓名→分数 学号→姓名想到unordered_map4、如果题目出现是否存在 是否重复 是否出现过 多少种不同元素想到unordered_set哈希勇士毕业考试请判断下面题目用什么。第一题统计每个数字出现次数答案unordered_mapint,int第二题判断用户是否注册答案unordered_setstring第三题找重复数字答案unordered_setint第四题统计不同单词数量答案unordered_setstring第五题统计学生成绩答案unordered_mapstring,int哈希王国最终总结经过十节课。你已经掌握第一阶段哈希原理✅ 哈希表是什么✅ 哈希函数✅ 哈希冲突第二阶段C中的哈希表✅ unordered_map✅ 统计次数✅ 判断存在✅ unordered_set第三阶段经典应用✅ 查重问题✅ Two Sum✅ 综合应用哈希勇士必背模板统计次数unordered_mapint,int cnt; cnt[x];判断存在if(s.count(x)) { }查重if(s.count(x)) { // 重复 } else { s.insert(x); }Two Sumif(s.count(target-x)) { // 找到答案 }统计不同元素unordered_setint s; s.insert(x); couts.size();哈希王国毕业口诀哈希表真神奇 查找速度天下第一。 统计次数用Map 出现几次全记下。 判断存在用Set 重复元素全识别。 Two Sum找搭档 target减它最漂亮。 学会哈希不用怕 百万数据也拿下 恭喜你你已经正式获得《哈希王国初级勇士证书》从“会用哈希表”升级为“真正理解哈希思想的算法高手”