AcWing算法基础课笔记

数据结构

单链表

• 邻接表（多个单链表）（head数组）
  • 存储图
  • 存储树

实现一个单链表，链表初始为空，支持三种操作：
(1)向链表头插入一个数；
(2)删除第k个插入的数后面的数；
(3)在第k个插入的数后插入一个数；
现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。
注意：题目中第k个插入的数并不是指当前链表的第k个数.例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为:第1个插入的数，第2个插入的数，…。第n个插入的数。
**输入格式**
第一行包含整数M，表示操作次数。
接下来M行，每行包含一个操作命令，操作命令可能为以下几种：
(1)“H x”，表示向链表头插入一个数x。
(2)“D k”，表示删除第k个输入的数后面的数(当k为0时，表示删除头结点)。
(3)“I k x”，表示在第k个输入的数后面插入一个数x(此操作中k均大于0)。

#include<iostream>
using namespace std;

const int N = 100010;
int head,e[N],ne[N],idx;

void init(){
    head = -1;
    idx = 0;
}
//头结点添加val
void add_to_head(int val){
    e[idx] = val, ne[idx] = head, head = idx++;
}
//在节点k的位置添加val
void add(int k,int val){
    ne[idx] = val, ne[idx] = ne[k], ne[k] = 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)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] << ' ';
    
    return 0;
}

双链表

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(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];
}

栈

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{}

队列

• 普通队列

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{}

• 循环队列

// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{}

单调栈

• 找出每个数左边离他最近且比他小的数

#include <iostream>
using namespace std;
const int N= 100010;
int n;
int stk[N], tt;
int main(){
    scanf("%d", &n);
    for(int i=0; i<n ; i++){
        // 加速
        cin.tie(0);
        ios::sync_with_stdio(false);
        int x;
        scanf("%d ",&x);
        // 栈非空，且栈顶值大于当前值x，则栈顶出栈
        while(tt && stk[tt]>=x)tt--;
        // 找到栈中第一个符合题意的数，并输出
        if(tt)printf("%d ",stk[tt]);
        else print("-1 ");
        // 当前数x需入栈
        stk[ ++ tt]=x;
    }
    return 0;
}

单调队列

• 滑动窗口，第一行输出窗口中的最小值，第二行输出窗口中的最大值
• 输入两行，第一行n，k，代表共n个数，窗口大小k；第二行有n个数

#include <iostream>
using namespace std;

const int N = 100010;
int n,k;           // 共n个数，窗口大小为k
int a[N],q[N];     // 数字存储在数组a，窗口于数组q记录k个下标

int main(){
    scanf("%d %d",&n,&k);
    for(int i = 0; i<n ;i++) scanf("%d",&a[i]);
    int 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;
        // 队列q队满，才需要
        if(i>=k-1)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>=k-1)printf("%d ",a[q[hh]]);
    }
    puts("");
    return 0;
}

KMP

给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
模板串P在模式串S中多次作为子串出现。
求出模板串P在模式串S中所有出现的位置的起始下标。
**输入格式**
第一行输入整数N，表示字符串P的长度。
第二行输入字符串P。
第三行输入整数M，表示字符串S的长度。
第四行输入字符串M。
**输出格式**
共一行，输出所有出现位置的起始下标(下标从0开始计数)，整数之间用空格隔开。

// 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];
        // 匹配成功后的逻辑
    }
}

Trie树

• 高效存储字符串、查询字符串

维护一个字符串集合，支持两种操作:
1.“I x”向集合中插入一个字符串x;
2.“Q x”询问一个字符串在集合中出现了多少次。
共有N个操作，输入的字符串总长度不超过 10^5，字符串仅包含小写英文字母。
**输入格式**
第一行包含整数N，表示操作数。
接下来N行，每行包含一个操作指令，指令为"1x“或"Q x“中的一种。
**输出格式**
对于每个询问指令”Q x”，都要输出一个整数作为结果，表示x在集合中出现的次数。
每个结果占一行。

#include<iostream>
using namespace std;

const int N = 10010;
char str[N];
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
int son[N][26],cnt[N],idx;

// 向集合中插入一个字符串
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没有儿子u,添加
        p = son[p][u];                    // p下一位肯定有u，迭代
    }
    cnt[p]++;                             // 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;
}

并查集

• 将两个集合合并
• 询问两个元素是否在同一集合中
• 集合用树来表示，树根的编号就是集合的编号

一共有n个数，编号是1~n，最开始每个数各自在一个集合中。
现在要进行m个操作，操作共有两种:
1.“M a b”，将编号为a和b的两个数所在的集合合并，如果两个数已经在同一个集合，则忽略这个操作;
2.“Q a b”，询问编号为a和b的两个数是否在同一个集合中;
**输入格式**
第一行输入整数n和m。
接下来m行，每行包含一个操作指令，指令为“M a b"或“Q a b"中的一种。
**输出格式**
对于每个询问指令”Q a b”，都要输出一个结果，如果a和b在同一集合内，则输出“Yes”，否则输出“No”。
每个结果占一行。

• 朴素并查集

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

• 维护size的并查集

// p[]存储每个点的祖宗节点
// size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量
int p[N],size[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;
    size[i] = 1;
}

// 合并a和b所在的两个集合：更新b集合的size，将a根节点的父节点设置为b根节点
size[find(b)] += size[find(a)];
p[find(a)] = find(b);

• 维护到祖宗节点距离的并查集

//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离
int p[N], d[N];

// 返回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)的偏移量

堆

1.插入一个数              heap[ ++size]= x; up(size);
2.求集合当中的最小值       heap[1];
3.删除最小值              heap[1]=heap[size]; size--; down(1);
4.刪除任意一个元素         heap[k]=heap[size]; size--; down(k)||up(k);
5.修改任意一个元素         heap[k]=x; down(k)||up(k);

搜索与图论

DFS深搜

• 排列数字

给定一个整数n，将数字1~n排成一排，按照字典序将所有排列方法输出。

#include<iostream>
using namespace std;

const int N = 10;

int n;
int path[N];
bool st[N];

void dfs(int u){
    if(u == n){
        for(int i = 0; i<n; i++) printf("%d ",path[i]);
        return;
    }
    
    for(int i = 1; i<=n; i++)
        if(!st[i]){
            path[u] = i;
            st[i] = true;
            dfs(u + 1);
            st[i] = false;
        }
}

int main(){
    cin >> n;
    dfs(0);
    return 0;
}

• n皇后问题

#include<iostream>
using namespace std;

const int N = 20;
int n;
char g[N][N];
bool col[N],dg[N],udg[N];

void dfs(u){
    if(u == n){
        for(int i = 0; i<n ;i++) puts(g[i]);
        puts("");
        return;
    }
    
    for(int i = 0;i<n;i++)
        if(!col[i] && !dg[u + i] && !udg[n - u + i]){
            g[u][i] = 'Q';
            col[i] = dg[u + i] = udg[n - u + i] = true;
            dfs(u + 1);
            col[i] = dg[u + i] = udg[n - u + i] = false;
            g[u][i] = '.';
        }
}

int main(){
    cin >> n;
    for(int i = 0;i < n ;i++)
        for(int j = 0; j<n ;j++)
            g[i][j] == '.';
    
    dfs(0);
    
    return 0;
}

#include<iostream>
using namespace std;

const int N = 20;
int n;
char g[N][N];
bool row[N],col[N],dg[N],udg[N];

void dfs(int x,int y,int queen){
    if(y == n) y = 0,x ++;
    
    if(x == n)
    {
        if(queen == n)
        {
            for(int i = 0;i<n;i++) puts(g[i]);
            puts("");
        }
        return;
    }
    
    //不放皇后
    dfs(x, y+1, queen);
    
    //放皇后
    if(!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n]){
        g[x][y] = 'Q';
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = true;
        dfs(x,y+1,queen+1);
        row[x] = col[y] = dg[x+y] = udg[x-y+n] = false;
        g[x][y] = '.';
    }
   
}

int main(){
    cin >> n;
    dfs(0,0,0);
    return 0;
}