当先锋百科网

首页 1 2 3 4 5 6 7

算法小本本

主要是c++刷题过程中的笔记，实时更新中！

目录

思想

提炼

碎碎念

Stl

stringstream

KMP

位操作

文件操作

线段树

manacher算法

图类题目

模板

数学

思想

  • leetcode 331.验证二叉树的前序序列化：利用栈，将已处理的部分替换掉,重复处理 4## -> #；在循环中，结合continue处理输入信息；树中n_{0}为子树个数为0的结点数，即叶子结点数；树是有向无环图，入度==出度

提炼

  • 利用栈，将已处理的部分替换掉，“递归”处理栈中信息
  • for(int i = 2; i < n; i++) 每次处理索引 i-2的元素，并对 i 判断，这样天然的解决了下标间隔的要求。

碎碎念

  • 匹配类问题，惯性思维是先锁定第一个元素，向后扫描第二个元素，发现不匹配，再换下一个数锁定，这样再来确定第二个元素时会有重复操作；相反若利用好第一次(或前面的)扫描的结果来帮我们判断第二个元素，可以避免重复扫描。
  • 同一个表达式换一换字母可能会好理解些
  • INF作为无穷大一般设为10^9 (int的最大值约为2*10^9)
  • while（）r++; 留意r的值
  • 模拟类题，初始点设为负，可以使代码更简洁。如迷宫类题起点设在（0，-1）处
  • 考虑结果为0
  • 对于string s ="abc", 避免循环（for(i = 0; i < n; i++)）访问到-1下标的处理办法：1.在前面加一个空格s = " "+ s;2.循环从1开始for(i = 1; i <= n; i++)， s[i-1]只会访问到0
  •     for(int i = 0; i < n ; i++) sum += r[i]/2;//直接把1去掉求和

  •     for(int i = n; i >= 1; i--) s[i * 2 + 1] = s[i], s[i * 2 + 2] = '#';// 从后往前赋值可以节省一个数组

  •     printf("%d%c",i,--k?' ':'\0');//控制输出

Stl

  • string类型只能用cin、cout输入输出，用printf()时，需转换成str.c_str();
  • 对于连续内存容器而言，删除单个元素erase(it)操作流程：将其之后所有元素（copy）前移，改变end()，析构最后无用元素，返回it，其实iterator类似指针封装，it所指的位置没变，内容刚好是删除元素的后一个元素。
  • 对于c++而言迭代器iterator所指内容被动（如连续内存容器做erase操作）更改时（即使你知道他改变后的内容），该迭代器视为失效。
  • 即对如vector、deque或string 使用erase后，删除位置之前的迭代器有效，之后位置的迭代器由于元素前移，所指内容发生改变视为无效。
  • 用map来记录处理字串类问题有奇效 - > pat1003
  • map.insert(map<int ,int>::value_type(nums[i], i));//向map中插入一对键值,重复键值无法再插入
map[i] = 1;//直接覆盖

stringstream

  • 可以使用 strstream.str() ，将 stringstream 类型转换为 string 类型；
  • 可以将多个字符串放入 stringstream 中，实现字符串的拼接目的；

KMP

《20数据结构高分笔记》kmp笔记

模式串：ABCDEGABCF    ，     F处与文本串不匹配时，F之前的字符串中重合的前缀与后缀分别指ABC与ABC

文本串：ABCABCABCABCF
模式串：ABCABCABCF     ，     F处与文本串A不匹配时，说明之前的匹配作废，此时朴素算法是拿A与B重新比较，而KMP的策略是拿A与A比较，F之前的字符串中有ABCABC与ABCABC, ABC与ABC  这两对是重合的前缀与后缀，前者称为最先出现的重合。前者尝试拿A与文本不匹配处比较，后者尝试拿A与文本不匹配处比较。

模式串中，在第 i 处出现不匹配时，明智的做法是从之前最先出现前缀和后缀重合子串的后一位与文本串不匹配处进行比较（最先保证不漏掉更早匹配到的情况，因为模式串不匹配时会一直向后移动）

next[j]表示模式串中第j个字符发生不匹配时，应从next[j]处的字符开始重新与文本串比较。

void getNext(string s, int next[]) {
    int i = 0, j = -1;
    next[0] = -1;//next[0]（字符串以0开头）初始化为-1，是为了在KMP匹配时，模式串首位与文本串 i 处不匹配时，作j =  next[j] 操作，此后由j == -1或text[i] == pattern[j] 就 i++，j++，这样i刚好为不匹配出的下一位，j刚好为0，再继续匹配。
    while(i < s.size()) {
        if(j == -1 || s[i] == s[j]) {
            ++i;
            ++j;
            next[i] = j;
        }
        else
            j = next[j];
    }
}
//优化版
void getNextval(string s, int nextval[]) {
    int i = 0, j = -1;
    while(i < s.size()) {
        if(i = -1 || s[i] == s[j]) {
            ++i;
            ++j;
            if(s[i] != s[j])
                nextval[i] = j;
            else
                nextval[i] = nextval[j];
        }
        else
            j = nextval[j];
    }
}

位操作

  • x<<1|1 == x*2+1 数组存树时节点的右孩子下标 ->拓展：x<<2|1,2,3 == x*4+1,2,3
  • x = (x<<1)+(x<<3)+(ch^48) == x= x*10 + ch – ‘0’
  • x&1 == 0 ? x为偶数：x为奇数
  • x ^= 1 翻转最低位
  • x ^ （-1） == ~x  对x所有位取反，效果-x-1
  • x^x == 0
  • (x^(x+1))>>1 取出右边连续的1

文件操作

  •  Clion做freopen操作的文件是在cmake-building-debug文件夹下，我们可以将该文件夹下的操作文件如“in.txt”“out.txt”发送快捷方式到桌面或者直接将文件名设为绝对位置，这样就可以愉快的debug啦！
#include<cstdio>
int main() {
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
/*中间原样写代码，什么都不用修改*/
    fclose(stdin);
    fclose(stdout);
}
"in.txt"可改为"C:\\Users\\Administrator\\Desktop\\abc.txt"表示windows下绝对位置

线段树

入门：

https://www.cnblogs.com/hualian/p/13045680.html

规范：数组小标以1为起始，线段树数组tree[N],初始区间数组s[n]

  1. 开4倍空间证明(N = 4 * n)：

  • 证明角度：从初始区间长度n即最终线段树叶节点个数 n_{0}， n_{0}与节点总数关系来证明。
  • 区间长度为n（即1—n），为线段树叶子结点数
  • 线段树的任一结点度仅为0或者2，且n_{0} = n_{2} + 1 ，  n_{2} = n_{0} - 1
  • 总结点数m =  n_{0} + n_{2} = (2 * n_{0}) - 1
  • 我们将区间长度n的数值拆开为n = 2^{x}+k ,(k = 1, 2, 3..., 2^{x}，且n就是 n_{0})来讨论。 如 n = 16 = 8 + 8，n = 9 = 8 + 1, n = 12 = 8 + 4
  • 虽然一旦n给出，k就是确定的值，但n经数值拆分，x确定后，k = 1, 2, 3..., 2^{x}时对线段树空间的要求都是一样的
  • 则线段树的总结点数在k = 1时，m = (2 * n) - 1 = 2^{x+1} - 1,  k = 2^{x}时，m = [2 * (2^{x} + 2^{x})]  - 1 = 2^{x+2} - 1
  • 我们对于任一区间长度n,需保证我们可以安全的访问到线段树数组中任一下标的元素且又不开出过多数组空间（试想极端情况：叶子结点全在最后两层时，有个叶结点在最右下角位置，但由于开的空间不够，导致访问该叶节点时数组越界），所以至少开一个完整满二叉树的空间，n拆开后k不管取1~ 2^{x}中的哪个值，开出的空间N总能放下叶节点数为n的线段树
  • 所以我们保守的对于任一n都当做k为1的情况，开出能容纳下k为2^{x}时的值，这样就算k为2^{x}，开出的数组空间也刚好能放下整个线段树，所以我们要找出一个系数t，使N = t*n时，就无论k = 1，还是k = 2^{x}，都有 N >= m
  • k = 1时  n = 2^{x} + 1, m =  2^{x+1} - 1, 开出k =  2^{x} 时的总结点数 m = 2^{x+2} - 1 = ( 2^{x} +1) * 4 - 5 = 4*n - 5 = N,所以 t = 4, N 一般直接取 4*n 即可。
  • 小故事：对于每一个学生，老师只有发给你100分值的卷子你才有机会考到100分，但是给的卷子分值不足100就永远考不到100分。（我要考一百浑！

manacher算法

  1. 作预处理后字符串恒为奇数的证明：
  • 若Len_s = 2n, (len_s-1+2) + len_s = 4n+1; 
  • len_s-1为字符串间的间隙数;+2为整个字符串两端外各有一个空;
  • len_s为字符串原长; 预处理后整个字符串长度为4n+1;
  • 下同；
  • 若len_s = 2n+1, (len_s-1+2) + len_s = 4n+3
  • 预处理后4n+1与4n+3均为奇数;

图类题目

有向图还是无向图，注意初始化问题；

对二维数组初始化fill(G[0], G[0]+MAXV*MAXV, INF);拓-> memset(a, 0, sizeof(int));是以字节为单位初始化的；

Pre[]记录最短路径中某点前驱的矩阵，由递归的需要，得初始化为自身；

模板

         快读：

inline int read(){
    char ch = getchar();
    int x = 0, f = 1;
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = (x<<1)+(x<<3)+(ch^48);
        ch = getchar();
    }
    return x*f;
}

        快写：

//version 1
inline void write(int x){
    char nums[200];
    int len = 0;
    if(x < 0){
        putchar('-');
        x = -x;
    }
    while(x){
        nums[len++] = x%10|48;
        x /= 10;
    }
    while(len>=0)
        putchar(nums[--len]);
}
//version 2
inline void write(long long x){
    if(x >= 10)//主函数处处理负号
        write(x/10);//与version3相比更精炼
    putchar(x%10|48);
}
//version 3
void write(long long x) {
    if(x == 0)
        return;
    write(x/10);
    putchar(x%10|48);
}

数学

  • 0是任何数的倍数
  • 同余定理：(a+b)mod n = ((a mod n)+(b mod n)) mod n , ((a-b) mod n = ((a mod n) - (b mod n)) mod n , ab mod n = ((a mod n) (b mod n) mod n
  • (a - b)mod n = 0 -> a mod n = b mod n , 亦是同余a ≡ b(mod n)的定义。