进入江苏省住房和城乡建设厅网站首页,焦作网站建设兼职,郑州网站建设行情,农大南路网络营销推广优化今天看网课学习了哈希的数据结构#xff0c;写下这一篇博客记录自己的学习过程。
1.哈希简介#xff1a; 我们发现某些时候映射到小集合的时候会同时有多个值映射到一个下标里面#xff0c;所以接下来是这种情况的解决方案1#xff1a; 我们考虑当两个数字映射之后的结果…今天看网课学习了哈希的数据结构写下这一篇博客记录自己的学习过程。
1.哈希简介 我们发现某些时候映射到小集合的时候会同时有多个值映射到一个下标里面所以接下来是这种情况的解决方案1 我们考虑当两个数字映射之后的结果是在同一个下标的时候那么不妨可以将第二个映射到这个下标的数字往后移动到第一个空白的下标里面。
实际上上面这一种解决问题的方式存在较大的问题当冲突之后后移的话会导致对应下标里面的值不再是本身应该映射到这个下标里面的值了。
所以考虑到第一种值冲突解决问题在有些情况的不适用那么接下来介绍第二种值冲突的解决方案 接下来详细介绍vector可以理解为动态数组 这样的方法可以理解为开设了多个链表每个下标都相当于是一条链表实际上虽然这种方法已经解决了绝大多数的问题但是当遇见特殊的样例也就是样例映射之后全部都在一个下标的时候一样是存在问题的。
接下来看一下哈希函数的设计 接下来看一下字符串如何进行哈希操作 另外请思考
令base为11会导致值冲突加剧另外发生值冲突我们考虑双哈希甚至三哈希等多次哈希操作来解决也就是设置多个base以及p的值这样的话只有当多组的base和p计算出来的值都相同的时候我们才会认为两个字符串相同。 接下来看一下c中自带的hash 接下来来看一些例题 代码如下
#includebits/stdc.h
using namespace std;
int n,m;
const int P9999971;//要模的素数
int a[200001],b[200001];
vectorintc[P];
int main(){cinnm;//存下两篇论文的长度for(int i0;iP;i)//将所有的链表数组清空c[i].clear();for(int i1;in;i){cina[i];c[a[i]%P].push_back(a[i]);//存下第一篇论文中所有的数字}int x0;for(int i1;im;i){cinb[i];bool okfalse;//假设这个数字不是抄袭的int vb[i]%P;int lc[v].size();//判断假设是否成立for(int j0;jl !ok;j)if(c[v][j]b[i]) oktrue;if(ok) x;//如果成立 抄袭的部分加一}//判断被标记的抄袭的论文部分是否大于了一半if(2*xm) coutYesendl;else coutNoendl;return 0;
}
这里还有一种使用map的方法
#includebits/stdc.h
using namespace std;
int n,m;
const int P9999973;
int a[200001],b[200001];
unordered_mapint,intc;
int main(){cinnm;c.clear();for(int i1;in;i){cina[i];c[a[i]]1;}int x;for(int i1;im;i){cinb[i];if(c.find(b[i]) ! c.end()) x;}if(x*2m) coutYesendl;else coutNoendl;return 0;
}
接下来再看第二个题 很明显这里是使用map这是我的代码
#includebits/stdc.h
using namespace std;
int n,m;
unordered_mapstring,inta;
unordered_mapstring,intb;
unordered_mapstring,intc;
int main(){cinnm;a.clear();b.clear();c.clear();for(int i1;in;i){string s;cins;int x,y,z;cinxyz;a[s]x;b[s]y;c[s]z;}for(int i1;im;i){string s;cins;if(a.find(s)a.end()) cout-1 -1 -1endl;else couta[s] b[s] c[s];}return 0;
}
但是会发现上面的代码使用了三个map来分别存身高年龄专业编码实际上这三个都可以通过一个结构体来存储
#includebits/stdc.h
using namespace std;
int n,m;
struct Info{int x,y,z;
};
unordered_mapstring,Infoa;
int main(){cinnm;a.clear();for(int i1;in;i){string s;cins;Info temp;cintemp.xtemp.ytemp.z;a[s]temp;}for(int i1;im;i){string s;cins;if(a.find(s) ! a.end()) couta[s].x a[s].y a[s].zendl;else cout-1 -1 -1endl;}return 0;
}
ok接下来看下一道题目 #includebits/stdc.h
using namespace std;
int n;
unordered_mapint,intc;
int a[200001];
int main(){scanf(%d,n);c.clear();for(int i1;in;i){int x;cinx;c[x];}int x0,l0;for(auto temp : c){if(temp.secondx){xtemp.second;l0;}if(temp.secondx) a[l]temp.first;}sort(a1,al1);for(int i1;il;i)couta[i] ;return 0;
} 这道题目看似很简单实则还是有一定难度的。正常人思路肯定一开始都是利用数组来存储每个数字出现的次数然后最后遍历数组容量更新出现次数最多的数字如果遇上多个相同大的那就利用一个数组和一个判断长度l的变量来进行不断更新和便于之后的输出。
接下来看第四题 代码如下
#includebits/stdc.h
using namespace std;
int n;
unordered_mapint,intc;
int main(){cinn;c.clear();for(int i1;in;i){int x;cinx;c[x];}int x0;bool addfalse;for(auto temp : c){if(temp.second 1) addtrue;xtemp.second/2*2;}if(add) x;coutxendl;return 0;
}
最后一个题目了 代码如下
#includebits/stdc.h
using namespace std;
int n,m;
const int p9999973,base101;
int ha[200010],hb[200010],c[200010];
char a[200010],b[200010];
int main(){scanf(%d%d,n,m);scanf(%s%s,a1,b1);c[0]1;for(int i1;i200000;i)c[i]c[i-1]*base%p;for(int i1;in;i)ha[i](ha[i-1]*base(a[i]-a))%p;for(int i1;im;i)hb[i](hb[i-1]*base(b[i]-a))%p;int ans0;for(int i1;im-1n;i)if((ha[im-1]-1LL*ha[i-1]*c[m]%pp)%phb[m])ans;printf(%d\n,ans);return 0;
}
以上是一个单哈希的写法c数组代表了base的i次方的值而ha和hb分别包含了长度为i子串的哈希值最后一个for循环进行遍历计算有b子串在a子串出现了多少次。然后输出答案接下来介绍一个双哈希的写法
#includebits/stdc.h
using namespace std;
int n,m;
const int p9999973,base101;
const int p29999973,base2137;
int ha[200010],hb[200010],c[200010],c2[200011],ha2[200011],hb2[200011];
char a[200010],b[200010];
int main(){scanf(%d%d,n,m);scanf(%s%s,a1,b1);c[0]1;c2[0]1;for(int i1;i200000;i){c[i]c[i-1]*base%p;c2[i]c2[i-1]*base2%p2;}for(int i1;in;i){ha[i](ha[i-1]*base(a[i]-a))%p;ha2[i](ha2[i-1]*base2(a[i]-a))%p2;}for(int i1;im;i){hb[i](hb[i-1]*base(b[i]-a))%p;hb2[i](hb2[i-1]*base2(b[i]-a))%p2;}int ans0;for(int i1;im-1n;i)if((ha[im-1]-1LL*ha[i-1]*c[m]%pp)%phb[m] (ha2[im-1]-1LL*ha2[i-1]*c2[m]%p2p2)%p2hb2[m])ans;printf(%d\n,ans);return 0;
}
希望今天的学习记录笔记同样对读者有所帮助。
