1.并查集的功能
1.将两个集合进行合并
2.询问两个元素是否在一个集合里面
2.并查集的基本原理
基本原理：每一个集合用一棵树来表示，树根的编号就是整个集合的编号，每一个点存储的都是其父节点，p[x]表示的就是x的父节点
要考虑的问题有三个
问题一：如何判断树根 if(p[x]==x)
问题二：如何求x的集合编号 while(p[x]!=x) x=p[x]
问题三：如何合并两个结合 p[x]是x的集合编号，p[y]是y的集合编号,p[x]=y;表示x的父节点是y
3.并查集的实现
并查集，查找两个元素，是否在一个集合里面，而且可以将两个集合合并
//首先要设置全员变量 using namespace std; const int n = 100010; int n,m; int p[N];//p[N]来存储的是父节点 //寻找操作 int find (int x) { if(p[x]!=x) p[x]=find (p[x]); return p[x];//如果x的父节点不是x的时候，就要将p[x]放在find函数里面去，用p[x]来接收，直到最后p[x]==x ，递归返回之后，这个结合的所有结点的父节点都是x } //相当于 返回x的祖宗结点，并且有路径压缩 //如果说我们输入”M“来表示将两个集合合并 int main() { scanf("%d%d",&n,&m); //输入n个数字，进行m次操作 for(int i = 1;i <= n; i++ ){ p[i]=i;//首先让n个结点的父节点都是自己本身，因为初始的时候每一个结点就是一个集合 } while(m--){ char op[2];//输入操作的字符 int a,b;//指定的两个结点 scanf("%s%d%d",op,&a,&b); if(op[0]=='M'){ p[find(a)]=find(b);//将两个集合合并，可以先找到a，b的祖宗结点，这样讲a祖宗结点的父节点设置为b的祖宗结点，这样两个集合合并 } else {//op不是M的时候，就是要进行判定ab是否是在一个集合里面 //如果是I 表示判断是否两个结点在一个集合里面 if(find(a)==find(b)){ printf("Yes\n"); }else { printf("NO\n"); } } } return 0; }
哈希表（hash）
哈希表常用的两个方式来存储数据, 拉链法和开放寻址法
哈希表的原理就是将一个很大范围中的数字,放置在一个小范围的数组中存储起来.
可以实现的功能为1.存储 2.查找
比如-109 ~109 存放在一个范围为0~105 的数组中存储起来
操作流程
1.先进行mod 取模,得到一个数字,存放在一个数组中
2.因为对于这些数据,会有冲突的时候,所以对于多个数据取模得到一个数值,使用拉链法,数组的每一个槽都可以对应一个链表形式的结构,通过这个结构,将取模相同的元素,放在这个槽对应的链表中,然后在查找的过程中近似实现O(1)的操作
我们mod的时候使用的数字应该是个质数,如果处理在0-100000范围内的数据,那么就要找到大于100000的最小质数
查找mod数值的方法为:
int getInteger(int n){//n传递为100000 while(n++){ for(int j=2;j*j<=n;j++){ if(n%j==0){ break; } } } return n; }
1.拉链法
操作的流程,在c/c++中需要自行用数组来表示链表,在Java中可以使用LinkedList来表示链表
我们使用c++来举例
using namespace std; const int n=100003;//我们提前找到了这个大于最大范围的最小质数 int h[N],e[N],ne[N],idx; //h[N]用来存储模的数值 //e[N]用来形成链表,存储的数值 //ne[N]用来得到当前N下标对应的下一个数值 //idx表示链表的下标 //我们要实现的是,输入一个n,表示有n个操作,如果是输入"I x"表示插入数值x,如果是"Q x"实现查找x,查找到x 输出Yes 没有输出No #include<string.h> #include<stdio.h> #include<iostream> void insert(int x){ int k=(x % N + N ) % N;//取模,x%N可能为负值,所以+N,然后再mod N //得到k就是要存储在槽中的数值h[N],就是找到位置 e[idx]=x;//用当前下标idx存储数值为x ne[idx]=h[k];//然后idx的下一个坐标为h[k]的位置也就是说,头插 h[k]=idx;//然后h[k]=idx h[k]就相当于头节点 idx++;//添加一个元素idx++; } bool find(int x){ int k=( x % N + N ) % N ; for(int i=h[k];i!=-1;i=ne[i]){ //得到x的存储在槽终点 位置h[k],然后查询链表 if(x==e[i]){ return true; } } return false; } int main() { int n; scanf("%d",&n); //表示输入n个操作 memset(h,-1,sizeof(h));//对于h[N]数组进行赋值为-1 while(n--){ char op[2]; int x; scanf("%s%d",op,&x); if(op=='I'){//插入存储数值x insert(x); }else { //进行查找x if(find(x)){ printf("Yes\N"); }else{ printf("No\n"); } } } return 0; }
拉链法的主要内容是
1.得到k的数值,然后在h[k]数组上加上链表,使用e[idx]数组来存储数值x,用ne[idx]=h[k],h[k]=idx来实现头插,最后idx++;
//插入的算法 void insert(int x){ int k=(x % N + N) % N; e[idx]==x; ne[idx]=h[k]; h[k]=idx; idx++; }
2.我们对于h[N]数组初始化的时候赋值为-1,但是在插入数据的时候,会头插,将idx的数值赋值给了h[N]数组
//查询的时候的代码 bool find(int x){ int k=(x % N + N) % N; for(int i=h[k];i!=-1;i=ne[i]){ if(e[i]==x){ return true; } } return false; }
拉链法主要是插入函数insert和find函数.
2.开放寻址法
开放寻址法的主要方式为: 开辟的数组的发小是输入数据范围的2,3倍
方法流程
1.先找到一个合适的质数
2.插入方法为,在存储数据的时候通过hash函数,得到k,然后存储
3.进行查找
代码演示
using namespace std; const int N=100003; int null=0x3f3f3f3f;//设定一个极大值 int h[N];//存储数值的数组 int find(int x){ int k=(x % N + N) % N; while(h[k]!=null && h[k]!=x){ //如果说是不为null不为x,表示没有存储过这个数值 k++;//没找到就k++ if(k==N) k=0;//如果等于N,那就从头0开始 } return k;//找到了就返回的k值 } int main() { int n;//表示n个操作数 scanf("%d",&n); memset(h,0x3f,sizeof(h)); //memset 作用是对于一个地址进行赋值,可以指定大小,指定数值 //函数有三个参数 //第一个是 输入地址,比如h表示数组地址,第二个参数是存放数值,这个是存放一个字节的数值,如果是int 数组,那就是4个0x3f //第三个参数是数组大小,也就是要赋值的范围 while(n--){ char op[2]; int x; scanf("%s%d",op,&x); int k= find(x); if(op[0]=='I'){ h[k]=x;//进行插入数值x }else{ //判断是否有x在数组里面 if(h[k]!=null) printf("Yes\n"); else printf("No\n"); } } return 0; }
3,字符串哈希
类似于kmp 但是可以实现查找字符串到O(1),基本上更好
字符串hash的用法步骤是:
1.使用p进制,类似于10进制这样,用h[0],h[1]….来存储前n个字符串的p计数
2.使得一串字符,得到一个数字 p进制,有个经验值为131或者是13331;如果是abcd 那就是(a *p[3]+b*p[2]+c*p[1]+d*p[0]) % Q Q也有经验值 为264 因为用h数组存储哈希值，264 可以用unsigned long long来表示,如果大于264 会超出存储范围 ，自动模值
那就是直接 unsigned long long h[n]=a*p[3]+b*p[2]+c*p[1]+d*p[0] 即可
3.然后如果是想要得到 l 到 r 之间的字符串哈希,前段为高位,后端为低位,如果是r>1 那么就是让 h [ l-1 ] *p[ r- l +1 ] 然后h[r]-h[l-1]*p[r-l+1]
代码如下
using namespace std; typedef unsigned long long ULL; const int N=100010,p=131; int n,m; char str[N]; ULL h[N],p[N]; //题目要求 第一行输入n m str[N] 表示为 n为字符串长度 m为比较次数 str为字符串数组 //接下来m行 输入l1 r1 l2 r2 比较 l1到r1 l2到r2 这两段字符串是否相等 ULL get(int l,int r){ return h[r]-h[l-1]*p1[r-l+1]; } int main() { scanf("%d%d%s", &n, &m, str + 1); //str数组从1开始 // p[0] = 1; //得到数字 for (int i = 1; i <= n; i++) { p[i] = p1[i - 1] * p; h[i] = h[i - 1] * p + str[i]; } while (m--) { int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2); if (get(l1, r1) == get(l2, r2)) printf("Yes\n"); else printf("No\n"); } return 0; }
