Data Structure And Algorithms

2022-07-19 阅读量

单链表与双链表

静态链表实现

单链表

核心实现

const int N = 100010;
int ne[N], e[N], head, idx;
// 初始化
void init(){
    head=-1; // -1表示空节点
}
// 头插法
void addHead(int x){
    e[idx]=x;
    ne[idx]=head;
    head=idx;  // 注意！
    idx++;
}
// 插入k后
void add(int x, int k){
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx;
    idx++;
}
// 删除k后节点
void del(int k){
    ne[k]=ne[ne[k]];
}

练习题型

&#127825 ;826.单链表

// 1.删除第k个插入节点，则其下标idx=k-1
// 2.删除头节点特殊处理：head=ne[head];

// 补充：我真的会谢，输入输出有问题）

双链表

练习题型

827.双链表

没有领悟到双链表的精髓呢！

// 1.功能上四个函数，但是完全可以压缩为两个函数的功能！
// ->add(),del()
// (体现双链表精华的地方，l[k]与r[k]左右获取)
// 2.不要分类讨论，就要统一处理！

// 重点！-- 初始化使头尾节点都各指向一空节点
void init(){
    head=0, tail=1;
    r[head]=tail, l[tail]=head;
    idx+=2;
}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数

练习题型

828.模拟栈

⭐830.单调栈：
栈内容递增

while(m--){
    int x; scanf("%d",&x);
    while(top!=-1&&s[top]>=x) top--;
    if(top!=-1) printf("%d ", s[top]);
    else printf("-1 ");
    s[++top]=x;
}

单调队列

常见模型：找出滑动窗口中的最大/小值

练习模拟

829.模拟队列

nc，scanf到现在都不知道加&吗

void push(int x){
    q[tail++]=x;
}
void pop(){
    if(head+1>=tail) head=tail;
    else head++;
}

🍍154.滑动窗口
(1)hh=0,tt=-1 (2)q[i]存储下标 (3)单增

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] = a[i];

    if(i >= k-1) printf("%d ", a[q[hh]]);
}

KMP

Trie树

高效存储/查找字符串集合

核心实现

835.Trie字符串统计

int son[N][26], cnt[N], idx; //下标为0的点既空节点又根节点
// 插入
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;
    }
    return cnt[p];
}

练习题型

143.最大异或对
(1)移位运算 (2)i=30->0

void insert(int x){
    int p=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;  // 表示取出第i+1位数
        if(!son[p][u]) son[p][u]=++idx;
        p=son[p][u];
    }
}
int query(int x){
    int p=0, res=0;
    for(int i=30;i>=0;i--){
        int u=x>>i&1;
        if(son[p][!u]){
            res+=1<<i;  // 左移位:乘以2
            p=son[p][!u];
        }
        else p=son[p][u];
    }
    return res;
}

并查集

（原生并查集）快速查找两点是否同一个集合；快速合并两个集合

核心实现

找祖宗与路径压缩

// 查找x的祖先+路径压缩
int find(int x){
    if(x!=p[x])p[x]=find(p[x]);
    return p[x];
}

合并集合
祖宗的祖宗所以p[find(a)]

1	p[find(a)]=find(b); // 出现了一次问题

变形题型

837.连通块中点的数量

// 合并集合时加到根节点上,size[N]令根节点有含义即可
if(find(a)==find(b)) continue;
size[find(b)]+=size[find(a)];
p[find(a)]=find(b);

🌻240.食物链
(被我写成模拟题>_<

根节点

// 核心find函数
int p[N], d[N];
int find(int x){
    if(x != p[x]){
        int u = find(p[x]);
        d[x] += d[p[x]];  // 非常完美！(递归 有点回溯的意思
        p[x] = u;
    }
    return p[x];
}

int main(){
    int n, k, res=0;
    scanf("%d%d", &n, &k);
    
    for(int i=1; i<=n; i++) p[i] = i;
    while(k--){
        if(a>n||b>n) res++;
        int pa = find(a), pb = find(b);
        if(op == 1){
            if(pa == pb && (d[a] - d[b])%3!=0) res++;
            else if(pa!=pb){
                p[pa] = pb; d[pa] = d[b] - d[a];  
                // (d[a] + d[pa] - d[b]) % 3 == 0
            }
        }
        else if(op == 2){
            if(pa == pb &&(d[a] - d[b] - 1)%3!=0) res++;
            else if(pa!=pb){
                p[pa] = pb; d[pa] = d[b] - d[a] + 1;
                // (d[a] + d[pa] -1 - d[b]) % 3 == 0
            }
        }
    }
    printf("%d\n", res);
}

堆

插入数；求最小值与删除最小值；删除修改任意元素

核心实现

初始建堆

1
2
3

for(int i=n/2;i;i--){
    down(i);
}

复杂度说明(利用高中的数列求和知识)：

$S=1*\frac{n}{2^2}+2*\frac{n}{2^3}+3*\frac{n}{2^4}+...$
$S=n*(1*\frac{1}{2^2}+2*\frac{1}{2^3}+3*\frac{1}{2^4}+...)$
$2*S=n*(1*\frac{1}{2}+2*\frac{1}{2^2}+3*\frac{1}{2^3}+4*\frac{1}{2^4}+...)$
$\Rightarrow S=2*S-S=n*(\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}+\frac{1}{2^4}+...)<n*1=n$

down操作与up操作

// 区别：down需要和两个儿子比大小；up只需要与一个爹比大小
void down(int idx){
    int t=idx;
    if(2*t<=size&&h[2*t]<h[idx]) t=2*idx;
    if(2*t+1<=size&&h[2*t+1]<h[idx]) t=2*idx+1;
    if(t!=idx){
        swap(h[t], h[idx]);
        down(t);
    }
}

void up(int idx){
    while(idx/2 && h[idx/2]>h[idx]){
        swap(h[idx], h[idx/2]);
        idx/=2;
    }
}

堆排序：不断拿出头节点

while(m--){
    printf("%d ",h[1]);  //堆中头节点不使用0
    head[1]=head[size--]; //通过数组最后一个元素删除头节点
    down(1); //维持有序
}

进阶实现

维护数插入的次序；用途：Dijkstra算法

// 多维护两个数组，用于记录位置
// 用途：删除或修改第k个插入的元素
int hp[N], ph[N];
// 将swap函数替换为heap_swap函数
void head_swap(int a, int b){
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

练习题型

838.堆排序

839.模拟堆

哈希表

哈希表：

1.存储结构：开放寻址法，拉链法
2.字符串哈希方式

注：取模的数应为质数

存储结构

拉链法 – 认为平均上时间复杂度为O(1)

// O(n^2)求解素数的方法
void insert(int x){
    int k = (x % N + N) % N;  //保证余数是正数；N为质数
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx;
    idx ++;
}
bool query(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;
}
//1. sizeof 在计算变量所占空间大小时括号可以省略；计算类型(模子)大小时不能省略
//2. memset 按字节赋值，通常赋0或-1
memset(h, -1, sizeof h);

开放寻址法
一般，INT_MAX=0x3f3f3f3f

const int N = 200003, null = 0x3f3f3f3f; // N: 2-3倍
// 返回的是应当insert的位置或者x的位置
int find(int x){
    int k = (x % N + N) % N;
    while(h[k]!=null && h[k]!=x){
        k++;
        if(k==N) k=0;
    }
    return k;
}

memset(h, 0x3f, sizeof h); // int 4字节

字符串前缀哈希法

p = 131或13331，Q = 2^64 (unsigned long long)

用于快速判断两个字符串是否相等

前缀和公式

$h[i+1]=h[i] \times P+s[i]$
区间公式

$h[l,r]=h[r]-h[l-1]*P^{r-l+1}$

841.字符串哈希
不能映射为0。否则会冲突

typedef unsigned long long ull;
int P = 131;
ull h[N], p[N];  // 这里p[N]不能为int类型


ull get(int a, int b){
    return h[b] - h[a-1] * p[b-a+1];
}


int main(){
    int n, m;
    scanf("%d%d", &n, &m);
    
    char str[N];
    scanf("%s", str);
    
    p[0]=1;
    for(int i=1; i<=n; i++){
        p[i] = p[i-1] * P;
        h[i] = h[i-1] * P + str[i-1];
    }
    
    while(m--){
        int a, b, c, d;
        scanf("%d%d%d%d",&a, &b, &c, &d);
        
        if(get(a, b)==get(c, d)) puts("Yes");
        else puts("No");
    }   
}

STL

vector

倍增： 系统为某一程序分配空间时，所需时间与空间大小无关，与申请次数有关