首先声明！！！

  • 1、此知识点为课堂总结内容；
  • 2、如有使用或转载请注明出处；
  • 3、如有不足，欢迎批评指正；

* 基础算法 + 数据结构大纲：

一、基础算法：

  • 1、前缀和（一维、二维）；
  • 2、差分（一维、二维）；
  • 3、二分（整数二分、小数二分）；
  • 4、双指针（头双、头尾、分开）；
  • 5、高精度算法（用的比较少）；
  • 6、贪心思想；

二、数据结构：

  • 1、链表（数组实现、map实现）；
  • 2、栈、队列（单调栈、单调队列）
  • 3、树（存储、堆、递归、并查集）
  • 4、图（存储）

三、搜索 + 图论；

  • 1、dfs搜索；
  • 2、bfs搜索（连通块）；
  • 3、拓扑排序；
  • 4、最短路：单源最短路（dijkstra、spfa）、多源最短路（Floyd）；
  • 5、最小生成树（kluskaer）；

四、数论：

  • 1、gcd、lcm；
  • 2、判断质数、分解质因数；
  • 3、筛质数（埃氏筛法、线性筛）；
  • 4、欧拉定理（欧拉函数）；
  • 5、逆元、取模；
  • 6、组合数；
  • 7、博弈论；

五、动态规划（DP）：

  • 1、背包（0/1，完全背包、多重背包）；
  • 2、最短（上升|下降）子序列；
  • 3、线性dp（一维、二维）；
  • 4、区间dp；
  • 5、状态压缩dp；
  • 6、树形dp；

* 这些都只是基础算法 + 数据结构（之后有中级、高级）

基础算法篇：

一、前缀和：

1、作用：q次查询的求区间和（O（1））；

  • 预处理出s[i]数组；
  • 查询只用s[r]-s[l-1]；
  • 注意：下标从1开始；

2、缺点（局限性）：

  • 只做查询，不能修改；
  • 查询的区间必须是连续的；

3、常见的有一维前缀和、二维前缀和：

一维前缀和C++代码模板：

1
2
3
4
5
6
7
8
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) s[i]=a[i]+s[i-1];   // 预处理出前缀和数组
while(m--){
    int l,r;
    cin>>l>>r;
    cout<<s[r]-s[l-1]<<'\n';     // O(1)复杂度查询区间和
}

二维前缀和C++代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cin>>n>>m>>q;
for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
        cin>>a[i][j];
    }
}
for(int i=1;i<=n;i++){            // 预处理出二维前缀和数组
    for(int j=1;j<=m;j++){
        s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    }
}
while(q--){
    int x1,x2,y1,y2;
    cin>>x1>>y1>>x2>>y2;         // O(1)复杂度查询二维区间和
    cout<<s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1]<<endl;
}

二、差分（前缀和的逆运算）：

1、作用：q次修改区间加上或减去固定的值（O（1））；

  • 预处理出c[i]数组；
  • 查询只用修改c数组；
  • 最后还原原数组；
  • 注意：下标从1开始；

2、缺点：

  • 修改的值是固定的（加|减）；
  • 修改的区间必须是连续的；

3、常见的有一维差分、二维差分：

一维差分C++代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++) c[i]=a[i]-a[i-1];  // 预处理出差分数组

while(m--){
    int l,r,s;
    cin>>l>>r>>s;
    c[l]+=s,c[r+1]-=s;        // 对差分数组进行修改
}

for(int i=1;i<=n;i++) a[i]=a[i-1]+c[i];  // 还原原数组
for(int i=1;i<=n;i++) cout<<a[i]<<' ';   
cout<<'\n';

二维差分C++代码模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
cin>>n>>m>>q;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j];		
for(int i=1;i<=n;i++){        // 预处理出二维差分数组
    for(int j=1;j<=m;j++){
        b[i][j]=a[i][j]-a[i-1][j]-a[i][j-1]+a[i-1][j-1];
    }
}

while(q--){
    int x1,y1,x2,y2,c;
    cin>>x1>>y1>>x2>>y2>>c;
    b[x1][y1]+=c;            // 对二维差分数组进行修改
    b[x1][y2+1]-=c;
    b[x2+1][y1]-=c;
    b[x2+1][y2+1]+=c;
}

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){     // 还原原数组并输出
        a[i][j]=a[i-1][j]+a[i][j-1]-a[i-1][j-1]+b[i][j];
        cout<<a[i][j]<<' ';
    }
    cout<<endl;
}

三、二分（号称最难的算法）：

1、整数二分：

  • 边界问题（记模板）；
  • 符合和不符合的区间查找；

2、小数二分：

  • 没有边界问题，只需要设置查找精度；
  • 符合和不符合的区间查找；

3、二分答案：

  • 最大最小 | 最小最大问题
  • 条件限制问题

C++代码模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//整数二分:
//找左边界
int l=1,r=2e9,x;
while(l<r){      //如果(l+r)/2; 则r=mid,l=mid+1;
    int mid=(l+r)/2;
    if(a[mid]<=x) l=mid+1; 
    else r=mid;
}
//找右边界
while(l<r){      //如果(l+r+1)/2; 则r=mid-1,l=mid;
    int mid=(l+r+1)/2;
    if(a[mid]<=x)  l=mid;  
    else r=mid-1;
}

// 小数二分:
double l=-10000,r=10000,eps=1e-8;
while(r-l>eps){
    double mid=(l+r)/2;
    if(mid*mid*mid<=n) l=mid;
    else r=mid;
}