AcWing数据结构-创新互联

1. 单链表 head表示头节点的下标,e[i]表示节点i的值,ne[i]表示节点i的next指针是多少 （节点i的下一个位置在什么地方） idx存储当前已经用到了哪个点
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指向的位置
    head = idx; // head指向插入新指针的位置
    idx ++; // idx指向下一个位置
}
将x插到下标是k的点后面
void add(int k, int x) {e[idx] = x; // 存新指针的值
    ne[idx] = ne[k]; // 新指针指向k点的下一个位置
    ne[k] = idx; // k点的下一个位置指向新插入点的位置
    idx ++; // idx指向下一个位置
}
将头节点删除，需要保证头节点存在
void remove () {head = ne[head];
}
将下标是k的点后面的点删掉
void remove(int k) {ne[k] = ne[ne[k]];
}
遍历链表
for(int i = head; i != -1; i = ne[i])
2. 双链表
int e[N], l[N], r[N], idx;
在点a的右边插入x
void add(int a, int x) {e[idx] = x;
	l[idx] = a, r[idx] = r[a];
	l[r[a]] = idx, r[a] = idx ++;
}
删除点a
void remove(int a) {l[r[a]] = l[a];
    r[l[a]] = r[a];
}
遍历链表
for (int i = r[0]; i != 1; i = r[i])
3. 栈 插入:
stk [++ tt] = x;
弹出：
tt --;
判断栈是否为空:
if(tt >0) not empty;
else empty;
查询栈顶:
stk[tt]; // tt存的栈顶元素
4. 队列 在队尾插入元素，在队头弹出元素:
int q[N], hh, tt = -1; // hh表示队头，tt表示队尾
插入:
q[++ tt] = x;
弹出:
hh ++;
判断队列是否为空:
if(hh<= tt) not empty 
else empty
取出队头元素:
q[hh];
取出队尾元素:
q[tt];
5. 单调栈
常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i<= n; i ++ ) {while (tt && check(stk[tt], i)) {tt -- ;
    }
    stk[ ++ tt] = i;
}
6. 单调队列
常见模型：找出滑动窗口中的大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i< n; i ++ ) {while (hh<= tt && check_out(q[hh])) {hh ++ ;  // 判断队头是否滑出窗口
    }
    while (hh<= tt && check(q[tt], i)) {tt -- ;
    }
    q[ ++ tt] = i;
}
7. KMP
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
// 求模式串的Next数组：
for (int i = 2, j = 0; i<= m; i ++ ) {while (j && p[i] != p[j + 1]) {j = ne[j];
    }
    if (p[i] == p[j + 1]) {j ++ ;
    }
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i<= n; i ++ ) {while (j && s[i] != p[j + 1]) {j = ne[j];
    }
    if (s[i] == p[j + 1]) {j ++ ;
    }
    if (j == m) {j = ne[j];
        // 匹配成功后的逻辑
    }
}
8. Trie
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str) {int p = 0;
    for (int i = 0; str[i]; 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]; i ++ ) {int u = str[i] - 'a';
        if (!son[p][u]) {return 0;
        }
        p = son[p][u];
    }
    return cnt[p];
}
9. 并查集 朴素并查集：
int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x) {if (p[x] != x) {p[x] = find(p[x]);
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i<= n; i ++ ) {p[i] = i;
}
// 合并a和b所在的两个集合：
p[find(a)] = find(b);
维护size的并查集：
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
int find(int x) {if (p[x] != x) {p[x] = find(p[x]);
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i<= n; i ++ ) {p[i] = i;
    size[i] = 1;
}

// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
维护到祖宗节点距离的并查集：
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
int find(int x) {if (p[x] != x) {int u = find(p[x]);
        d[x] += d[p[x]];
        p[x] = u;
    }
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i<= n; i ++ ) {p[i] = i;
    d[i] = 0;
}

// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
[例题]

AcWing 1250. 格子游戏
AcWing 1252. 搭配购买
AcWing 237. 程序自动分析

专注于为中小企业提供成都网站制作、成都网站建设服务,电脑端+手机端+微信端的三站合一,更高效的管理,为中小企业马关免费做网站提供优质的服务。我们立足成都，凝聚了一批互联网行业人才，有力地推动了上1000+企业的稳健成长，帮助中小企业通过网站建设实现规模扩充和转变。10. 堆
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
void heap_swap(int a, int b) {swap(ph[hp[a]],ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u) {int t = u;
    if (u * 2<= size && h[u * 2]< h[t]) {t = u * 2;
    }
    if (u * 2 + 1<= size && h[u * 2 + 1]< h[t]) {t = u * 2 + 1;
    }
    if (u != t) {heap_swap(u, t);
        down(t);
    }
}

void up(int u) {while (u / 2 && h[u]< h[u / 2]) {heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) {down(i);
}
二叉堆 例题

acwing 148 合并果子

11. 哈希表 拉链法(N = 100003)
int h[N], e[N], ne[N], idx;//槽,链表值，下一个位置，当前用到哪个位置 

void insert(int x) {int k = (x % N + N) % 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;		
}
开放寻址法(N=200003)
int h[N]; // 槽

int find(int x) {// 如果x在哈希表存在，返回x的位置，如果不存在，返回x应该存贮的位置 
	int k = (x % N + N) % N;
	while(h[k] != null && h[k] != x){// 当前位置有人并且不是x 
		k ++;
		if(k == N) {	k = 0;//循环看第一个位置 
		}
	} 
	return k;	
}
12. STL
  • vector变长数组，利用倍增思想
初始化
vectora;
返回元素个数
a.size()
返回a是否为空 空true， 非空false
a.empty()
清空vector
a.clear()
返回第一个数
a.front()
返回最后一个数
a.back()
在最后插入一个数
a.push_back()
删除最后一个数
a.pop_back()
迭代器

第0个数

a.begin()

最后一个数的下一个数

a.end()
  • pair存储二元组
定义
pairt;
元素
p.first
p.second
三种元素
pair>p
  • string字符串
定义
string s
字符串长度
a.size()
字符串是否为空
a.empty()
清空字符串
a.clear()
从起始位置开始的字符串
a.substr(字串的起始位置，字串的长度)
  • queuq队列
定义
queueq
队列长度
q.size()
队列是否为空
q.empty()
向队尾插入元素
q.push()
返回队尾元素
q.back()
弹出对头元素
q.pop()
清空队列(没有clear函数)
q = queue();
  • priority_queue优先队列，默认是大根堆
定义
priority_queueq
插入一个元素
q.push()
返回堆顶元素
q.top()
弹出堆顶元素
q.pop()
变成小根堆

方法一

priority_queueheap;
heap(-x);

方法二

priority_queue, greater>heap;
  • stack栈
定义
stackq;
栈长度
q.size()
栈是否为空
q.empty()
向栈顶插入一个元素
q.push()
返回栈顶元素
q.top()
弹出栈顶元素
q.pop()
  • deque双端队列
定义
dequeq;
队列长度
q.size()
队列是否为空
q.empty()
清空队列
q.clear()
返回队列的第一个元素
q.front()
返回队列的最后一个元素
q.back()
向队列最后插入一个元素
q.push_back()
弹出队列最后一个元素
q.pop_back()
向队首插入一个元素
q.push_front()
从队首弹出元素
q.pop_front()
迭代器

第0个数

q.begin()

最后一个数的下一个数

q.end()
其他STL
  • binary_search查找某个元素是否出现
函数模板：
binary_search(arr[],arr[]+size,x)
参数说明：
arr[]:数组首地址
size:数组元素个数
x：需要查找的值
函数功能：

在数组中以二分法检索的方式查找，若在数组中查找到indx元素则真，若查找不到则返回值是假

  • lower_bound查找第一个大于或等于某个元素的位置

返回查找元素的第一个可安插位置，也就是“元素值>=查找值”的第一个元素的位置

函数模板：
lower_bound(arr[],arr[]+size,x)
参数说明：
arr[] : 数组首地址
size : 数组元素的个数
x : 需要查找的值
函数功能：函数lower_bound()在first和last的前闭后开区间进行二分查找，返回大于或等于val的第一个元素的位置，如果所有元素都小于val，则返回last的位置，且last的位置是越界的！
  • upper_bound查找第一个大于某个元素的位置

返回查找元素的最后一个可安插位置，也就是“元素值>查找值”的第一个元素的位置

函数模板 :
upper_bound(arr[] , arr[]+size , x)
参数说明：
arr[] : 数组首地址
size : 数组元素个数
x : 需要查找的值
函数功能 : 函数upper_bound()返回的在前闭后开区间查找的关键字的上界，返回大于val的第一个元素位置 13.树状数组
int a[N];
int tr[N]; // 树状数组
int Greater[N], lower[N]; // Greater[i]表示比i大的数,lower[i]表示比i大的数

int lowbit(int x) {return x & -x;
}

void add(int x, int c) {// 树状数组的增加函数 为第x个数加上c,并且给它的父亲节点也加上，这里为了表示是否出现，所以加的是1
    for (int i = x; i<= n; i += lowbit(i)) {tr[i] += c;
    }
}

// 求前1~x个数的和,tr[x]存储的是区间[x − lowbit(x) + 1,x]出现的数的次数，题目说y1到yn是1到n的排列，所以这个sum是用来求1~x中出现的数的个数
int sum (int x) {// 树状数组的查询函数
    int res = 0;
    for (int i = x; i; i -= lowbit(i)) {res += tr[i];
    }

    return res;
}
[例题]

AcWing 241. 楼兰图腾
AcWing 242. 一个简单的整数问题
AcWing 243. 一个简单的整数问题2
AcWing 244. 谜一样的牛

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


当前标题：AcWing数据结构-创新互联
链接地址：http://scjbc.cn/article/diposo.html

其他资讯

联系小谭

企业微信号
友情链接： 机柜租用   成都品牌网站建设   成都定制网页设计   成都网站建设   崇州湖霆科技   达州电信机房   遂宁海缘科技   成都钢筋机械设备   企业网站设计   四川雅安服务器托管   

123ABC 成都网站建设，成都定制网站建设——全心全意建网站公司