一些简单的算法板子(以后可能分开来)

2021-08-22

二分，三分,离散化，trie树，对顶堆

二分查找

特征

具有单调性的数组
求最大/最小值
答案离散(具有有限种可能)

做法

区间排好序
确定答案区间
在保证答案在区间内的前提下缩小区间
当区间缩小到仅包含一个解时，该解就是答案

两种写法

左闭右开区间

不直接找到目标值的写法，跳出循环后的num[l-1]要么是目标值，要么是目标值目标值左面的值；num[l]是目标值右面的值

int l=0,r=n+1;
while (l<r){
    int mid = l + ((r - l) >> 1);//取中间值
    if(num[mid]<target){
        l = mid + 1;
    }
    else{
        r = mid;
    }
}
cout<<num[l-1];

直接找到目标值(适合写在函数里)

int l=0,r=n+1;//右开，所以指向区间最右面的下一位
while (l<r){
    int mid = l + ((r - l) >> 1);//取中间值
    if(num[mid]<target){
        l = mid + 1;
    }
    else if(num[mid]>target){
        r = mid;
    }
    else{
        return num[mid];
    }
    return -1;// 没有找到
}

左闭右闭区间

和上面差不多(包括跳出循环的值)，无非差别在于等于号以及r的区别

int l=0,r=n;//右闭，所以指向区间最右面
while (l<=r){
    int mid = l + ((r - l) >> 1);//取中间值
    if(num[mid]<target){
        l = mid + 1;
    }
    else if(num[mid]>target){
        r = mid-1;
    }
    else{
        return num[mid];
    }
    return -1;// 没有找到
}

三分

特征

类似于二分查找，三分搜索法也是比较常用的基于分治思想的高效查找方法。但是和二分不同，二分只适用于单调函数，三分用于单峰函数(求极值)

代码

long double f(double x){// 算出某个点的函数值
    //something
}

const double eps=1e-10;// 精度，建议开高一点，免得被卡
long double sanfen(double l, double r){
    long double mid,midr,ans, midl;
    while (fabs(r-l)>eps) {
        mid = (r - l) / 3.0;
        midl = l + mid;
        midr= r - mid;
        //>:求极小值  <:求极大值
        if(f(midl) > f(midr)) l=midl; else r=midr;   
    } 
    ans=f(l);// l为三分出的极值点，f(l)为此处的函数值
    return ans;
}

离散化

使用场景

在数据规模较大（大于数组能开的范围），只需要数据的相对关系，而不需要数据的具体值时，我们可以使用离散化

代码

STL版

for(int i=1;i<=n;i++)
 scanf("%d",p+i),b[i]=p[i];// 建立两个相同的数组
sort(b+1,b+n+1); 
int m = unique(b + 1, b + n + 1) - b - 1;// 去重，指向最后一个相同的数，所以要-1
for(int i=1;i<=n;i++)
 p[i]=lower_bound(b+1,b+m+1,p[i])-b;// 在第二个数组中找出当前值，获取该值的下标（相对位置）

非STL版

int a[MAX];// 源数据数组
int A[MAX];// 离散化数组
int n;// 数组长度
int cmp(int i, int j) {
    return a[i] < a[j];// 点睛之笔，用源数据来进行离散数组的排序，这样离散数组就会排出来源数据的相对大小

}

for (int i = 1; i <= n; i++) {
    cin >> a[i];
    A[i] = i;// 初始化相对位置

    // 例：
    // a: 3 2 7 5
    // A: 1 2 3 4
}
sort(A + 1, A + 1 + n, cmp);
// A: 2 1 4 3

Trie 树（字典前缀树）

例题传送门是他错误的点名开始了

介绍

Trie树是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

性质

根节点不包含字符，除根节点外每一个节点都只包含一个字符
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符都不相同

功能模块

存储树

struct Trie {
    int son[50] = {0}; // son[i]记录的是当前节点的子节点
    int sum = 0;// num 是当前这个单词在查询中出现的次数
} a[MAX];
int t = 0;// 节点编号

建树

void build(string s) {
    int p = 0;// 当前访问的节点
    for (int i = 0; i < s.size(); i++) {
        if (a[p].son[s[i] - 'a'] == 0) {// 判断当前字符是否存在Trie树中
            a[p].son[s[i] - 'a'] = ++t;// 不存在则添加新节点
        }
        p = a[p].son[s[i] - 'a'];// 插入下一个字符
    }
    // a[p].sum++;// 标记当前字符串有一个
}

查询

int query(string s) {
    int p = 0;// 当前访问的节点
    for (int i = 0; i < s.size(); i++) {
        if (a[p].son[s[i] - 'a'] == 0) { // 如果该字符的节点不存在
            return 0;// 直接返回0代表查询不到
        }
        p = a[p].son[s[i] - 'a'];// 查询下一个字母
    }
    // a[p].sum++; // 该单词的查询次数+1（本题要求）
    return a[p].sum;
}

对顶堆

介绍

可用于动态维护第k大的值（例如中位数）,每次操作为O（logn）

例题P1168 中位数
我们需要分别维护两个堆，让小根堆的堆顶作为分界线，如果大于它就加入小根堆，否则就加入大根堆,如果两个堆的个数相差超过1，就将多的那个堆的堆顶弹出来放到另一个堆的堆顶。奇数个数的中位数显然是堆中数量最多的堆的堆顶。偶数个数的中位数则是两个堆堆顶取平均值。

加入元素的操作

priority_queue<int> q_big;// 大顶堆
priority_queue<int, vector<int>, greater<int> > q_less;// 小顶堆

void insert(int x) {
    if (q_less.empty() || x > q_less.top()) {
        q_less.push(x);
    } else {
        q_big.push(x);
    }
    while (q_less.size() > q_big.size() + 1) {
        q_big.push(q_less.top());
        q_less.pop();
    }
    while (q_big.size() > q_less.size() + 1) {
        q_less.push(q_big.top());
        q_big.pop();
    }
}