【AcWing】算法基础课-数据结构
目录
1、单链表
实现单链表实际上有两种方式
第一种是使用结构体+指针，称为动态链表，在面试中是可以使用的，但是在算法题中因为new太慢了，所以不推荐使用
第二种是使用数组模拟，称为静态链表，我们这里用的就是静态链表
静态链表有几个参数：
数组e表示某个点的值
数组ne表示某个点的next指针
head是头指针，链表为空时用-1
idx表示当前使用到了哪一个点
#include<iostream>
#include<stdio.h>
using namespace std;
const int N = 1e5 + 10;
int e[N], ne[N], head, idx, n;
void init()
{
head = -1;
idx = 0;
}
void push_front(int x)
{
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
void insert(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
void erase(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
scanf("%d", &n);
while(n--)
{
int k, x;
char ch;
cin>>ch; // 不要使用scanf，因为缓冲区
// while(scanf(" %c", &ch) != 1 || ch == ' '); 若要使用scanf，就这样
if(ch == 'H')
{
scanf("%d", &x);
push_front(x);
}
else if(ch == 'D')
{
scanf("%d", &k);
if(!k) head = ne[head];
else erase(k - 1);
}
else
{
scanf("%d %d", &k, &x);
insert(k - 1, x);
}
}
for(int i = head;i != -1;i = ne[i]) printf("%d ", e[i]);
printf("\n");
return 0;
} 注意：
（1）insert中是将x插到下标为k的结点的后面
（2）删除第k个插入，就是删除下标为k-1的，因为第1个插入，下标为0
（3）对于头删需要特殊处理，否则head没变
2、双链表
（1）双链表是让下标为0的点为头结点，下标为1的点为尾结点。刚初始化完就已经有2个结点了，所以idx是从2开始的
（2）因为idx是从2开始的，所以我们在处理第k个插入时，传参时下标时k + 1
#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int e[N], l[N], r[N], idx, m;
void init()
{
r[0] = 1,l[1] = 0;
idx = 2;
}
void insert_r(int k, int x)
{
e[idx] = x;
l[idx] = k;
r[idx] = r[k];
l[r[k]] = idx;
r[k] = idx++;
}
void insert_l(int k, int x)
{
/*e[idx] = x;
r[idx] = k;
l[idx] = l[k];
r[l[k]] = idx;
l[k] = idx++;*/
insert_r(l[k], x); // 后面3个直接复用insert_r即可
}
void push_front(int x)
{
/*e[idx] = x;
l[idx] = 0;
r[idx] = r[0];
l[r[0]] = idx;
r[0] = idx++;*/
insert_r(0, x);
}
void push_back(int x)
{
/*e[idx] = x;
r[idx] = 1;
l[idx] = l[1];
r[l[1]] = idx;
l[1] = idx++;*/
insert_l(1, x);
}
void erase(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
init();
scanf("%d", &m);
while(m--)
{
string ch;cin>>ch;
if(ch == "L")
{
int x;scanf("%d", &x);
push_front(x);
}
else if(ch == "R")
{
int x;scanf("%d", &x);
push_back(x);
}
else if(ch == "D")
{
int k;scanf("%d", &k);
erase(k + 1);
}
else if(ch == "IL")
{
int x, k;scanf("%d%d", &k, &x);
insert_l(k + 1, x);
}
else
{
int x, k;scanf("%d%d", &k, &x);
insert_r(k + 1, x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
return 0;
}3、栈
3.1 模拟栈
tt是栈顶下标，初始化tt为-1
#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int st[N], tt;
void init()
{
tt = -1;
}
void push(int x)
{
st[++tt] = x;
}
void pop()
{
--tt;
}
bool empty()
{
return tt == -1;
}
int query()
{
return st[tt];
}
int main()
{
init();
int m;scanf("%d", &m);
while(m--)
{
string s;cin>>s;
if(s == "push")
{
int x;scanf("%d", &x);
push(x);
}
else if(s == "pop") pop();
else if(s == "empty")
{
if(empty()) printf("YES\n");
else printf("NO\n");
}
else printf("%d\n", query());
}
return 0;
}3.2 表达式求值
这道题看起来是很简单的，明显就是开两个栈，一个栈用来存数字，一个栈用来存符号，当遇到右括号就拿出两个数和一个符号来计算，再将计算结果放入栈，直到左括号。最后直到存放符号的栈为空，存放数字的栈中有唯一的数，这个数就是答案。
这样是不对的，没有考虑到运算的优先级，乘除法的优先级是高于加减法的。如2 * 3 + 5，按上面的思路，最终存数字的栈2 3 5，存符号的栈* +，我们会先算加法，导致出错
为了考虑优先级，此时有4步。开一个存数字的栈num，存符号的栈op
考虑优先级主要有两条规则：
优先级高的要比优先级低的先计算
优先级相同的要从左向右依次计算
(1)遇到数字，放入num
(2)遇到'('，放入op
(3)遇到')'，从num中取出两个数，从op中取出一个符号，计算完再将结果放入num，直到op的栈顶是'('，然后将'('弹出栈
(4)遇到+、-、*、/，要看一下op栈顶的符号的优先级是否大于等于当前的符号，若大于等于，要先计算，直到op栈顶的符号优先级低于当前符号。像上面的2 * 3 + 5，我们遍历到+时，num里面是2 3，op里里面是*，*的优先级明显高于+，所以我们要先计算，直到op的栈顶元素的优先级低于+，第一次计算后，num里面是6，op里面没有元素了，直接放入+，此时就先计算了*。注意：这一步为什么要有等于，因为我们计算优先级相同的运算符时需要从左向右依次计算，比方说0 - 5 + 8，如果没有等于，会先计算5 + 8，结果是-13，明显是错的
#include<iostream>
#include<stack>
#include<unordered_map>
#include<string>
using namespace std;
stack<int> num;
stack<char> op;
unordered_map<char, int> cmp = {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; // 存放个运算符的优先级
void equl() // 计算过程
{
int a = num.top(); num.pop();
int b = num.top(); num.pop();
char x = op.top(); op.pop();
int k = 0;
if(x == '+') k = a + b;
else if(x == '-') k = b - a;
else if(x == '*') k = a * b;
else k = b / a;
num.push(k);
}
int main()
{
string s; cin>>s;
for(int i = 0;i < s.size();i++)
{
char ch = s[i];
if(isdigit(ch))
{
int k = ch - '0', j = i + 1;
while(j < s.size() && isdigit(s[j]))
k = k * 10 + (s[j++] - '0');
num.push(k);
i = j - 1;
}
else if(ch == '(') op.push('(');
else if(ch == ')')
{
while(op.size() && op.top() != '(') equl();
op.pop();
}
else
{
while(op.size() && cmp[op.top()] >= cmp[ch]) equl();
op.push(ch);
}
}
// 此时剩余的运算符都是优先级低的，因为优先级低的运算符放入栈前要先将优先级高的弹出
while(op.size()) equl();
cout << num.top() << endl;
return 0;
}4、队列
hh表示队头下标，tt表示队尾下标，hh初始化为0，tt初始化为-1
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int q[N], hh, tt;
void init()
{
hh = 0, tt = -1;
}
void push(int x)
{
q[++tt] = x;
}
void pop()
{
++hh;
}
bool empty()
{
return tt < hh;
}
int query()
{
return q[hh];
}
int main()
{
init();
int m;scanf("%d", &m);
while(m--)
{
string s;cin>>s;
if(s == "push")
{
int x;scanf("%d", &x);
push(x);
}
else if(s == "pop") pop();
else if(s == "empty")
{
if(empty()) printf("YES\n");
else printf("NO\n");
}
else printf("%d\n", query());
}
return 0;
}5、单调栈
这道题很容易就能想到暴力解法，两层for循环，这样的时间复杂度明显是O(N^2)的
我们需要对其就行优化。
假设我们当前遍历到下标为i的位置，可以用一个栈来存储i左边的所有元素。此时会发现有一些元素是没有用的，假设i>5，此时栈中有a[3] >= a[5]，我们现在是要找离下标i最近的一个，且比a[i]小的，a[3]离a[i]比a[5]离a[i]更远，且a[3] >= a[5]，所以在i以及后面的所有数中，都不可能会用到a[3]，所以可以直接将a[3]从栈中删除
现在思路就变成了，遍历到a[i]，看一下栈顶元素是否大于等于a[i]，若栈顶元素大于等于a[i]，那么a[i]之后的元素一定不会用到这个栈顶元素，直接将栈顶元素删除，然后继续比较，直到找到一个栈顶元素小于a[i]，输出，并将a[i]放入栈中。当然也有可能a[i]在与栈中元素比较过程中，栈中元素弹出完了还没有找到比a[i]小的元素，此时直接输出-1，然后将a[i]放入栈中
只要按照这个思路执行，这个栈就是单调的，以这道题找左边最近的较小值为例，这个栈是单调递增的
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int st[N], tt = -1;
int main()
{
int n;scanf("%d", &n);
while(n--)
{
int x;scanf("%d", &x);
while(tt != -1) // 只要栈不为空就一直找比x小的
{
if(st[tt] < x)
{
printf("%d ", st[tt]);
break;
}
else --tt;
}
if(tt == -1) printf("-1 "); // 栈弹出完了输出-1
st[++tt] = x; // 将x入栈
}
return 0;
}这里使用的是数组模拟的栈，数组模拟的栈可以不用像前面模拟栈中写成各个函数，在做题时直接写反而更简便些。这里也可以使用STL中的stack，不过这样不如直接使用数组模拟的快。
这样，我们对于每一个元素最多出栈一次、入栈一次，所以时间复杂度是O(N)
6、滑动窗口
我们以输出窗口中的最小值为例，输出最大值是类似的，这道题很容易想到的就是每次遍历一遍窗口，这样时间复杂度是O(k*n)。
这个窗口是从前面出，后面进，所以我们可以用一个队列来模拟这个窗口。我们会发现有一些值是没有用的，假设我们现在的遍历到的元素是-3，从队头弹出一个元素后，队列中的值是-5，1，我们会发现1 > -3，并且1在-3的左边，也就是说对于-3往后遍历到的值，1在的时候-3一定也在，所以1是没用的，直接弹出，现在队列中剩下-5，-5比-3小，不需要管，将-3放入队列，此时-5就是这个队列中最小的。
现在思路就变成了，遍历到a[i]，若下标已经大于等于3(下标从0开始)，先弹出队头元素，若小于3，则不需要弹出。比较一下a[i]与队尾元素的大小，若队尾元素大于等于a[i]，直接弹出，直到找到一个比a[i]小的或者弹出完了，就将a[i]放入。只要根据这个规则，这个队列就一定是单调的，像这道题，队列就是单调递增的，最小的元素就是队头元素
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int a[N], q[N], hh, tt, n, k; // q是存下标
int main()
{
scanf("%d%d", &n, &k);
for(int i = 0;i < n;i++) scanf("%d", &a[i]);
hh = 0, tt = -1;
for(int i = 0;i < n;i++)
{
// 判断队头是否需要滑出窗口,hh<=tt是保证队列不为空，i-k+1>q[hh]是保证队列中元素最多只有3个
if(hh <= tt && i - k + 1 > q[hh]) hh++;
while(hh <= tt && a[q[tt]] >= a[i]) tt--; // 如果队尾数据大于等于a[i],则弹出
q[++tt] = i;
if(i >= k - 1) printf("%d ", a[q[hh]]); // 当窗口中只有第1个数或前两个数时是不会输出的
}
printf("\n");
hh = 0, tt = -1; // 一定要记得恢复
for(int i = 0;i < n;i++)
{
// 判断队头是否需要滑出窗口,hh<=tt是保证队列不为空，i-k+1>q[hh]是保证队列中元素最多只有3个
if(hh <= tt && i - k + 1 > q[hh]) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--; // 如果队尾数据大于等于a[i],则弹出
q[++tt] = i;
if(i >= k - 1) printf("%d ", a[q[hh]]); // 当窗口中只有第1个数或前两个数时是不会输出的
}
return 0;
}7、KMP字符串
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
char p[N], s[M];
int ne[N];
int n, m;
int main()
{
cin >> n >> p + 1 >> m >> s + 1;
// 构建next数组
for (int i = 2, j = 0; i <= n; i++)
{
while (j && p[i] != p[j + 1]) j = ne[j]; // 当不匹配时就一直回退，直到匹配或者j == 0
if (p[i] == p[j + 1]) j++; // 如果回退到了匹配的位置,j++
ne[i] = j;
}
// 匹配原数组
for (int i = 1, j = 0; i <= m; i++)
{
while (j && s[i] != p[j + 1]) j = ne[j]; // 当不匹配时就一直回退，直到匹配或者j == 0
if (s[i] == p[j + 1]) j++; // 如果回退到了匹配的位置,j++
if (j == n) // p数组遍历完了
{
printf("%d ", i - n); // 打印起始位置
j = ne[j]; // 遍历完成后回退到ne[j]的位置继续匹配
}
}
return 0;
}8、Trie字符串统计
方法一
使用Trie树，Trie树快速存储和查找字符串集合的一种数据结构
一般字符串集里的字符都是全小写、全大写或全数字
一般会在一个单词结尾的位置打上标记
查询时不仅要看这个单词能否走完，还要看走完时有没有标记
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int son[N][26], cnt[N], idx; // 下标是0的点，既是根节点，也是空结点
char str[N];
void insert(char str[])
{
int p = 0;
for(int i = 0;str[i] != '\0';i++)
{
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx; // 如果没有这个子节点，那就插入
p = son[p][u]; // 再从现在的结点向下移动一个结点
}
cnt[p]++;
}
int query(char str[])
{
int p = 0;
for(int i = 0;str[i] != '\0';i++)
{
int u = str[i] - 'a';
if(!son[p][u]) return 0; // 如果没有这个子节点返回0
p = son[p][u]; // 若有这个子节点则移动到子节点
}
return cnt[p]; // 返回以p这个结点为结尾的字符个数
}
int main()
{
int n;
scanf("%d", &n);
while(n--)
{
char op[2];
scanf("%s%s", op, str);
if(op[0] == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}son --- 存每个结点的子节点，因为这道题里面字符串都是小写字母，所以每个字母最多向外延申26条边
cnt --- 以当前字母结尾的单词有几个
0是根节点，一个结点没有下一个结点也会让其下一个为0
方法二
使用map
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main()
{
int n;scanf("%d", &n);
map<string, int> mp;
while(n--)
{
char ch;
string s;
cin>>ch>>s;
if(ch == 'I')
{
int x = mp.count(s);
if(x == 0) mp.insert({s, 1});
else mp[s]++;
}
else
{
int x = mp.count(s);
if(x == 0) cout<<x<<endl;
else cout<<mp[s]<<endl;
}
}
return 0;
}9、并查集
并查集主要能够完成两个操作：
1. 将两个集合合并
2. 询问两个元素是否在一个集合当中
通过并查集完成这两个操作可以将时间复杂度控制在近乎O(1)
基本原理：每个集合用一颗树存储。树根的编号就是这颗树的编号。每个结点存储它的父结点，p[x]表示x的父结点。
问题一：如何判断一个结点是否是树根：if(p[x] == x)，结果为真就是树根
问题二：如何求x所在集合编号：while(p[x] != x) x = p[x]; 先看一下这个点的父结点是否是根，若不是则一直往上找，直到找到根，根的编号就是集合的编号
问题三：如何合并两个集合：px、py分别是x、y的集合编号。p[px] = py。合并两个集合，实际上就是将一个集合变成另一个集合的子树，这里就是将x所在集合变成y所在集合的子树。
此时将两个集合合并的时间复杂度是O(1)，但是询问两个元素是否在一个集合中的时间复杂度并不是O(1)，所以此时需要进行路径压缩优化
路径压缩：当找一个点的祖先时，直接将这个点以及这个点到祖先路径上的所有点都指向根
这样在下一次寻找路径上的点时，就能做到O(1)的时间复杂度了
9.1 合并集合
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N];
int find(int x) // 返回x所在集合的编号 + 路径压缩
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i++) p[i] = i; // 最先开始每个集合都只有一个元素
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所在集合的子树
else
{
if(find(a) == find(b)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}9.2 连通块中点的数量
这道题与上一道题是类似的，只是这道题还需要维护每一个集合有几个元素
在a和b之间连一条边就是将a和b所在集合合并，若a和b相等则不进行操作
连通块是指a可以到b，b也可以到a，就说明a和b在一个连通块中，判断a和b是否在一个连通块中，实际上就是判断a和b是否在一个集合中
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int p[N], sz[N]; // sz数组表示的是每一个集合的大小，只保证集合的根节点有意义
int find(int x) // 返回x所在集合的编号 + 路径压缩
{
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1;i <= n;i++)
{
p[i] = i;
sz[i] = 1;
}
while(m--)
{
char op[5];
int a, b;
scanf("%s", op);
if(op[0] == 'C')
{
scanf("%d%d", &a, &b);
if(find(a) != find(b)) // 只有当a和b在两个不同集合时才进行操作
{
sz[find(b)] += sz[find(a)]; // b集合的大小需要加上a集合的大小
p[find(a)] = find(b); // 将a集合变成b集合的子树
}
}
else if(op[1] == '1')
{
scanf("%d%d", &a, &b);
if(find(a) == find(b)) printf("Yes\n");
else printf("No\n");
}
else
{
scanf("%d", &a);
printf("%d\n", sz[find(a)]);
}
}
return 0;
}10、堆
堆主要有5个操作：
1. 插入一个数 heap[++size] = x; up(size);
2. 求集合当中的最小值 heap[1];
3. 删除最小值 heap[1] = heap[size]; size--; down(1);
4. 删除任意一个元素 heap[k] = heap[size]; size--; down(k)或up(k)
5. 修改任意一个元素 heap[k] = x; down(k)或up(k)
这里删除任意一个元素是将这个元素与堆的最后一个元素交换，然后让size--，此时有3种可能性，若不变，则不需要任何操作，若变小了需要向上调整，变大了需要向下调整。为了简便代码，可以不管这些，直接down一遍，再up一遍，最多只会执行一个。修改任意一个元素同理。
注意：堆要从1开始存放数据，若从0，0*2=0
10.1 堆排序
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int h[N], sz;
void down(int u) // u是下标
{
int t = u; // 用t在记录最小的那个数的下标
if(2 * u <= sz && h[2 * u] < h[t]) t = 2 * u;
if(2 * u + 1 <= sz && h[2 * u + 1] < h[t]) t = 2 * u + 1;
if(t != u)
{
swap(h[u], h[t]);
down(t);
}
}
void up(int u) // 这道题不需要用到向上调整法，写在这里只是为了记忆，因为下道题会对down和up进行修改
{
while(u / 2 != 0 && h[u] < h[u / 2])
{
swap(h[u], h[u / 2]);
u /= 2;
}
}
int main()
{
scanf("%d %d", &n, &m);
for(int i = 1;i <= n;i++) scanf("%d", &h[i]);
sz = n;
// 使用向下调整法来建堆
for(int i = n / 2;i > 0;i--) down(i);
while(m--)
{
printf("%d ", h[1]);
swap(h[1], h[sz]);
sz--;
down(1);
}
return 0;
}10.2 模拟堆
这道题很关键的一个点就是，它是删除、修改第k个插入的数，而我们将元素放进堆后，顺序全被打乱了，根本不知道一个元素是第几个插入的，所以此时就需要使用一个ph数组存放数据，ph[k]表示第k个插入的数在堆中的下标是几。此时仍然是不够的，因为我们现在已经知道了第k个插入的数在堆中的下标是几，但是我们不知道堆中的一个数是第几个插入的，所以还需要有一个hp数组，hp[k]表示下标为k的点是第几个插入的点
我们现在要交换这两个点，不仅仅要交换这两个点的值，还需要交换hp，但是我们此时只知道这两个点在堆中的下标，要如何通过下标去找到ph呢？是没有办法的，所以要有hp，通过hp找到ph，ph也是要交换的。
#include<iostream>
#include<algorithm>
#include <string.h>
using namespace std;
const int N = 1e5 + 10;
int n, m; // m记录是第几个插入的点
int h[N], ph[N], hp[N], cnt; // cnt用来记录当前堆中有几个元素
void heap_swap(int a, int b) // 交换下标为a、b的元素，此时交换就不仅仅交换h[a]、h[b]，还要交换hp、ph
{
swap(ph[hp[a]], ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u) // u是下标
{
int t = u; // 用t在记录最小的那个数的下标
if(2 * u <= cnt && h[2 * u] < h[t]) t = 2 * u;
if(2 * u + 1 <= cnt && h[2 * u + 1] < h[t]) t = 2 * u + 1;
if(t != u)
{
heap_swap(u, t); // 交换的地方都要换
down(t);
}
}
void up(int u) // 这道题不需要用到向上调整法，写在这里只是为了记忆，因为下道题会对down和up进行修改
{
while(u / 2 != 0 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u /= 2;
}
}
int main()
{
int n, m = 0;
scanf("%d", &n);
while (n -- )
{
char op[5];
int k, x;
scanf("%s", op);
if (!strcmp(op, "I"))
{
scanf("%d", &x);
cnt ++ ;
m ++ ;
ph[m] = cnt, hp[cnt] = m;
h[cnt] = x;
up(cnt);
}
else if (!strcmp(op, "PM")) printf("%d\n", h[1]);
else if (!strcmp(op, "DM"))
{
heap_swap(1, cnt);
cnt -- ;
down(1);
}
else if (!strcmp(op, "D"))
{
scanf("%d", &k);
k = ph[k];
heap_swap(k, cnt);
cnt -- ;
up(k);
down(k);
}
else
{
scanf("%d%d", &k, &x);
k = ph[k];
h[k] = x;
up(k);
down(k);
}
}
return 0;
}带映射的堆并不常用，但是Dijkstra算法需要用到
11、哈希表
11.1 模拟散列表
哈希表就是能够将数据范围非常庞大的数据，通过哈希函数计算后，映射到一个相对较小的数据范围内的数据结构。如将数据范围在[-10^9, 10^9]的数据通过哈希函数映射到[0, 10^5]内。看起来十分像离散化，实际上离散化是一种特殊的哈希，离散化映射是需要保序的，这里讨论的是一般的哈希。而在将原始数据通过哈希函数映射的过程中，有可能有两个数通过哈希函数映射后的值是相等的，也就是发生了哈希冲突。解决哈希冲突的方法有两种，拉链法和开发寻址法，所以，实现哈希表的方法也有两种
拉链法
一般使用拉链法建立的哈希表只提供两种操作，插入元素和查找元素，不会支持删除元素，若要删除元素也可以，新开一个数组记录一下每个结点的情况，并不会真正的去链表中删除
这里为了避免哈希冲突，取模的数，也就是哈希表中存放链表根节点的数要是一个质数，并且这个质数要离2的整次幂尽可能的远，这样能将哈希冲突降到最低。这道题最多有10^5个数，所以我们先来计算一下比10^5的的第一个质数
int main()
{
for(int i = 100000;;i++)
{
bool flag = true;
for(int j = 2;j * j <= i;j++)
if(i % j == 0)
{
flag = false;
break;
}
if(flag)
{
cout<< i <<endl;
break;
}
}
return 0;
}结果是100003，所以我们哈希表的数组开100003
注意C++中的负数取模结果也是负数，-10 % 3 = -1，所以取模后一定要让数大于0，因为我们开了100003个空间，取模后的结果范围应该在[0, 100003)
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1e5 + 3;
int h[N], e[N], ne[N], idx, n; // h数组就是哈希表，h[k] = -1表示这个链表为空，h[k]就是这个链表头结点的下标，就是单链表那一个题的head
void Insert(int x)
{
int k = (x % N + N) % N; // 让余数变成正数
e[idx] = x;
ne[idx] = h[k];
h[k] = idx++;
}
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;
}
int main()
{
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(find(x)) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}开放寻址法
开放寻址法开的数组大小要是数据的2到3倍，删除操作与拉链法类似
这道题的数据范围最大是10^5，所以我们找大于20000的第一个质数
int main()
{
for(int i = 200000;;i++)
{
bool flag = true;
for(int j = 2;j * j <= i;j++)
if(i % j == 0)
{
flag = false;
break;
}
if(flag)
{
cout<< i <<endl;
break;
}
}
return 0;
}结果是200003
开放寻址法重点是定义一个find函数，这个find函数若x在哈希表中，返回x在哈希表中的位置，若不在哈希表中，则返回其应该存储的位置
要定义一个不在数据范围内的数，表示位置没有数
memset是按字节进行赋值的
#include<iostream>
#include<cstring>
using namespace std;
const int N = 2e5 + 3, null = 0x3f3f3f3f; // 定义null来表示一个位置没有数
int h[N], n;
int find(int x) // 找到了返回x在哈希表中的位置，没找到返回应该放入的位置
{
int k = (x % N + N) % N;
while(h[k] != null && h[k] != x) // 当映射到的位置有值，并且这个值与x不相等时，往后找
{
k++;
if(k == N) k = 0;
}
return k;
}
int main()
{
scanf("%d", &n);
memset(h, 0x3f, sizeof(h)); // 按照字节赋值，0x3f3f3f3f，有4个字节，每个字节都是0x3f
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] == x) printf("Yes\n");
else printf("No\n");
}
}
return 0;
}11.2 字符串哈希
这道题我们可以预处理出一个所有前缀的哈希值,当要比较两个区间的字符串是否相等时,我们只需要比较这两个区间的哈希值是否相等。这里说的哈希值就是每个字符串通过哈希函数映射后的结果
计算字符串所有前缀的哈希值
给的是一个字符串，我们要如何计算出前缀的哈希值呢？
我们采用的方法是将这个字符串看成是一个p进制数，哈希函数就是将p进制数转成十进制数，计算出的十进制数就是哈希值
通常p会取131或13331。因为p比较大，而且字符串可能会非常长，所以需要取模，取模通常取2^64，这样哈希冲突会最低
我们取p=131，来计算一下ABCD所有前缀的哈希值
计算子区间的哈希值
我们现在计算出了这个字符串的所有前缀哈希值，那要如何用这些前缀哈希值去求某一个子区间的哈希值呢？
能使用这种计算方法是因为将字符串ABCD看成p进制数A是高位，D是低位
因为我们上面取模是取的2^64，所以这个哈希表需要用usinged long long来存储，无符号类型可以利用栈溢出来达到取模的效果，所以在代码中并没有取模的操作
#include <iostream>
#include <algorithm>
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]; // p数组用来存P的次方，如p[2] = 131 ^ 2
ULL get(int l, int r) // 计算区间哈希值的函数
{
return h[r] - h[l - 1] * p[r - l + 1];
}
int main()
{
scanf("%d%d", &n, &m);
scanf("%s", str + 1);
p[0] = 1; // 131 ^ 0 = 1
for (int i = 1; i <= n; i ++ ) // 预处理出前缀和
{
h[i] = h[i - 1] * P + str[i]; // 这里既有大小写也有数字，所以使用ASCII值来计算
p[i] = p[i - 1] * P;
}
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;
}更多推荐
31
0- 0
已为社区贡献5条内容
所有评论(0)