前言:
在复习hash表的时候遇到了困难，这玩意儿实在是太抽象了。
我感觉这种与数学沾染了的算法与数据结构，都会变得很抽象。
这里讲的是自己手写hash表，而不是stl库中的hash表。
主要是因为有时候引用了stl的undered_map可能会超时，所以下面来模拟一下映射与寻址。
概述:
手写hash表有两种方法，这里讲的是开放寻址法。
开放寻址法
先定义一个hash数组
1
| int h[N];//N为数据范围的2倍以上，越大映射得越好。
|
接下来便是开放寻址
1
2
3
4
5
6
7
8
| int find(int x){
int t=x(x%M+M)%M;//映射到hash数组上
while(h[t]!=-1&&h[t]!=x){//寻址的过程
if(++t==m)
t=0;
}
return t;
}
|
实践:
接下来我们直接上一道蓝桥杯的难题以供大家理解hash表
题目:
在一个二维平面上放置着 n个炸雷，第 i个炸雷 (xi,yi,ri)表示在坐标 (xi,yi)处存在一个炸雷，它的爆炸范围是以半径为 ri的一个圆。
为了顺利通过这片土地，需要玩家进行排雷。
玩家可以发射 m个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j个排雷火箭 (xj,yj,rj)表示这个排雷火箭将会在 (xj,yj)处爆炸，它的爆炸范围是以半径为 rj的一个圆，在其爆炸范围内的炸雷会被引爆。
同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷？
你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。
代码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
using namespace std;
typedef long long LL;
const int N=5e4+5,M=2e5+7,X=1e9+1;
class circle{
public:
int x,y,r;
}c[N];
int id[M];
LL h[M];
bool st[M];
int n,m;
LL get_value(int x,int y){//将坐标映射成一维数据
return x*X+y;
}
LL find(int x,int y){
int value=get_value(x,y);
int t=(value%M+M)%M;//找到相应hash数组下标
while(h[t]!=-1&&h[t]!=value){//如果该下标有数据同时hash数组的val值不等于value往后找
if(++t=M)//当从t搜索到末尾还没有，从头开始搜索
t=0;
}
return t;
}
int sqr(int x){
return x*x;
}
void dfs(int x,int y,int r){
st[find(x,y)]=true;//该点的炸雷已经引爆过
for(int xx=x-r;xx<=x+r;xx++){
for(int yy=y-r;yy<=y+r;yy++){
if(sqr(yy-y)+sqr(xx-x)<=sqr(r)){
int t=find(xx,yy);
if(!st[t]&&id[t]){
dfs(xx,yy,c[id[t]].r);
}
}
}
}
}
int main(){
cin>>n>>m;
memset(h,-1,sizeof h);//初始化hash数组
for(int i=1;i<=n;i++){
int x,y,r;
cin>>x>>y>>r;
c[i]={x,y,r};
int t=find(x,y);
while(h[t]==-1)h[t]=get_value(x,y);
if(!id[t]||c[id[t]].r<r){//该点没有过炸雷，或者之前的炸雷半径比现在的小
id[t]=i;//该坐标有炸雷
}
}
while(m--){
int x,y,r;
cin>>x>>y>>r;
for(int xx=x-r;xx<=x+r;xx++){
for(int yy=y-r;yy<=y+r;yy++){
if(sqr(xx-x)+sqr(yy-y)<=sqr(r)){//判断是否在圆内
int t=find(xx,yy);
if(!st[t]&&id[t]){//该点没有被dfs过，同时该点有炸雷
dfs(xx,yy,c[id[t]].r);
}
}
}
}
}
int res=0;
for(int i=1;i<=n;i++){//遍历每个炸雷，统计被引爆的炸雷
if(st[find(c[i].x,c[i].y)]){//若炸雷被引爆,res++;
res++;
}
}
cout<<res;
return 0;
}
|
