Oudasheng 2020-04-11
memset是按字节来初始化的,int中有四个字节,初始化成0x3f就是将每个字节都初始化成0x3f,所以每个int就是 0x3f3f3f3f
通过哈希函数h(x)
这个函数可以映射到某个位置
离散化是极其特殊的哈希方式。因为他要有序
拉链的长度都比较短。一般没有删除
只有添加和查找某个数
删除的话就在那个位置做一个标记,开一个bool变量
做哈希的时候,数组长度,一般来说是一个质数
#include <cstdio> #include <iostream> #include <string.h> using namespace std; const int maxn = 1e5 + 3; int h[maxn], edx[maxn], ne[maxn], idx; // h[k]表示第k位数字指向的下一位地址 // ne[idx]表示第idx位数字的地址是多少 void insert(int x) { int k = (x % maxn + maxn) % maxn; edx[idx] = x; ne[idx] = h[k]; h[k] = idx; idx++; } bool find(int x) { int k = (x % maxn + maxn) % maxn; for (int i = h[k]; i != -1; i = ne[i]) // 空指针用-1来表示 if (edx[i] == x) return true; return false; } int main() { int n; char op[2]; cin >> n; memset(h, -1, sizeof h); // -1表示指向的下一个节点是空 while (n -- ) { //exit(0); int x; scanf("%s%d", op, &x); if(!strcmp(op, "I")) // *op == ‘I‘ { insert(x); } if(!strcmp(op, "Q")) { if(find(x)) puts("Yes"); else puts("No"); } } return 0; }
一般要开2-3倍的位置
上厕所一个道理,找不到厕所就找下一个,下一个还找不到就再下一个。最后的还找不到就去第一个
#include <cstdio> #include <iostream> #include <string.h> using namespace std; const int maxn = 200003, null = 0x3f3f3f3f; int h[maxn]; int find(int x) { int k = (x % maxn + maxn) % maxn; while (h[k] != null && h[k] != x) // 如果相同的话就返回相同的位置 { k ++ ; if (k == maxn) k = 0; } return k; } int main() { int n; char op[2]; cin >> n; memset(h, 0x3f, sizeof h); // -1表示指向的下一个节点是空 while (n -- ) { //exit(0); int x; scanf("%s%d", op, &x); int k = find(x); if(!strcmp(op, "I")) // *op == ‘I‘ { h[k] = x; } if(!strcmp(op, "Q")) { // if (h[k] != null) puts("Yes"); // else puts("No"); // 可能是k不在范围内,只要求了mod,肯定在正常范围内 if (h[k] == null) puts("No"); else puts("Yes"); } } return 0; }
时间复杂度是\(O(1)\) 但是用到哈希表的题目都是$ O(N)$
大部分的题目都是赋值成-1,0,0x3f
想做的事情就是把字符串变成数字
这样能直接通过数字来比较两个字符串是否相等
计算某一段的哈希值的时候比如
ABDCA
我要取出CA
根据定义分别求出\(hash[i]\)
$ hash[1]=s1$
$ hash[2]=s1?p+s2$
\(hash[3]=s1?p^2+s2?p+s3\)
\(hash[4]=s1?p^3+s2?p^2+s^3?p+s4\)
$ hash[5]=s1?p4+s2?p3+s3?p^2+s4?p+s5$
现在我们想求\(s_3s_4\) 的\(hash\)值,不难得出为\(s_3 * p +s_4\) ,并且从上面观察,如果看\(hash[4]?hash[2]\)并将结果种带有\(s_1,s_2\),系数的项全部消掉,就是所求。但是由于\(p\)的阶数,不能直接消掉,所以问题就转化成,将\(hash[2]\)乘一个关于\(p\)的系数,在做差的时候将多余项消除,从而得到结果。
不难发现,对应项系数只差一个\(p^2\)
,而\(4 - 3 + 1 = 2\)(待求\(hash\)子串下标相减再加一),这样就不难推导出来此例题的求解式子。
快速判断两个字符串是否相等(把字符串变成数字)
用公式算出字串的哈希值
h[]表示某一前缀的哈希值
#include <cstdio> #include <iostream> using namespace std; typedef unsigned long long ULL; // 用unsigned long long就不需要取模了 const int maxn = 1e5 + 10, P = 131; ULL p[maxn], h[maxn]; char str[maxn]; int n, m; // h[i] = h[i - 1] * p + str[i]; // h[r] - h[l - 1] * p[r - l + 1]; l - r之间有几个数字 ULL get(int l, int r) { return h[r] - h[l - 1] * p[r - l + 1]; } int main() { int n, m; p[0] = 1; cin >> n >> m; scanf("%s", str + 1); for (int i = 1; i <= n; i ++ ) { p[i] = p[i - 1] * P; // P进制 h[i] = h[i - 1] * P + str[i]; // 移动了一位之后,ascii码不会超过P } while (m -- ) { int l1, l2, r1, r2; cin >> l1 >> r1 >> l2 >> r2; if(get(l1, r1) == get(l2, r2)) puts("Yes"); else puts("No"); } return 0; }
KMP可以求字符串的循环节
坐在马桶上看算法