算法总复习

? ! 白白！？

2026-09-26 11:58:12

发布于：上海

7阅读

0回复

0点赞

算法总复习

结构体排序

概念

当一个对象有多个属性（如学生：姓名，成绩，学号，性别）时，我们用结构体把他们打包在一起。排序的时候需要自定义比较规则，告诉sort函数**"谁排前面"**。

核心要点

用struct定义定义结构体，把相关数组织组织在一起。
在比较函数cmp时，返回true
$时表示第一个参数在前面。

  struct stu{
      int id;//学号
      int score;//成绩
  }
  //先按成绩降序排序，再按学号升序排序
  bool cmp(stu a,stu b){
      if(a.score ! b.score) return a.score > b.score;
      else return a.id < b.id;
  }

多关键字排序：先比较主关键字，主关键字相同时，比较次关键字。

识别信号

"按X排序，若相同则按Y排序"：多关键字排序问题。
"输出排名"，"第k名"，"前m名"：先排序再取数据。

筛法

概念

判断质数和批量求质数是完全不同的两个问题。

判断质数（试除法：枚举`2~n-1`，看看是否`n`的因子）

bool is_prime(int n){
    if(n < 2) return 0;
    for(int i = 2;i * i <= n;i++){
        if(n % 1 == 0) return false;
    }
    return true;
}

批量求质数（埃氏筛）(选修)

bool notP[100005];//notP 为true时，表示不是质数
int primes[100005],cnt;//储存质数
void sieve(int n){
    notP[0] = notP[1] = 1;
    for(int i = 2;i <= n;i++){
        if(!notP)){
            primes[++cnt] = i;
            for(int j = 2 * 1;j <= n;j += i){\
                `notP[j] = 1;
            }
        }
    }
}

枚举

枚举三要素

-确定枚举对象：枚举什么?（枚举答案，枚举分割点，枚举子集）

确定枚举范围：循环的范围是从哪到哪。
枚举条件：什么样的枚举对象是我需要的。

贪心

概念

贪心算法的核心思想是每一步都做出当前最优的选择，希望局部最有能推导出全局最优

常见贪心策略

-排序后贪心（按照某种规则排序后顺序处理）
-选择当前可选中最大/最小的

区间贪心（按照开始/结束/时长排序“

二分查找与二分答案

二分查找概念

在有序数组中查找目标值，每次比较中间元素，将搜索范围缩小一半。

二分答案概念

当答案具有单调性时（即答案 $>= x$ 可行，但 $< x$ 不可行），不直接求答案，而是二分猜答案，每次check答案是否可行。

双指针

概念

双指针是一种用两个变量（代替指针）在数组或序列上同时移动来解决问题的技巧，核心是避免不必要的重复计算。

常见类型

同向双指针(滑动窗口)：两个指针同向移动。维护一个窗口。用户最长/最短连续子序列问题。
相向双指针(碰撞双指针)：一个从头，一个从尾向中间靠拢。用于有限数组上的查找。

前缀和与差分

前缀和概念

预处理数组前缀和s[i] = s[i - 1]+a[i]，之后任意区间 $[l,r]$ 的和可以 $O(i)$ 算出：s[r]-s[l - 1]

差分概念

前缀和的逆运算。构造差分数组d[i] = a[i] - a[i - 1] ,对区间 $[l,r]$ 在 $O(1)$ 进行修改，只需要修改两个节点：d[l] +=v,d[r + 1]-=v。最后对差分数组求前缀和还原。

STL数据结构

容器	特点	用途
$stack$	后进先出	括号匹配、表达式求值
$queue$	先进先出	BFS
$map$	键值对，按键有序	计数，离散化
$set$	有序不重复集合	去重，查找