数学 - wenzhoullq/leetcode GitHub Wiki
容斥
哈希表维护最值
一般问你最值的话,而且不涉及多个比较的话,用map（不会用treeSet)的,只用维护最值即可,然后更新最值
题目
a+c*mod c是任意非负数
如果是一组的话,nums[i]%mod后结果相同
题目
辗转相除
数字特征是1e9,从尾到头考虑，然后一般用大的取小的数的余数,
while(满足条件,不含=){
小对大取余数辗转相除
}
if(不满足) return ;
return 是否满足;
题目
乘法原理
题目
gcd
int gcd(int a, int b){
return a%b==0?b:gcd(b,a%b);
}
题目
1819. 序列中不同最大公约数的数目 求子序列的最大公约数就是枚举公约数,然后看它是否构成这个子序列的最大公约数（如何判断为最大公约数？设公约数为a;b,c,d为代求的数,如果b/a 和 c/a 和d/a有非1的公约数的话,那么a不是b,c,d的最大公约数
其他
不好归类，先放置其他列表
题目
343. 整数拆分 每段取3时最大，剩余4的时候直接取4
856. 括号的分数 ()是1,其他的都是乘法结合律
1675. 数组的最小偏移量 奇数×2可以变成偶数，但是偶数可以变成奇数，因此所有奇数先×2
数论
题目
829. 连续整数求和 （等差公式）
绝对值
拆除绝对值的时候有±两种情况
题目
v[i],i,v[j],j,i<j
反方向遍历，取将v[i]和i并到一起
题目
坐标
帕累托解
一个坐标按降序排序，排序后比较另一个坐标是否大于这个坐标
题目
中位数
O(1)
两个优先队列,中位数下标为（len1+len2+1）/2
题目
聚拢最小
将数据聚拢的时候，以中位数为中枢聚拢最快；如果是环的话，还要破环成链
- 曼哈顿距离
找一个距离点到所有的距离最小，二维的话就排两次,以中位数为中心聚拢
- 聚集
类似于曼哈顿距离，但是一个位置只能占一个坑，因此需要进行再次处理，排序后再次每个数字-i
题目
- 曼哈顿距离
- 聚拢
[字节跳动七月模拟T4]
小W是一名教师，在某次授课时，它将教室中的m个座位围成了一个圈，并按顺时针顺序编号1~m，共有n个学生自由地选择了自己的位置，但是小W认为他们坐的过于分散了，于是小W决定让学生们能够调整自己的位置，使得他们的位置能够连续,同时，为了避免学生们的不满情绪，小W希望学生们的总移动距离能够最小(设当前座位编号为x，最终座位编号为y,则移动距离定义为min(ly-x,m-ly-x)。小W的数学并不好，所以希望你能帮助他求出这个最小总移动距离。
第一行输入两个正整数n,m(1<=n<=2x10^5, n<=m<=10^9)，分别代表学生数量和座位数量。
最小值
模板
Arrays.sort(nums);
for(;);//求sum
根据题意寻找target
分析
数学推理类出现关键词最小值，考虑数学分析，这个最小值，肯定和数组中的某个值相关，通过sum来求，并且一般都会进行排序
逻辑思维
最少反转次数 res=min（错排段数，2）
1015. 可被 K 整除的最小整数 以1结尾的不能被除数%5==0和除数%2==0的整除,注意对余数的处理
斜率
求三点的斜率，算出他们的长和高,分别为h1,h2,w1,w2 h1w2==h2w1的话说明斜率相等，如果用除法的话会出现精度问题
题目
计算面积
面积=area1-重合+area2;如果重合部分没有直接返回 area1+area2
题目
定理公式
最短非子序列
划分若干区间，区间内填满（HashSet）
题目
偏序集
非严格最长上升子序列的长度=非严格最短下降子序列的个数，反之同理
循环递归
递归到目标值退出，可以是Hash记录
质数
求质数最基本的是埃氏筛
题目
866. 回文素数 (当数据长度为8的时候不存在质数)
- 丑数 丑数的本质是用一个数轮询的去乘对应的数字集合，选取最小的数作为下一个丑数，在轮询相乘的时候会出现重复的数字，因此需要去重
264. 丑数 II多路复用埃氏筛
- 贝祖定理
gcd(a,b) = d ,则 ax+by==nd a,b,n是任意的整数