编程竞赛必备算法精解
枚举
例题
字符计数
反倍数
洁净数
扫雷
模拟
例题
饮料换购
图像模糊
螺旋矩阵
回文日期
长草
注意：该参考代码仅通过80%，仅作学习模拟的参考
最大距离
进制转换
例题
前缀和
一维前缀和
前缀和:对于一个长度为n的列表a,前缀和为:
sum[i]= a[0]+a[1]+…+a[i]
例如:a= [1,3,4,2,5],前缀和数组sum=[1,4,8,10,15]
前缀和的性质:
Sum[i]=Sum[i-1]+a[i]
a[l] +…+a[r]= Sum[r]-Sum[l-1]
第一条性质用于处理出前缀和
第二条性质可以在O(1)的时间内求出区间和
前缀和实现一：
实现二
例题
区间次方和
代码如下：
小郑的蓝桥平衡串
代码如下：
二维前缀和
前缀和:对于N*M的二维列表a(下标统一从1开始),前缀和为:
例题
统计子矩阵
注：以下参考代码仅通过70%数据，仅作学习二维前缀和参考
差分
一维差分数组
对于一个数组a[], 差分数组diff[]的定义是: diff[i] = a[i] - a[i -1]
对差分数组做前缀和可以还原为原数组:
diff[1]+diff[2]+diff[3]+ ... +diff[i]
=a[1]+(a[2]-a[1])+(a[3]-a[2])+ ... +(a[i]-a[i-1])
= a[i]
例题
代码如下：
二维差分数组
离散化
离散化: 不关注数字本身,只关注大小关系时,利用排名代替原数据。
本质: 一种哈希,将离散的数字、浮点数,转换成1-n
例如:【100,200,300,400,500】,离散化后为【1,2,3,4,5】
所有仅关注偏序关系的题目,均可以先离散化
数组a的离散化步骤:
1、把a拷贝一份设置为b
2、对b排序、去重
3、把a中每个元素设置为b数组中的下标(二分查找)
法一：使用二分查找
注：
法二：使用字典
贪心
例题
谈判
糖果混合
代码如下
纪念品分组
代码如下：
翻硬币
代码如下：
日志统计
代码：
字典使用
构造
例题
大衣的邻近和
代码如下：
二分
浮点二分
例：估计根二的值
二分答案
题目所求答案(一般为整数)具有单调性质,采用猜答案+二分
1、确定初始范围[left,right]
2、当left≤right时:
mid =(left+right)//2
check(mid):判断mid是否合法:(定义check函数,什么时候是合法,根据题目的单调定来确定)
如果合法:更新ans=mid
根据合法调整左右区间,调整策略为二选一:left=mid+1, right = mid -1
例题
分巧克力：
代码如下：
跳石头
代码如下：
肖恩的乘法表
代码如下：
双指针
反向扫描
例题
纪念品分组
回文判定
同向扫描
例题
美丽的区间
挑选子串
位运算
位运算技巧
1. 判断奇偶性:
直接判断二进制的第0位是否为1或者0
相当于直接判断x&1，结果是1就是奇数，结果是0就是偶数
2. 求出x二进制的第i位:
获取第0位:直接&1
先将第i位转成第0位 : 右移i位 (x>>i)&1
3. 将二进制的第i位设置为1:
对(1 << i)进行或运算：x | (1 << i)
4. 将二进制的第i位设置为0:
对~(1<<i)进行与运算：x & ( ~ (1 << i))
5. 判断是否为2的若干次方:
判断x&(x-1)是否等于0
因此2的若干次方二进制表示中只存在一个1,上述一定成立,并且上述成立时说明只有一个1
6. 获取x的最低位的 1：
Lowbit(x)= x&(-x)
例题
二进制中1的个数
区间或
思路：
假如列表为【1,3,2,4,5】
那么他们的二进制是001,011,010,100,101
合起来第0位【1,1,0,0,1】第1位【0,1,1,0,0】第2位【0,0,0,1,1】
那么假如你要想判断区间2~5，即3,2,4,5
则第0位【1,0,0,1】进行或运算，第1位是【1,1,0,0】,第2位是【0,0,1,1】，得出来就是111，即7
那么我们在这里用一种快一点的判断方法（前缀和），或运算是有1得1，那么我们是是不是只有识别这个区间和大于0即可说明该区间有1
我们把原来的（第三行）换算成前缀和：第0位【1,2,2,2,3】第1位【0,1,2,2,2】第2位【0,0,0,1,2】
然后我们要判断区间2~5，是不是只要判断前缀和第0位的第5个数减去第1个数（前缀和公式），即3-1=2，说明有两个1，那么就可以判断第0位是1（这里需要了解前缀和）
那么我们就可以做一个循环，观察数据，发现二进制最多位数应该是31，那么我们就从0判断到30
假设第i位，我们就观察第i位的区间是不是大于0，大于0则为1，然后用(1<<i)表示第i位为1，且转成十进制
最后累加得出结果
