gcd、lcm实现
- gcd又叫做欧几里德算法，求最大公约式，记住以下迭代式即可：
gcd(a,b) = gcd(b,a mod b)
- lcm基于gcd实现求最小公倍数
lcm(a, b) = (a * b) / gcd(a, b)
牛顿迭代法
用于求方程近似根，以leetcode：实现sqrt() 为例进行应用
牛顿迭代法的迭代公式如下：
公式得来牛顿迭代法的迭代公式基于泰勒级数展开和切线的概念而来。其基本思想是利用函数在某点的切线来逼近函数的零点，然后通过迭代不断靠近真实的零点。 证明：考虑一个函数在点 
处的泰勒级数展开： 
在该级数中，我们希望找到 ( x ) 的值，使得 ( f(x) ) 等于零。由于我们希望在 ( x_n ) 处找到零点，可以将上述等式简化为： 
然后解出 
得到：
这就是牛顿迭代法的迭代公式。它告诉我们，从当前的近似解 出发，可以通过用当前的函数值
除以当前的导数值
来得到一个新的近似解 
。通过不断迭代，我们可以逐渐逼近真实的零点，从而得到方程 
的解。 总结来说，牛顿迭代法的迭代公式是通过近似线性化函数，利用切线来逼近零点，然后通过迭代逐步靠近真实解的方法得到的。这个方法在实际应用中可以高效地求解非线性方程的近似根。 定义 y=x^_2−_C, y`=2x 代入：
由于y=f（x）有
和
两个根，为了让其在成功收敛到正根，xn初值必须大于0，这里可以感受到0~
, 因此为了方便我们把初始值设置得尽量靠近根的右侧，也就是xn=C
double C = x, x0 = C;
while (true) {
double x1 = 0.5 * (x0 + C / x0);
if (fabs(x0 - x1) < 1e-7) // fabs= float abs
break; //两次近似根差值足够小了，OK认为找到了
x0 = x1;
}
return int(x0);
概率
暂时只遇到了概率处理题 流程： 1.平方放大固定写法
int rand49(){
return rand7() + 7*(rand7()-1);
//前面是base：[1-7] + (0..6)*[1-7]
}
2.舍弃重试+分组
int rand10() {
while((n=rand49()-1) && n>=40);
//分组映射分10组，[0..3] [4..7] ... [36..39]
return n/4 + 1;
}
位运算
清除二进制最低位1：n&=(n-1); 位翻转：n^1
排列组合
- 路径数量(leetcode) 最基本的组合数：m+n个位置上，选择出m或者n个多少种位置
- 路径数量Plus (假如m>=n，n相关的移动不能连续，必须间隔m)
- 即隔板法，以量少n为基准摆好，用m插入到n+1个隔间空间中，