当前位置: 首页 > article >正文

CC45.【C++ Cont】STL中的哈希表及练习

目录

1.unordered_set和unordered_multiset

2.unordered_set

3.unordered_map

4.例题:P5266 【深基17.例6】学籍管理

分析

代码

提交结果

5.练习题:P1102 A-B 数对

分析

方法1:暴力求解

方法2:哈希表或者红黑树

哈希表解法

提交结果

红黑树解法

提交结果

6.练习题:P3405 [USACO16DEC] Cities and States S

分析

一对「特殊」的城市的含义

细节处理

代码

红黑树写法

写法1和2的区别

提交结果

写法3

提交结果

哈希表写法

提交结果


1.unordered_set和unordered_multiset

对比之前在CC42.【C++ Cont】STL库的红黑树set的使用文章讲过的set,set底层用的红黑树,而unordered_set和unordered_multiset的底层用的哈希表,使用方法完全一样

set存的是有序的,unordered_set和unordered_multiset存的是无序的(unordered)

这里以unordered_set为例

2.unordered_set

参见CC42.【C++ Cont】STL库的红黑树set的使用文章,除了没有lower_bound和upper_bound接口,其余使用方法完全一样

注意使用前要先包含<unordered_set>头文件

3.unordered_map

参见CC42.【C++ Cont】STL库的红黑树set的使用文章,除了没有lower_bound和upper_bound接口,其余使用方法完全一样

注意使用前要先包含<unordered_map>头文件

4.例题:P5266 【深基17.例6】学籍管理

https://www.luogu.com.cn/problem/P5266

分析

属于正常的增删查改的问题,考察最基本的接口调用问题,对不同情况判断做出相应的操作即可

代码

#include <iostream>
#include <unordered_map>
#include <string>
#define endl "\n"
using namespace std;
int op,score,times;
string name;
unordered_map<string,int> mp;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>times;	
	while (times--)
	{
		cin>>op;
		if (op==1)
		{
			cin>>name>>score;
			if (mp.count(name))
				mp[name]=score;
			else
				mp.insert({name,score});
			cout<<"OK"<<endl;
		}
		else if (op==2)
		{
			cin>>name;
			if (mp.count(name))	
				cout<<mp[name]<<endl;
			else
				cout<<"Not found"<<endl;
		}
		else if (op==3)
		{
			cin>>name;
			if (mp.count(name))
			{
				mp.erase(name);
				cout<<"Deleted successfully"<<endl; 
			}		
			else
				cout<<"Not found"<<endl;
		}
		else//op==4
			cout<<mp.size()<<endl; 
	}
}

注:存储的方式选择unordered_map<string,int>或map<string,int>都可以,但不能用set,set只能存储单关键字

提交结果

5.练习题:P1102 A-B 数对

https://www.luogu.com.cn/problem/P1102

分析

方法1:暴力求解

将n个数用数组arr存储,使用两层循环,判断arr[i]-arr[j]是否等于c,如果等于,计数器+1,时间复杂度为O(N^2),读题发现N最大为2*10^5,显然超时,此方法不通

方法2:哈希表或者红黑树

A-B==C转换为A==B+C,C是已知的,先遍历一次数组得出B的值,再查询B+C==A中哈希表或红黑树统计的A的出现次数

注意:本题C最大可以取到2^{30},因此int不可以,使用unsigned long long(题目限定是数)

哈希表解法
#include <iostream>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	unordered_map<ull,ull> mp;
	const int N=2e5+10;
	ull n,c,count=0;
	ull arr[N];
	cin>>n>>c;
	for (ull i=0;i<n;i++)
	{
		cin>>arr[i];
		mp[arr[i]]++; 
	}
	for (ull j=0;j<n;j++)
	{
		count+=mp[c+arr[j]];
	}
	cout<<count;
	return 0; 
}
提交结果

红黑树解法

只要把上方代码的unordered_map改成map就行了

#include <iostream>
#include <map>
using namespace std;
typedef unsigned long long ull;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	map<ull,ull> mp;
	const int N=2e5+10;
	ull n,c,count=0;
	ull arr[N];
	cin>>n>>c;
	for (ull i=0;i<n;i++)
	{
		cin>>arr[i];
		mp[arr[i]]++; 
	}
	for (ull j=0;j<n;j++)
	{
		count+=mp[c+arr[j]];
	}
	cout<<count;
	return 0; 
}
提交结果

6.练习题:P3405 [USACO16DEC] Cities and States S

https://www.luogu.com.cn/problem/P3405

分析

一对「特殊」的城市的含义

如下图:

在存储城市和州(州可以理解为省) 的对应关系时,可以使用pair<string,string>,因为题目要求"对于两个城市,它们的前两个字母互为对方所在州的名称"则在存储时只保留城市的前两个字母(即MIAMI的MI,FLINT的FL).

细节处理

"如果他们具有上面的特性,并且来自不同的州"

即对于城市名称的前两个字符串如果和州名相同的,是不能统计的,例如

城市abc州:ab
城市abd州:ab

城市abc和abd都来自ab州,也符合"对于两个城市,它们的前两个字母互为对方所在州的名称"条件,但不能统计进去

代码

红黑树写法

使用红黑树map存储双关键字: map<pair<string, string>, int> mp;

注:如果要按城市和州的对应关系去做,是不能用unordered_map去做的,没有pair<?,?>对应的哈希函数!

//写法1
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<pair<string, string>> arr;
	string tmp1, tmp2;
	map<pair<string, string>, int> mp;
	int n, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp1;
		cin >> tmp2;
		tmp1 = tmp1.substr(0, 2);
			arr.push_back({ tmp1,tmp2 });
		mp[{tmp1, tmp2}]++;
	}
	for (int j = 0; j < n; j++)
	{
		if (mp.count({ arr[j].second, arr[j].first })&&arr[j].first!=arr[j].second)
			cnt += mp[{arr[j].second, arr[j].first}];
	}
	cout << cnt / 2;//cnt一定是偶数,必须/2才可以得到结果
	return 0;
}

//写法2
#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<pair<string, string>> arr;
	string tmp1, tmp2;
	map<pair<string, string>, int> mp;
	int n, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp1;
		cin >> tmp2;
		tmp1 = tmp1.substr(0, 2);
		if (tmp1!=tmp2)
			arr.push_back({ tmp1,tmp2 });
		mp[{tmp1, tmp2}]++;
	}
	for (int j = 0; j < n; j++)
	{
		if (mp.count({arr[j].second, arr[j].first}))
			cnt += mp[{arr[j].second, arr[j].first}];
	}
	cout << cnt/2 ;
	return 0;
}
写法1和2的区别

写法1:一开始可以记录"城市名称的前两个字符串如果和州名相同的"情况到红黑树map,但在统计时不能计入cnt,即:

if (mp.count({ arr[j].second, arr[j].first })&&arr[j].first!=arr[j].second)

写法2:或者可以这样做:一开始在录入map时不记录"城市名称的前两个字符串如果和州名相同的"情况,即

if (tmp1!=tmp2)
	arr.push_back({ tmp1,tmp2 });

这样之后计入cnt时的条件改成这样:

if (mp.count({ arr[j].second, arr[j].first }))

推荐写法2,因为只存储了有效的输入对,减少了arr的大小,空间复杂度比较低

提交结果

写法3

可以在写法2的基础上继续优化,不使用arr数组,而且cnt不用除以2

#include <iostream>
#include <map>
#include <string>
using namespace std;
typedef unsigned long long ull;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string tmp1, tmp2;
	map<pair<string, string>, int> mp;
	int n, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp1;
		cin >> tmp2;
		tmp1 = tmp1.substr(0, 2);
		if (tmp1==tmp2)
			continue;
		mp[{tmp1, tmp2}]++;
		cnt+=mp[{tmp2, tmp1}];
	}
	cout << cnt ;
	return 0;
}
提交结果

哈希表写法

如果强行使用哈希表也是可以的,但不能存储城市和州的对应关系,算法如下:

第一个关键字:存储城市的前两个字母和州拼接后的字符串

第二个关键字:出现的次数

例如MIAMI FL-->存储"MIFL"字符串,其mp["MIFL"]++

#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
using namespace std;
typedef unsigned long long ull;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	string tmp1, tmp2;
	unordered_map<string, int> mp;
	int n, cnt = 0;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> tmp1;
		cin >> tmp2;
		tmp1 = tmp1.substr(0, 2);
		if (tmp1==tmp2)
			continue;
		mp[tmp1+tmp2]++;
		cnt+=mp[tmp2+tmp1];
	}
	cout<<cnt;
	return 0;
}
提交结果


http://www.kler.cn/a/589572.html

相关文章:

  • 定时器‘PWM和串口通信(20250317)
  • cesium 实现万级管网数据渲染,及pickImageryLayerFeatures原生方法改写
  • 网络性能指标
  • 五金打磨车间降温设备都哪些?
  • 在 TypeScript 中,两个看似相同的字符串用 `==` 比较返回 `false`
  • 【Agent】OpenManus-Prompt组件详细分析
  • C3P0数据库连接池技术详解及实战
  • 【网站检测工具Web-Check】Web-Check本地部署与远程访问解决方案全面掌控网站状态
  • CentOS 7 更换 YUM 源为国内
  • Android视频渲染SurfaceView强制全屏与原始比例切换
  • 【Go】go语言指针
  • 计算机网络:(二)计算机网络在我国发展与网络类别与性能 (附带图谱更好对比理解)
  • python | 输入日期,判断这一天是这一年的第几天
  • 基于CPLD电力/轨道交通3U机箱开关量输出板(DO)
  • KV 缓存简介
  • 最长最短单词(信息学奥赛一本通-1143)
  • 京东Taro小程序原生端接入操作
  • 第四十八篇——数学和其它学科:为什么数学是更底层的工具?
  • provide/inject源码实现
  • 光猫 和 全光 WiFi