第二章 数据结构
一、链表与邻接表
1.1、静态链表
首先在C++中链表可以使用结构体struct来实现,在Java中使用类class来实现,属于动态链表;使用数组来模拟链表,属于静态链表。
//head 头节点的下标
//e[i]表示节点i 的值
//ne[i] 表示节点i的next指针是多少
//idx 当前已经用到了那个点 : curr
#include<iostream>
using namespace std;
const int N = 100010;
//静态链表
//数组模拟链表:快
int head,e[N],ne[N],idx;
//初始化
void init(){
head = -1;
idx = 0;
}
//将x插到头节点
void add_to_head(int x){
e[idx] = x;
ne[idx] = head;
head = idx;
idx++;
}
//将x插入第k个之后
void add(int k, int x){
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
//删除k
void remove(int k){
ne[k] = ne[ne[k]];
}
int main(){
int m;
cin>>m;
init();
while(m--){
int k,x;
char op;
cin >> op;
if(op == 'H'){
cin >> x;
add_to_head(x);
}else if(op == 'D'){
cin >> k;
if(!k){
//k=0 删除头节点
head = ne[head];
}
remove(k - 1);
}else{
cin >> k >> x;
add(k - 1,x);
}
}
for(int i = head;i != -1;i = ne[i]){
cout<<e[i]<<' ';
}
cout<<endl;
return 0;
}
使用数组实现双链表:
二、栈与队列
2.1、单调栈
单调栈可用于在数组中寻找每一个数左边离他最近最小的数。
问题:在数组中寻找每一个数左边离他最近最小的数。
首先我们想到的是暴力解法:时间复杂度O(n^2),优化思路:在往左端查找最小值 j 时,我们知道如果a[i-1] >= a[i]
那么a[i-1]
在以后的查询中就不可能为所找的最小值,因为存在比他小的a[i]
,故在栈stack
中保存a[i]
; 当a[i]
需要在栈中寻找最近最小值时,从栈的top
开始出发,如果stk[top] >= a[i]
那么也跟上述情况一样去掉栈顶元素top--
,知道找到stk[top] < a[i]
,如果top==-1,也就是说没有即输出-1
for(int i = 0;i < n;i++){
for(int j = i - 1;j >= 0;j--){
if(a[j] < a[i]){
cout<<a[j]<<' ';
}
}
}
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int n;
int stk[N],top;
int main(){
cin>>n;
for(int i = 0;i < n;i++){
int x;
cin >> x;
while(top && stk[top] >= x){
top--;
}
if(top){//不为空
cout << stk[top] << ' ';
}else{
cout << -1 << ' ';
}
top++;
stk[top] = x;
}
return 0;
}
2.2、单调队列–滑动窗口
问题:给定一个大小为 n≤106n≤106 的数组。有一个大小为 k 的滑动窗口,它从数组的最左边移动到最右边,求该滑动窗口中的最大值和最小值。
#include<iostream>
using namespace std;
const int N = 1000010;
int n,k;
int a[N],q[N];
int main(){
scanf("%d%d",&n,&k);
for(int i = 0;i < n;i++){
scanf("%d",&a[i]);
}
int head = 0,tail = -1;
for(int i=0;i < n;i++){
//判断队头是否已经滑出窗口
//head <= tail :队列不为空
//i - k + 1 > q[head] i走到了k之外
if(head <= tail && i - k + 1 > q[head]){
head++;
}
// 判断队列队尾元素 是否 >= 当前a[i],
/*
当队尾元素a[q[tail]] >= a[i] 说明a[q[tail]] 不是当前最小值
tail--
*/
while(head <= tail && a[q[tail]] >= a[i]){
tail--;
}
//将当前元素添加进队列中
tail++;
q[tail] = i;
// i >= k - 1 是判断是否需要输出
if( i >= k - 1){
printf("%d",a[q[head]]);
}
}
//----------------------------------------------------
head = 0,tail = -1;
for(int i=0;i < n;i++){
//判断队头是否已经滑出窗口
if(head <= tail && i - k + 1 > q[head]){
head++;
}
// 判断队列队尾元素 是否 >= 当前a[i],
while(head <= tail && a[q[tail]] <= a[i]){
tail--;
}
//将当前元素添加进队列中
tail++;
q[tail] = i;
// i >= k - 1 是判断是否需要输出
if( i >= k - 1){
printf("%d",a[q[head]]);
}
}
return 0;
}
三、KMP
问题:给定一个模式串 S,以及一个模板串 P,所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串 P 在模式串 S 中多次作为子串出现。
求出模板串 P 在模式串 S 中所有出现的位置的起始下标。
其实就是求子串 P 在 S中出现的位置,首先想到暴力算法:s[i]与p[j] 一个一个进行对比,在遇到不匹配的情况下i++,时间复杂度O(n^2)
for(int i = 1;i <= n;i++){
bool flag = true;
for(int j = 1;j <= m;j++){
if(s[i + j - 1] != p[j]){
flag = false;
}
}
if(flag){
cout<<i<<'';
}
}
优化思路,在进行匹配时如果遇到不匹配的情况,不是直接i++,而是在已经匹配的p[j]中寻找最长的相同前后缀,前后缀相同且已经与s[i]匹配,那么拿出最长的后缀位置作为i跳转下标
S = "abcabcabdd"
P = "abcabdd"
P[j] = "abcabd" //时d不匹配,那么说明前面的abcab一定是匹配的,找到"abcab"最长的相同前后缀作为下一次匹配的前缀即"abcab" --> "ab"
#include<iostream>
using namespace std;
const int N = 1000010;
int n,m;
char s[N],p[N];
int ne[N];
int main(){
cin>>n>>p+1>>m>>s+1;
// 求 next 的过程
for(int i = 2,j = 0;i <= n;i++){
// j 表示匹配成功的长度,i表示q数组中的下标
//由于q数组下标从1开始,i==1时,一定为0
while(j && p[i] != p[j + 1]){
//不匹配就跳到ne[j]
j = ne[j];
}
if(p[i] == p[j + 1]){
//成功匹配 + 1
j++;
}
ne[i] = j;
//保存下标
}
//kmp匹配过程
// j表示匹配成功的长度
for(int i = 1,j = 0;i <= m;i++){
//如果匹配不成则跳到ne[j]
while(j && s[i] != p[j + 1]){
j = ne[j];
}
//匹配成功j+1
if(s[i] == p[j + 1]){
j++;
}
if(j == n){
//匹配成功
printf("%d ",i - j);
j = ne[j];
//
}
}
return 0;
}
四、Tire树
Tire树:快速存储和查找字符串集合的数据结构
#include<iostream>
using namespace std ;
const int N = 100010;
// 0号点既是根节点,又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
int son[N][26],cnt[N],idx;
char str[N];
void insert(char str[]){
int p = 0;
//son[][] 表示结点
for(int i = 0;str[i];i++){
int u = str[i] - 'a';//用数字保存字母
if(!son[p][u]){ //如果该结点没有值的话
son[p][u] = ++ idx; //idx表示son指向的下标
}//这里使用idx与静态链表类似,son二维数组保存结点不是连续的
//p指向子节点
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);
while(n--){
char op[2];
scanf("%s%s",op,str);
if(op[0] == 'I'){
insert(str);
}else{
printf("%d\n",query(str));
}
}
return 0;
}
4.1、异或 (xor)
- 异或:按位运算相同为 0 不同为 1
- 首先异或操作:二进制按位运算,相同位0,不同位1
- 总结:具有分支寻找、存储这类特征的可以使用Tire数
a[i] = 110110010
a[j] = 111101100
a[i] ^ a[j] = 001011110
//1、暴力算法
for(i = 0 ;i < n;i++){
for(j = 0;j < i;j++){
res = max{res , a[i] ^ a[j]}
}
}
//2、Tire树
//我们知道了异或的运算操作后,便可以得知,想要得到res = max{res , a[i] ^ a[j]},那么就是找到从末位与a[i] 尽量不同的a[j]
//a[i] = 110110010 --> 期望得到001001101 从tire树中寻找尽量靠近的数
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10,M = 31 * N;
int n;
int a[N];
int son[M][2],idx;
void insert(int x){
//如何取出数x 的第i位二进制数
int p = 0;
//int 31位 0...30
for(int i = 30;i >= 0;i--){
int u = x >> i & 1;
if(!son[p][u])son[p][u] = ++idx;
p = son[p][u];
}
}
int query(int x){
int p = 0, res = 0;
for(int i = 30;i >= 0;i--){
int u = x >> i & 1;
if(son[p][!u]){
p = son[p][!u];
res = res * 2 + !u;
//路径
}else{
p = son[p][u];
res = res * 2 + u;
}
}
//路径 res res * 2表示左移一位比如1101 --> 11010
// 然后再加上u --> 1101u
return res;
}
int main(){
scanf("%d",&n);
for(int i = 0;i < n;i++) scanf("%d",&a[i]);
int res = 0;
for(int i = 0;i < n;i++){
insert(a[i]);
int t = query(a[i]);
res = max(res,a[i] ^ t);
}
printf("%d",res);
return 0;
}
五、并查集
5.1、并查集操作:
- 将两个集合合并
- 询问两个元素是否在一个集合中
5.2、基本原理:
- 每个集合用一棵树表示,树根的编号就是整个集合的编号,每个结点存储它的父节点,p[x]表示父节点
- 问题1:如何判断树根:if(p[x] == x)
- 问题2:如何求x 的集合编号,while(p[x] != x) x = p[x]
- 问题3:如何合并两个集合: px 是 x 的集合编号【根】,py 是 y 的集合编号:p[x] = y
优化:降低树的高度,路径压缩
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N];
// 返回 x 所在集合编号p 加上路径压缩
int find(int x){
if(p[x] != x){
p[x] = find(p[x]);
}
return p[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 0;i < n;i++){
p[i] = i;
}
while(m--){
//op[2] 过滤掉一些空格回车 在输入字符 字符串的时候会出现异常
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0] == 'M'){
p[find(a)] = find(b);
}else{
if(find(a) == find(b)){
puts("Yes");
}else{
puts("No");
}
}
}
return 0;
}
5.3并查集的应用:1、求集合内元素数量
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int p[N],mysize[N];
// 返回 x 所在集合编号p 加上路径压缩
int find(int x){
if(p[x] != x){
p[x] = find(p[x]);
}
return p[x];
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 0;i < n;i++){
p[i] = i;
mysize[i] = 1;
}
while(m--){
//op[2] 过滤掉一些空格回车 在输入字符 字符串的时候会出现异常
char op[5];
int a,b;
scanf("%s",op);
if(op[0] == 'C'){
scanf("%d%d",&a,&b) ;
if(find(a) == find(b)){
continue;
}
mysize[find(b)] += mysize[find(a)];//维护mysize
p[find(a)] = find(b);
}else if(op[1] == '1'){
scanf("%d%d",&a,&b);
if(find(a) == find(b)){
puts("Yes");
}else{
puts("No");
}
}else{
scanf("%d",&a);
printf("%d\n",mysize[find(a)]);
}
}
return 0;
}
5.4、求解集合合并类
//使用并查集维护食物链
AcWing 240. 食物链
六、堆
堆的操作:下标从 1 开始
- 插入一个数 heap[ ++size ] = x
- 求集合中的最小值 小根堆的root : heap[1]
- 删除最小值 删除root,把最后一个元素放回root的位置 进行down/up操作 heap[1] = heap[size] ;size–;down(1);
- 删除任意一个元素 heap[k] = heap[size];size–;down(k);up(k);
- 修改任意一个元素 heap[k] = x; down(k);up(k);
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n,m;
int h[N],mysize1;
void down(int u){
int t = u;
//判断以u为子树三个元素水谁最小
if(u * 2 <= mysize1 && h[u * 2] < h[t])t = u * 2;
if(u * 2 + 1 <= mysize1 && h[u * 2 + 1] <h[t]) t = u * 2 + 1;
if(u != t){
swap(h[u],h[t]);//交换
down(t);//对t进行down
}
}
void up(int u){
while(u / 2 && h[u / 2] > h[u]){
swap(h[u / 2],h[u]);
u /= 2;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i = 1;i<=n;i++){
scanf("%d",&h[i]);
}
mysize1 = n;
//给定数组h 那么我们如何构建堆呢 可以一个一个插入 O(nlongn)
for(int i = n / 2;i ; i--){
down(i);
}
while(m--){
printf("%d ",h[1]);
h[1] = h[mysize1];
mysize1--;
down(1);
}
return 0;
}
七、哈希表
给定-10^9 ~~ 10^9
范围,通过哈希函数映射到 0 ~ 10^5
,离散化一般来说用于具有单调性的数列,是特殊的哈希化。
- 一般来说 x mod 10^5 :且一般取质数,离2的整次幂越远越好,减少哈希冲突的概率
- 可能会出现哈希冲突
- 哈希表的存储结构:拉链法 开放寻址法
- 字符串哈希方式
拉链法 和 开放寻址法
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 100003;
int h[N],e[N],ne[N],idx;
void insert(int x){
//如果是负数取模 那么结果会是负数 + N 变成整数 再 % N 去掉N
//正数 x % N + N = N
//负数 x % N + N
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(){
int n ;
scanf("%d",&n);
//清空h数组
memset(h,-1,sizeof h);
while(n--){
char op[2];
int x;
scanf("%s%d",op,&x);
if(op[0] == 'I')insert(x);
else{
if(find(x)){
puts("Yes");
}else{
puts("No");
}
}
}
return 0;
}
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
const int N = 200003,null = 0x3f3f3f3f;
int h[N];
//开放寻址法:当发送冲突就查找下一位
void insert(int x){
//如果是负数取模 那么结果会是负数 + N 变成整数 再 % N 去掉N
//正数 x % N + N = N
//负数 x % N + N
int k = (x % N + N) % N;
}
int find(int x){
int k = (x % N + N) % N;
//!= null 表示已经被占
//h[k] != x 表示占位置的不是自己 : 用于重复查找的情况
while(h[k] != null && h[k] != x){
k++;
if(k == N){
k = 0;
}
}
return k;
}
int main(){
int n ;
scanf("%d",&n);
//按字节赋值 int 4个字节 所以是0x3f0x3f0x3f
memset(h,0x3f,sizeof h);
while(n--){
char op[2];
int x;
scanf("%s%d",op,&x);
int k = find(x);
if(op[0] == 'I'){
h[k] = x;
}
else{
if(h[k] != null){
puts("Yes");
}else{
puts("No");
}
}
}
return 0;
}
字符串哈希
计算一些字符串类型的题目
str = "ABCABCDEFGZXCAcwing"
h[0] = 0;
h[1] = "A"; //"A"的hash值
h[2] = "AB";
h[3] = "ABC";
h[4] = "ABCA";
//那么如何计算"A"的hash值:即有字符串-->数字
//假设P进制 和 Q P = 131 或者 13331 | Q =2^64
(A,B,C,D) = (1,2,3,4) = 1*P^3 + 2*P^2 + 3*P^1 + 4*P^0;
//前缀和
h[i] = h[i - 1] * P + str[i];
//保存P进制次数 从高位到低位
p[i] = p[i - 1] * P;
//计算[l,r] 区间内的字符串前缀hash
h[r] - h[l -1] * p[r - l + 1];
#include<iostream>
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];
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;
}
STL
vector, 变长数组,倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front() / back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算,按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算,以first为第一关键字,以second为第二关键字(字典序)
string,字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标,(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列,默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式:priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树(红黑树),动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继,时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x,删除所有x O(k + logn)
(2) 输入一个迭代器,删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似,增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound(), 迭代器的++,--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反