Acwing Arithmetic Learning:数据结构(1)
程序员文章站
2022-03-25 15:50:48
数据结构(1)acwing (用数组模拟 >称为静态链表) 1.单链表和邻接表(存储树和图) 规范: -1表示空集,idx:指针(当前用到了哪个点) 第1个插入数的下标为0,因此第k个插入数的点下标为(k-1) int e[N]:代表数组内部的值,ne[N]:代表指针,指向下一个节点 插入节点到链表 ......
数据结构(1)acwing
目录
(用数组模拟--->称为静态链表)
1.单链表和邻接表(存储树和图)
规范:
- -1表示空集,idx:指针(当前用到了哪个点)
- 第1个插入数的下标为0,因此第k个插入数的点下标为(k-1)
int e[n]:代表数组内部的值,ne[n]:代表指针,指向下一个节点
插入节点到链表中步骤:
(1)将x插到head结点
(2)将x插到k节点后面
(3)删除下标是k的后面的点
void remove(int k){ ne[k] = ne[ne[k]]; }
2.双链表:优化某些问题
-
规范:
- int e[n]、l[n]、r[n],idx
- 0:左端点,1:右端点
-
1.插入结点步骤:
// 在下标为k的点的右边,插入x void add(int k,int x){ e[idx] = x; r[idx] = r[k]; l[idx] = k; l[r[k]] = idx; r[k] = idx; }
ps: 想要在下标为k的左边,插入x----》最easy方式:add(l[k],x)
-
2.删除节点
// 删除第k个点 void delete(int k){ r[l[k]] = r[k]; l[r[k]] = l[k]; }
3.栈
-
单调栈:(时间复杂度:o(n)----->出栈及入栈分别为n)
int n; int stk[n],tt; int main(){ cin >> n; for(int i = 0; i < n; i++){ int x; cin >> x; while(tt && stk[tt] >=x) t--; if(tt) cout << stk[tt] << ' '; else cout << -1 << ' '; stk[ ++ tt] = x; } return 0; }
4.队列
-
单调队列:
- 规范:hh = 0,tt = -1
-
实现代码(滑动窗口)------{没看懂}
5.kmp算法
- 思路:
- 暴力算法怎么做?
- 如何去优化?