[Acwing] 算法基础课总结 一 基础算法

1.快速排序

1. 分成子问题
2. 递归处理子问题
3. 子问题的合并

2.归并排序

1. 将一个无序数组 一分为二

2. 将两个有序数组 合二为一

   虽然逆序对 可以 使用 归并排序求,但是大多数情况下我们都选择 树状数组

3.二分

1. 求 [ L , R ] [L,R] [L,R] 通过 m i d mid mid每次逼近
2. 求答案 , 每次二分 m i d mid mid 然后 c h e c k check check 对于处理小数二分的时候,我们需要引入 e p s eps eps来考虑精度

4. 高精度

1. 全是模板

5. 前缀和

一维前缀和

1. s u m [ i ] = s u m [ i − 1 ] + a [ i ] sum[i] =sum[i-1]+a[i] sum[i]=sum[i−1]+a[i]
2. s u m [ r ] − s u m [ l − 1 ] ( [ L , R ] ) sum[r] - sum[l-1] ([L,R]) sum[r]−sum[l−1]([L,R])

二维前缀和

1. s u m [ i ] [ j ] = s u m [ i − 1 ] [ j ] + s u m [ i ] [ j − 1 ] − s u m [ i − 1 ] [ j − 1 ] + a [ i ] [ j ] sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1]+a[i][j] sum[i][j]=sum[i−1][j]+sum[i][j−1]−sum[i−1][j−1]+a[i][j]
2. s u m [ x 2 ] [ y 2 ] − s u m [ x 1 − 1 ] [ y 2 ] − s u m [ x 2 ] [ y 1 − 1 ] + s u m [ x 1 − 1 ] [ y 1 − 1 ] sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1]+sum[x1-1][y1-1] sum[x2][y2]−sum[x1−1][y2]−sum[x2][y1−1]+sum[x1−1][y1−1] ( [ ( x 1 , y 1 ) − ( x 2 , y 2 ) ] ) ([(x1,y1)-(x2,y2)]) ([(x1,y1)−(x2,y2)])

6. 差分

一维差分

1. b [ i ] = a [ i ] − a [ i − 1 ] b[i] = a[i] - a[i-1] b[i]=a[i]−a[i−1]
2. b [ l ] + = c , b [ r + 1 ] − = c ( 给 [ L , R ] + c ) b[l]+=c,b[r+1]-=c(给[L,R]+c) b[l]+=c,b[r+1]−=c(给[L,R]+c)
3. b [ i ] = b [ i ] + b [ i − 1 ] ( 差 分 的 前 缀 和 即 原 数 组 变 化 之 后 的 数 组 ) b[i] = b[i]+b[i-1] (差分的前缀和 即原数组变化之后的数组) b[i]=b[i]+b[i−1](差分的前缀和即原数组变化之后的数组)

二维差分 : (可以拆分成多个一维)

7. 双指针

1. 最长连续不重复子序列 (子序列中的所有元素都不可以重复) 通过枚举左端点, 同时使用一个标记数组 , 对于每一次遍历,我们都考虑是否需要更新右端点,并且更新答案

for(int i=1,j=1;i