网站建设企业属于什么类型的公司,网络推广方案的制定流程,中国网络科技公司排名,网络营销软件哪个好用知识概览#xff08;哈希表#xff09; 哈希表可以将一些值域较大的数映射到较小的空间内#xff0c;通常用x mod 质数的方式进行映射。为什么用质数呢#xff1f;这样的质数还要离2的整数幂尽量远。这可以从数学上证明#xff0c;这样冲突最小。取余还是会出现冲突情况。…知识概览哈希表 哈希表可以将一些值域较大的数映射到较小的空间内通常用x mod 质数的方式进行映射。为什么用质数呢这样的质数还要离2的整数幂尽量远。这可以从数学上证明这样冲突最小。取余还是会出现冲突情况。怎么解决冲突呢有两种方式开放寻址法和拉链法。算法题中哈希表的题目可能会有添加、查找操作删除操作较少删除用逻辑删除即用一个bool数组来标识出哪些数已经被删除了。 例题展示
题目链接
https://www.acwing.com/problem/content/842/
代码拉链法
#include iostream
#include cstringusing namespace std;const int N 100010;int h[N], e[N], ne[N], idx;void insert(int x)
{int k (x % N N) % N;e[idx] x;ne[idx] h[k];h[k] idx;
}bool query(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;
}int main()
{int n;scanf(%d, n);memset(h, -1, sizeof h);while (n--){char op[2];int x;scanf(%s%d, op, x);if (*op I) insert(x);else{if (query(x)) puts(Yes);else puts(No);}}return 0;
}
代码开放寻址法
#include iostream
#include cstringusing namespace std;const int N 200003, null 0x3f3f3f3f; // 数组长度设置为题目数据范围的2~3倍且是质数int h[N];int find(int x)
{int k (x % N N) % N;while (h[k] ! null h[k] ! x){k;if (k N) k 0;}return k;
}int main()
{int n;scanf(%d, n);memset(h, 0x3f, sizeof h);while (n--){char op[2];int x;scanf(%s%d, op, x);int k find(x);if (*op I) h[k] x;else{if (h[k] ! null) puts(Yes);else puts(No);}}return 0;
} 知识概览字符串哈希 字符串哈希也称为字符串前缀哈希法它先预处理出所有前缀的哈希值。主要思想是用一个P进制的角度把一个字符串看成一个数字。例如一个字符串ABCD假设A为1B为2C为3D为4则其哈希值为其中P可以取131或13331Q可以取这些是经验值99.99%的情况下不会出现冲突不解决冲突。字符串哈希用来快速判断两个字符串是不是相等。KMP算法可以求循环节除此之外KMP算法不如字符串哈希字符串哈希确实简单直接。 例题展示
题目链接
https://www.acwing.com/problem/content/843/
题解
不用考虑取余溢出相当于取余。
代码
#include iostreamusing namespace std;typedef unsigned long long ULL;const int N 100010, P 131;int n, m;
char str[N];
ULL h[N], p[N];ULL get(int l, int r)
{return h[r] - h[l - 1] * p[r - l 1];
}int main()
{scanf(%d%d%s, n, m, str 1);p[0] 1;for (int i 1; i n; i){p[i] p[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)) puts(Yes);else puts(No);}return 0;
}
