acwing基础课第二章 数据结构
单链表/数组模拟
#include
using namespace std;
const int N = 100010;
int e[N], ne[N]; // e[i]表示第i数的值，ne[i]表示第i个数后面的数
int head, idx; // head表示链表头，idx表示当前用到了哪个节点
void init()
{
head = -1;
idx = 0;
}
// 将x插入到头节点后面
void add2head(int x)
{
e[idx] = x;
ne[idx] = head; // idx节点指向head指向的那个节点
head = idx; // head指向idx节点
idx++;
}
// 在第k个插入的数后面插入x
// k表示的是第k个插入的数，不是当前链表中第k个数
void add(int k, int x)
{
e[idx] = x;
// 下面两句顺序不能变
ne[idx] = ne[k];
ne[k] = idx;
idx++; // 当前节点+1
}
// 删除第k个插入的数后面的数
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
int m;
cin >> m;
while(m --)
{
char op;
int x, k;
cin >> op;
switch(op)
{
case'H':
cin >> x;
add2head(x);
break;
case'D':
cin >> k;
if(!k) head = ne[head];
else remove(k - 1);
break;
case'I':
cin >> k >> x;
add(k - 1, x);
break;
}
}
for(int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
cout << endl;
return 0;
}
数组模拟 栈
#include
using namespace std;
const int N = 1000010;
int stk[N], tt = 0; // stk是栈，tt是栈顶
// 插入
stk[++tt] = x;
// 删除栈顶
tt--;
// 判断是否为空
if(tt > 0) not empty;
else empty;
// 取栈顶
stk[kk]; //
// *************** //
// ......hh......tt....
// 队列
int q[N], hh, tt = -1; // q是队列，hh是头，tt是尾
// 队尾插入
q[++t] = x;
// 删除队首
hh++;
// 判断队列是否为空
if(hh > tt) empty;
else not empty;
// 取队首
x = q[hh];
单调栈
例子： 找到一个数左边第一个比该数小的数
输入样例
5
3 4 2 7 5
输出样例
-1 3 -1 2 2
思路
- 用一个栈保存
a[i]左边的数 - 如果
i < j并且a[i] > a[j]，那么在后面的过程中a[i]在后面永远不会被用到，所以栈中保存的是一个单调递增的序列；所以对于每个a[i]，如果栈不为空(tt>=0)并且栈顶元素大于a[i]（stk[tt] >= a[i]）那么就将栈顶元素删除，直到栈为空或者栈顶元素小于a[i]，输出栈顶元素或者-1 - 然后将
a[i]存入栈中
注意：使用scanf() 最快
代码
#include
using namespace std;
const int N = 1000010;
int stk[N], tt = 0; // stk是栈， tt是栈顶
int a[N];
int n;
int main()
{
scanf("%d ", &n);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < n; i++) {
while(tt && stk[tt] >= a[i]) tt--; // 如果栈不为空，并且栈顶大于a[i]
// 就把栈顶剔除
if(tt) printf("%d ", stk[tt]); // 栈顶不为空的话，说明栈顶就是a[i]左边第一个比a[i]小的数
else printf("-1 ");
// 把a[i]加入到stk中
stk[++tt] = a[i];
}
return 0;
}
单调队列
给定一个大小为 n≤106n≤106 的数组。
有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子：
该数组为 [1 3 -1 -3 5 3 6 7]，k 为 33。
| 窗口位置 | 最小值 | 最大值 |
|---|---|---|
| [1 3 -1] -3 5 3 6 7 | -1 | 3 |
| 1 [3 -1 -3] 5 3 6 7 | -3 | 3 |
| 1 3 [-1 -3 5] 3 6 7 | -3 | 5 |
| 1 3 -1 [-3 5 3] 6 7 | -3 | 5 |
| 1 3 -1 -3 [5 3 6] 7 | 3 | 6 |
| 1 3 -1 -3 5 [3 6 7] | 3 | 7 |
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 nn 和 kk，分别代表数组长度和滑动窗口的长度。
第二行有 nn 个整数，代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出，从左至右，每个位置滑动窗口中的最小值。
第二行输出，从左至右，每个位置滑动窗口中的最大值。
输入样例：
8 3
1 3 -1 -3 5 3 6 7
输出样例：
-1 -3 -3 -3 3 3
3 3 5 5 6 7
思路
首先对于求最小值，和上面单调栈的思路相近，使用一个队列来存放a[i]左边的数的下标（为什么存放的是下标不是数呢，待会下面会讲）
考虑这个队列中的元素和a[i]的大小关系，如果这个队列中有比a[i]大的数，只要a[i]在，那么窗口内比a[i]大的数就不可能被用到，所以我们维护一个单调队列：
- 首先保证这个队列处于窗口内，
- 然后保证队首的元素是当前窗口最小的，队列内的元素单调递增，
- 那么只需要取队首就是窗口内最小元素了。
为什么队列里面存的是下标而不是数呢，因为我们要保证队列中的元素一直处于窗口内，那么就需要知道每个数的下标，根据下标判断队首的元素是不是超过了窗口，所以我们在队列里面存对应数字的下标是最好的方法。
代码
#include
#include
using namespace std;
const int N = 1000010;
int q[N], hh = 0, tt = -1; // hh是头，tt是尾部
int a[N];
int n, k;
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++)
{
// 如果队列头部超过了k的大小，前面的出队
// 因为这里每次窗口只右移动一个，所以每次只需要一个if判断一次head是不是越过了窗口即可
if(hh <= tt && i - k + 1 > q[hh]) hh++;
// 如果队尾大于a[i]，那么需要将队尾移除
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
// 把a[i]的下标i加入到队列
q[++tt] = i;
// 当有k个数之后再输出
if(i+1>=k)
{
printf("%d ",a[q[hh]]);
}
}
puts("");
//输出最大值
// 重置队列
hh = 0, tt = -1;
for(int i = 0; i < n; i++)
{
if(hh <= tt && i - k + 1 > q[hh]) hh++;
while(hh <= tt && a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if(i+1 >= k)
{
printf("%d ",a[q[hh]]);
}
}
return 0;
}
trie树
维护一个字符串集合，支持两种操作：
“I x”向集合中插入一个字符串x；
“Q x”询问一个字符串在集合中出现了多少次。
共有N个操作，输入的字符串总长度不超过 105105，字符串仅包含小写英文字母。
输入格式
第一行包含整数N，表示操作数。
接下来N行，每行包含一个操作指令，指令为”I x”或”Q x”中的一种。
输出格式
对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2?1041≤N≤2?104
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1
//trie树算法
#include
#include
#include
const int N = 1000010;
using namespace std;
int son[N][26], cnt[N], idx;
// son[][]存储树中每个节点的子节点，
// cnt[i]表示该单词i的出现次数
// idx表现当前用到了哪个节点，idx单调递增
void insert(char * str)
{
int p = 0; // parent
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx; // idx = 0 是根节点root
p = son[p][u]; // 继续该单词的下一个节点
}
cnt[p]++;
}
int query(char * str)
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if(!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
}
int main()
{
int n;
scanf("%d", &n);
char op[2];
char str[N];
while(n--)
{
scanf("%s%s",op,str);
if(op[0] == 'I') insert(str);
else printf("%d\n", query(str));
}
return 0;
}
并查集
堆
模拟散列表
拉链法
// 拉链法存/查 hash表
// 取模的最好使用质数
#include
#include
#include
using namespace std;
const int N = 100003; // 大于100000的最小质数
int h[N], e[N], ne[N], idx;
// h[]表示散列表
// e[] ne[] idx是单链表里面的
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;
// 这里的-1，是因为初始化的时候将h[k]都初始化成了-1
for(int i = h[k]; i != -1; i = ne[i])
{
if(e[i] == x) return true;
}
return false;
}
int main()
{
memset(h, -1, sizeof(h));
int n;
scanf("%d",&n);
while(n--)
{
char op[2];
int a;
scanf("%s%d", op, &a);
if(op[0] == 'I')
{
insert(a);
}
else
{
if(find(a)) puts("Yes");
else puts("No");
}
}
return 0;
}
开放寻址法
#include
#include
#include
using namespace std;
const int N = 200003; // 通常开2~3倍
const int null = 0x3f3f3f3f; // h初始化成它
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()
{
memset(h, 0x3f, sizeof(h)); // memset按照字节初始化，h是int类型，所以初始化完之后就是0x3f3f3f3f
}
字符串hash
实质就是将一个字符串映射成整数
方便判断两个字符串是否相等
给定一个长度为n的字符串，再给定m个询问，每个询问包含四个整数 l1,r1,l2,r2 ，请你判断[ l1,r1 ]和[ l2,r2 ]这两个区间所包含的字符串子串是否完全相同。
字符串中只包含大小写英文字母和数字。
输入格式
第一行包含整数n和m，表示字符串长度和询问次数。
第二行包含一个长度为n的字符串，字符串中只包含大小写英文字母和数字。
接下来m行，每行包含四个整数 l1,r1,l2,r2 ，表示一次询问所涉及的两个区间。
注意，字符串的位置从1开始编号。
输出格式
对于每个询问输出一个结果，如果两个字符串子串完全相同则输出“Yes”，否则输出“No”。
每个结果占一行。
数据范围
1 ≤ n, m ≤ 105
输入样例：
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2
输出样例：
Yes
No
Yes
思路
依据经验，我们使得数值尽量重复时需要限定:
1.p最好是131或者13331
2.对数值%(226)，我们刚好采取unsigned long long 溢出时的状态也是一致的
这样几乎没有可能重复从而冲突
将字符串的前缀转换为数来存值
由于每位的权值是不一样的 所以每个前缀值都对应着唯一的一种字符串
所以相减后的值也应该是唯一的 从而利用相减后的值可以判断字符串的区间段是否相等
————————————————
版权声明：本文为CSDN博主「ken的信徒」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43910320/article/details/107718725
代码：
#include
#include
#include
using namespace std;
// 小技巧：取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果
typedef unsigned long long ULL;
const int N = 100010;
char str[N];
ULL h[N], p[N]; // h表示一个字符串的前缀和
// p表示各个位的权重
int P = 131; // 131 或者 13331
ULL get(int l, int r)
{
return h[r] - h[l-1]*p[r-l+1];
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
scanf("%s",str+1);// 因为前面可能空格？
for(int i = 1; i < n; i++ )
{
p[0] = 1;
for(int i = 1; i <= n; i++)
{
p[i] = p[i-1] * P; // h[i]表示各位的权重
h[i] = h[i-1]*P + str[i]; // h[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;
}