[TOC]
3.12 算法
选择
1）KMP match之前的比对次数
2）小根堆调整为大根堆堆最小交换次数
3）冒泡排序的交换次数
逆序对的个数
4）K-means决定K是多大
Elbow法拐点出现的地方
5）Hash线性探测法最终插入位置
6）小明有10颗草莓糖、10颗橘子糖，小红有10颗草莓糖，现在小明随机拿10颗糖给小红，之后小红随机打卡一颗糖，是橘子糖的概率是
1/4
多选
1）Batch norm
batchnorm可以帮助模型逃离鞍点
2）梯度下降法
参考1
- 批量梯度下降：在每次迭代时，用整个数据集的所有样本上的梯度计算更新。
- 随机梯度下降：在每次迭代时，用单个样本上的梯度计算更新。
- 小批量梯度下降：在每次迭代时，用多个但不是全部样本上的梯度计算更新。通常也简称为随机方法。
3）RF提高推理速度
减小树深度和树的数量
4）马尔可夫不等式、切比雪夫公式
5）可以用二分查找的序列
6）梯度提升树处理NaN的方法
可以用自带处理方法：
- XGBoost：为每个节点学习一个默认方向，当遇到缺失值时，数据将沿着这个方向移动。默认方向是在训练时确定的，以最小化损失函数。
- LightGBM：在寻找最佳分裂时，考虑将缺失值分到左子树或右子树，看哪种情况能获得更好的结果。通过这种方式，算法自动发现处理缺失值的最佳方法。
7）不能连续入栈3次的出栈序列
OJ
Q1
Alice 和 Bob 又在玩游戏了。
游戏的过程是：有两个正整数 x，y，Alice 和 Bob 轮流操作，Alice先手，每次当前操作的玩家将x，y 分别变为 x‘，y’ （x‘，y’ 也必须是正整数）
| 并需要满足：x+y=x‘+y’ 且｜x-y｜> | x’-y’ | (其中 ｜x｜表示x的绝对值。) |
如果轮到的玩家无法进行操作，则输掉游戏，小苯想知道如果两人都绝顶聪明，最终谁能获胜。
输入描述
输入包含T+1行。
第一行一个正整数T （1 ≤ T ≤ 10^4），表示测试数据的组数。
接下来 T 行，每行两个正整数x，y （1≤x,y ≤10^9），表示 x,y 初始的值。
输出描述
输出包含T行。
对于每个测试数据，如果Alice 会获胜，输出 Alice，否则输出 Bob.
示例 1
输入
2
3 4
5 7
输出
Bob
Alice
A1
解析：只要x，y相差小于等于1，无路可走，反之，一步可以让对方无路可走。所以就判断一下绝对差是否大于1即可。
t = int(input())
for i in range(t):
a,b = map(int,input().split())
if abs(a-b)>1:
print("Alice")
else:
print("Bob")
Q2
小苯刚刚和怪兽经历了一场恶战，现在血量见底，他面前有n瓶恢复药剂，每瓶药剂都可以为小苯恢复血量，但可能会有副作用，由一对整数（x, y）描述。
假设小苯使用了一些药剂，则所有使用的药剂中副作用最强的那一瓶会发挥其副作用。
具体的，如果小苯选择使用了第 P1，P2，P3 · · · Pk 个药剂，则他的血量会增加： \(\Sigma^k_{i=1}Х_{р_і} - \ max(У_{p_1}, У_{p_2},..., У_{p_k}).\) 现在小苯想知道，他以最优方式选择药剂使用（也可以不选），最多可以恢复多少血量，请你帮帮他吧。
输入描述
输入包含n+1行。
第一行一个正整数n（1 ≤ n ≤ 10^9），表示小苯可以选择的药剂个数。
接下来n行，每行两个正整数 x,y （1≤x,y ≤10^9），表示每瓶药剂。
输出描述
输出包含一行一个整数表示答案。
示例 1
输入
5
1 2
3 4
3 2
5 4
4 1
输出
12
A2
解析：本题有一个最优子结构，即，对poison度进行升序排序之后，若我们取index=i处的药水，那么必取i之前的所有药水。所以排序之后一遍过。
n = int(input())
l = []
for i in range(n):
i,j = map(int,input().split())
l.append((i,j))
res = 0
l.sort(key=lambda x:x[1])
poi = 0
pre = 0
for a in l:
pre+=a[0]
poi=a[1]
res = max(res,pre-poi)
print(res)
Q3
小苯有一个疑问，如果一个宿舍有n个人，编号从1到n，且有些人之间是好朋友，必须同时在一个群或不在一个群。在这样的情况下，宿舍最多能建几个不同的群聊（答案对1000000007取模）。
注：
- 小苯认为一个人不能建群，也就是说群聊人数必须大于 1。
- 定义两个群聊不同，当且仅当存在至少一个人，此人在其中一个群聊而不在另一个群聊。
输入描述
输入包含 m+1行。
第一行两个正整数n，m（1≤n,m ≤2×10^5），分别表示宿舍的人数和好朋友关系数量。
接下来 m 行，每行两个正整数 u，v（1≤u,v ≤n）且 （u不等于v），代表u，v两人是一对好朋友，必须同时在一个群聊里或同时不在一个群聊里。
示例1
输入
5 2
1 2
2 3
输出
5
A3
解析：利用并查集计算联通域的个数为res，并统计单节点联通域个数为single，那么根据集合计算可以得到结果为2^res-1-single，有两个注意点，一个要取模，第二个是用快速幂。
n,m = map(int,input().split())
fa = [_ for _ in range(n)]
c = [1]*n
def find(x):
t = x
while fa[t]!=t:
t=fa[t]
fa[x]=t
return t
def union(x,y):
xf,yf = fa[x],fa[y]
if xf!=yf:
if c[xf]<c[yf]:
fa[xf]=yf
c[yf]+=c[xf]
else:
fa[yf]=xf
c[xf]+=c[yf]
for i in range(m):
i,j = map(int,input().split())
if find(i-1)!=find(j-1):
union(i-1,j-1)
s = set()
res = 0
single = 0
mod = 10**9+7
for i in range(n):
if find(i) not in s:
res+=1
s.add(fa[i])
if fa[i]==i and c[i]==1:
single+=1
print((pow(2,res,mod)-1-single)%mod)
Reference
-
批量梯度下降，随机梯度下降和小批量梯度下降的区别. https://blog.csdn.net/Strive_For_Future/article/details/108104227 ↩
