9.26 算法复习<0o0>

宇宙超级无敌霸王龙

2026-09-26 20:31:10

发布于：上海

7阅读

0回复

0点赞

算法：

结构体排序：

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

struct stu{
    string name;
    int score;
    int id;
};
bool cmp(stu a,stu b){
    if(a.score!=b.score) return a.score>b.score;
}

核心要点：
1、比较函数中，返回true表示第一个参数排在前面。
2、多关键排序：当第一关键字不等时，再比较第二关键字，以此类推。
3、用struct定义结构体，把相关数据组织在一起。

识别信号：
1、按x排序，若相同则按y排序
2、输出所有人的排名，第k名，前n名。
3、稳定排序需要用stable_sort

筛法

判断质数和批量求质数是两个不同的问题：
1、判断质数（试除法）：判断单个数n是否为质数，只要从2到√n遍历查看是否有n的因子即可。
2、批量求质数（埃式筛）：批量求1~n内的所有质数，从2开始，每找到一个质数就把它的所有倍数标记为合数，时间复杂度为O(n log log n)

埃式筛代码：

bool notP[10005];//notP[i]=1 表示不是质数
int primes[10005],cnt;
//把1到n的质数都存下来
void sieve(int n){
    notP[0]=notP[1]=1;
    for(int i=2;i<=n;i++){
        if(!notP[i]){
            primes[++cnt]=i;
            for(int j=2*i;j<=n;j+=i){
                notP[j]=1;
            }
        }
    }
}

枚举:

枚举三要素：
1、确定枚举对象：要枚举什么？（枚举答案、枚举分割点、枚举子集）
2、确定枚举范围：循环从哪开始到哪结束？
3、合法条件：什么样的枚举对象是题目要求的答案？

识别信号：
1、枚举算法的数据结构范围通常都不大（ $N \le1000$ )。
2、“所有方案”，“有都少种可能性”，“恰好满足”

贪心:

贪心算法的核心思想是每一步都做出当前最优的选择，希望局部最优能推导出当前最优。
1、排序后才能选择。
2、区间贪心（按开始时间，结束时间，时长排序）

二分查找和二分答案

二分查找：在有序数组中查找目标值，每次比较中间元素，将搜索范围缩小一半。时间复杂度O(logn)
二分答案：要求解最大值最小或最小值最大时，不直接求答案，而是二分猜答案，每次check当前猜测是否可行。

//找第一个大于等于x的位置
int l=1,r=n,ans=n+1;
while(l<=r){
    int mid=(l+r)/2;
    if(a[mid]>=x){
        ans=mid;
        r=mid-1；
    }
    else l=mid+1;
}

双指针

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

常见类型：
1、同向双指针（滑动窗口）：两个指针同向移动，维护一个窗口。用于“最长/最短连续子序列”问题。
2、相向双指针：一个从头、一个从尾向中间靠拢。用于有序数组上的查找。

识别信号：
1、暴力需要O( $n^2$ )的双重循环，且内层循环的起点随外层单调移动。

前缀和与差分

前缀和：预先处理出前缀和数组s[i]=s[i-1]+a[i]，之后任意[l,r]的和可以O(1)计算出s[r]-s[l-1]。
差分：前缀和的逆运算。构造差分数组d[i]=a[i]-a[i-1]，对区间[l,r]整体加减一个值，只需要修改两个端点就能修改整个区间d[l]+=v,d[r+1]-=v

识别信号：
1、要多次询问区间的和：前缀和预处理
2、要多次修改区间的值：差分