数据结构
链表
单链表
使用数组模拟的方式进行
单链表用的最多的两个技术就是可以用来写邻接表，邻接表可以用来存储图和树
双链表可以用来优化某些问题
如何使用数组进行模拟呢？
用两个数组来进行模拟，一个数组存储数值，一个数组存储结点
#include <iostream>
using namesapce std;
const int N = 100010;
// head 表示头节点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点的next指针
// 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 = idx; idx++;
}
// 将x插入到下标是k的节点的后面
void add(int x,int k)
{
e[idx] = x;
ne[idx] = ne[k];
ne[k] = idx;
idx++;
}
// 将下标是k的点的后面的节点删除
void remove(int k)
{
ne[k] = ne[ne[k]];
}
双链表
结合画图会更好理解
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int e[N],l[N],r[N],idx=0;
void init()
{
l[1] = 0;
r[0] = 1;
idx = 2;
}
// 在第k个的右边插入节点
void add(int k, int x)
{
e[idx] = x; // new node
l[idx] = k; // node.left = k
r[idx] = r[k]; // node.right = k.right
r[k] = idx; // k.right = node
l[r[idx]] = idx; // node.right.left = node
idx ++;
}
void remove(int k)
{
r[l[k]] = r[k]; // k.left.right = k.right
l[r[k]] = l[k]; // k.right.left = k.left
}
int main()
{
int n;
cin >> n;
int k,x;
init();
while(n--)
{
string op;
cin >> op;
if(op == "L")
{
cin >> x;
add(0,x);
}else if(op == "R"){
cin >> x;
add(l[1], x);
}else if(op == "D"){
cin >> k;
remove(k+1);
}else if(op == "IL"){
cin >> k >> x;
add(l[k+1],x);
}else{
cin >> k >> x;
add(k + 1,x);
}
}
for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';
}
栈
先插入的元素会先弹出来
基础栈
#include <iostream>
using namespace std;
const int N = 100010;
int stk[N],tt;
// 插入
stk[++t] = x;
// 弹出
tt --;
// 判断栈是否为空
if(tt > 0) not empty;
// 栈顶
stk[tt];
单调栈
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int stck[N],tt;
int main()
{
cin >> n;
while(n --)
{
int x;
cin >> x;
// 维护一个单调递增的队列
while(tt and stck[tt] >= x) tt--;
if(tt) cout << stck[tt] << ' ';
else cout << -1 << ' ';
stck[++tt] = x;
}
return 0;
}
队列
先进先出
基础队列
#include <iostream>
using namespace std;
const int N;
int q[N],hh,tt = -1;
// 插入
q[++t] = x;
// 弹出
hh++;
// 判空
if(hh<=tt) not empty;
else empty;
// 取出对头元素
q[hh];
// 取出队尾元素
q[tt];
单调队列
#include <iostream>
using namespace std;
const int N = 1000010;
int n,k;
int a[N],q[N];
int main()
{
cin >> n >> k;
for(int i =0;i<n;i++) cin >> a[i];
int hh = 0, tt = -1;
// 维持一个单调递增的队列
for(int i =0;i<n;i++)
{
// 去除超过头部的元素
if(hh <= tt and q[hh] < i - k + 1) hh++;
// 如果新加入的元素小于队尾元素，那就删除掉队尾元素
while(hh <= tt and a[q[tt]] >= a[i]) tt--;
q[++tt] = i;
if (i >= k - 1) cout << a[q[hh]] << ' ';
}
// 维持一个单调递减的队列
cout << endl;
hh = 0, tt = -1;
for(int i =0;i<n;i++)
{
// 去除超过头部的元素
if(hh <= tt and q[hh] < i - k + 1) hh++;
while(hh <= tt and a[q[tt]] <= a[i]) tt--;
q[++tt] = i;
if (i >= k - 1) cout << a[q[hh]] << ' ';
}
}
KMP
KMP: 字符串匹配问题
思路：
- 先考虑暴力怎么做，然后再考虑如何如何去优化算法
- 使用一个next数组来进行储存
tip
next数组用来存模式串中每个前缀最长的能匹配前缀子串的结尾字符的下标。 next[i] = j 表示下标以i-j为起点，i为终点的后缀和下标以0为起点，j为终点的前缀相等，且此字符串的长度最长。用符号表示为p[0~j] == p[i-j~i]。
#include <iostream>
using namespace std;
const int N = 100010, M = 1000010;
int n,m;
char p[N],s[M];
int ne[N];
int main()
{
cin >> n >> p +1 >> m >> s + 1;
// 构造next数组
for(int i =2,j = 0;i<=n;i++)
{
while(j and p[i] != p[j+1]) j = ne[j];
if(p[i] == p[j+1]) j++;
ne[i] = j;
}
// kmp 匹配过程
for(int i = 1,j=0; i<=m;i++)
{
while(j and s[i] != p[j+1]) j = ne[j];
if(s[i] == p[j+1]) j++;
if(j == n)
{
cout << i - n << ' ';
j = ne[j];
}
}
}
树
树的中序遍历
迭代写法
// 中序遍历的迭代写法
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while(root or stk.size())
{
// 先将左节点全部压入节点当中
while(root)
{
stk.push(root);
root = root->left;
}
if(stk.size())
{
root = stk.top();
stk.pop();
res.push_back(root->val);
// 压入当前节点的右节点
root = root->right;
}
}
return res;
}
};
递归写法
class Solution {
public:
vector<int> res;
vector<int> inorderTraversal(TreeNode* root) {
dfs(root);
return res;
}
void dfs(TreeNode* root)
{
if(!root) return;
dfs(root->left);
res.push_back(root->val);
dfs(root->right);
return;
}
};
Trie树
用于高效地存储和查找字符串集合的数据结构，一般存储的字符串都不是很长
问题：是如何存储字符串的呢？
使用树结构来存储字符串，有字符串作为结尾的节点需要打上标记
#include <iostream>
using namespace std;
const int N = 100010;
char str[N];
int son[N][26]; // 存入所有的儿子节点
int cnt[N]; // 下标是0的点，即是根节点，又是空节点
int idx; // 当前用到了哪一个下标
// 插入字符串
void insert(char str[])
{
int p = 0;
for(int i =0;str[i];i++)
{
int u = str[i] - 'a';
// If you don't find a node in the tree, you need to create one new node.
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];
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
char op[2];
scanf("%s%s",op,str);
if(op == "I") insert(str);
else print("%d\n",quert(str));
}
return 0;
}
并查集
快速的处理如下问题：
- 将两个集合合并
- 询问两个元素是否在一个集合当中
基本原理： 用树的形式来维护集合，每个集合编号是树的根节点，每个节点存储他的父节点
问题1： 如何判断是否是树根：if(p[x] == x)
问题2： 如何求x的集合编号：while(p[x]!= x) x =p[x];
问题3： 如何合并两个集合：px是x的集合编号，py是y的集合编号，p[x]= y
优化：一旦往上走的时候找到了根节点，就把所有路径上的节点都指向根节点（路径压缩）
#include <iostream>
using namespace std;
const int N = 100010;
int p[N]; // father数组，存储每个元素的父节点是谁
int size[N]; // 表示每一个集合的大小，每一个集合里面点的数量
int find(int x) // 返回x的祖宗节点
{
if(p[x] != x) p[x] = find(p[x]); // 在便利的过程中把每个节点都指向根节点
return p[x];
}
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1;i <= n; i++ )
{
p[i] = i;
size[i] = 1;
}
while(m--)
{
char op[5];
int a,b;
scanf("%s",op);
if(op[0] == 'C')
{
cin >> a >> b;
// 特判一个调节
if(find(a) == find(b)) continue;
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
}
else if(op[1] == '1'){
scanf("%d%d",&a,&b);
if(find(a) == find(b)) cout << "YES" << endl;
else cout << "NO" << endl;
}else
{
scanf("%d",&a);
printf("%d\n",size[find(a)]);
}
}
return 0;
}
堆
堆的基本操作
- 插入一个数（STL: 优先队列）
heap[++size] = x; up(size);- 求集合当中的最小值（STL）
heap[1];- 删除最小值（STL）
heap[1] = heap[size]; size--; down(1);- 删除任意一个元素
heap[k] = heap[size]; size--; down(k);up(k);- 修改任意个元素
heap[k] = x; down(k); up(k);
堆的性质
- 堆是一个完全二叉树，上层节点都是满的，最后一层的节点从左向右排布
- 如何去存储？ 用一维数组去存储一个堆，x的左儿子是2x，x的右儿子是2x+1 ( 下标从1开始 )
堆排序算法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N];
int size,n,m;
void down(int u)
{
int t = u; // 表示三个点里面的最小值的编号
if(u * 2 <= size and h[u * 2] < h[t]) t = u*2;
if(u * 2 + 1 <= size and h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if(u != t)
{
swap(h[u],h[t]);
down(t);
}
}
void up(int u)
{
while(u / 2 and h[u/2] > h[u])
{
swap(h[u/2],h[u]);
u /= 2;
}
}
int main()
{
scanf("%d",&n,&m);
for(int i =1;i<=n;i++) scanf("%d",&h[i]);
size = n;
for(int i = n/2;i;i--) down(i); // O(n)时间复杂度的建堆
while(m--)
{
printf("%d ",h[1]);
h[1] = h[size--];
down(1);
}
return 0;
}
模拟堆算法
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N],size,hp[N],ph[N];
int n,m;
void headSwap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a],hp[b]);
swap(h[a],h[b]);
}
void up(int u)
{
while(u / 2 and h[u/2] > h[u])
{
heap_swap(u/2,u);
u /= 2;
}
}
void down(int u)
{
int t = u;
if(u * 2 <= size and h[u * 2] < h[t]) t = u * 2;
if(u * 2 +1 <= size and h[u*2 + 1] < h[t]) t = u * 2 + 1;
if(u != t)
{
headSwap(u,t);
down(t);
}
}
int main()
{
scanf("%d",&n,&m);
while(n--)
{
string op;
scanf("%s", &op);
if(op == "I")
{
scanf("%d",&x);
ph[++m] = ++size;
h[size] = x;
up(size);
}else if(op == "PM") cout << h[1] << endl;
else if(op == "DM")
{
heap_swap(1,size);
size--;
down(1);
}else if(op == "D")
{
scanf("%d",&k);
k = ph[k];
heap_swap(k,size);
size --;
down(k); up(k);
}else
{
cin >> k >> x;
k = ph[k];
h[k] = x;
down[k];up[k];
}
}
}
哈希表
将大范围的数映射到一个小范围的数当中
问题1：哈希函数要怎么写：直接取模即可, 这个数
一般取成一个质数问题2：冲突问题
- 拉链法： 在冲突的地方拿出一条链来存储冲突的数
- 开放寻址法：从第k个位置开始找，如果第k个位置有冲突就去第k+1个位置
// 拉链法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10003;
int h[N],e[N],ne[N],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;
for(int i=h[k];i != -1; i = ne[i])
{
if(e[i] == x) return true;
}
}
int main()
{
int n;
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)) puts("Yes");
else puts("No");
}
}
}
// 开放寻址法
#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003, null = 0x3f3f3f3f;
int h[N],idx;
int find(int x)
{
int k = (x%N + N)%N;
while(h[k] != null and h[k] != x)
{
k++;
if(k == N) k = 0;
}
return k;
}
int main()
{
int n;
scanf("%d",&n);
memet(h,0x3f,sizeof h);
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] != null) puts("Yes");
else puts("No");
}
}
}
字符串哈希值
将一个长度为p的字符串看做一个p进制的数，然后将这个数字转化为10进制的值后进行哈希