基础知识

结构体的表示方法

无以下特殊需求，一律用数组模拟结构体，用数组下标i模拟指针。

// 不使用 malloc 直接开足够大的空间
const int N = 1e5 + 10;

int e[N], ne[N], h, idx;
// e[N] : 存入值 ne[N] : 存入指针下标 idx: 定位数组的指针

但是数组也不是万能的，

1. 遇到需要使用 sort() 排序时，需要用结构体+重载：

const int N = 1e5 + 10;

struct Range {
    int l, mid, r;
    // 左边 const 指不能修改W的成员变量
    // 右边 const 指不能修改this的成员变量
    // 使用引用，避免对象拷贝，减小内存消耗
    bool operator< (const Range &W)const {
		    // 返回值会用来判断当前this对象是否小于W对象
		    return r < W.r;
		}
}range[N];

// 按照r的大小进行排序
sort(range, range + n)

或者使用 pair<int, int> 也可以，sort会优先按p.first 进行排序，若 p.first 相同，会对 p.second 进行排序。

1. 树的数据结构一般在Leetcode里会直接给出来，不需要我们自己设计数据结构。

链表

// 静态单链表
int val[N] ,        //链表值
nxt[N],             //下一个节点的下标
head,               //头节点指向的结点下标
idx;                //创建下一个结点时所在的数组下标

void init(){
    head = -1;
    idx = 0;
}

// 将x插到链表头部
void add_to_head(int x){
    val[idx] = x;
    nxt[idx] = head;
    head = idx;
    idx++ ;
}
// 将x插到链表下标为k的后面
void add_after_k(int k,int x){
    val[idx] = x;
    nxt[idx] = nxt[k];
    nxt[k] = idx;
    idx++;
}

// 删除下标为k的节点的后一个节点
void del_after_k(int k){
    nxt[k] = nxt[nxt[k]];
}
// 删除头结点
void remove_head(){
    head = nxt[head];
}

// 静态双链表 注意没有头指针h
int val[N],pre[N],nxt[N],idx;
// 初始化
void init(){
    // 0代表左端点 1代表右端点
    nxt[0] = 1;
    pre[1] = 0;
    idx = 2;
}
// 在下标k的节点右边插入一个节点
void add_after_k(int k,int x){
    val[idx] = x;
    nxt[idx] = nxt[k];
    pre[idx] = k;
    pre[nxt[k]] = idx;
    nxt[k] = idx;
    idx++;
}

// 在下标k的节点左边插入一个节点
void add_before_k(int k,int x){
    add_after_k(pre[k],x);
}
// 删除第k个节点
void remove(int k){
    pre[nxt[k]] = pre[k];
    nxt[pre[k]] = nxt[k];
}

栈与队列

// 栈
int stack[N];
int top;

void push(int x){
    stack[++top ] =x;
}

void pop(){
    top --;
}

int getTop(){
    return stack[top];
}

bool empty(){
    return top <= 0;
}

// 队列
int queue[N];
int head = 0,tail = -1;

void push(int x){
    queue[++tail] = x;
}

void pop(){
    head ++;
}

bool empty(){
    return head > tail;
}

int getFront(){
    return queue[head];
}

KMP 字符串匹配