2021年1月最后一周，国服依然并查集，美服依然随机出题，同时难度上米乐M6 M6米乐较之上周都有增加，另外国美两服罕见地在同一周出了相同的题：【最小体力消耗路径】

　　本周出了5道并查集，并查集的难度都设置在Medium以上，但因为套路感较强，并不至于难到无从下手

　　把每个小格子按对角线个小三角形，然后格子内与格子间做union，最后数一数有多少个连通分量

　　感觉没有那么Hard，优先union公共边（因为公共的相当于一个顶俩），然后再分别union爱丽丝和鲍勃的，加总三种类型的所有多余边数

　　把格子与格子之间想成一条有权重的边，按权重从小到大依次union，直到首尾在一个连通分量中，此时权重就是最小体力

　　题目有说格子是0到N×N-1的排列，所以可以从0开始依次union该格子与其四周数值更小的格子（更明可游通），每union一次便检查一次首尾是否连通，和上一题有异曲同工的地方

　　同样是利用并查集，将两个具有相似性的字符串union起来，最后数一数有多少连通分量，至于如何判断两字符串是否相似，完全可以出成另外一题了。。难度大概是Easy，这里就不赘述了

　　【下一个排列】分3步，第一步从右边开始找出递减数组的区间，第二步将该递减区间翻转成递增，第三步将第一步找到的递减区间的左边界的前一个数与该区间内第一个比它大的数调换位置（如果不存在前一个数，说明整个数组都是递减的，则做到第二步即可）

　　【二叉树的垂序遍历】对树做一次dfs遍历，把每个节点的值与其横纵坐标存入list，按先横坐标再纵坐标最后值的比较级排序，然后再按横坐标分类输出即可

　　【具有给定数值的最小字符串】题目有点绕，想明白了就发现该字符串是有固定的模式的，一段a后接某一个字母，再接一段z结束，所以可以分别求解z的数量，中间字母，M6 米乐和a的数量，从而拼凑出整个字符串

　　【数组的最小偏移量】因为如果元素是偶数的话，就只能向下走，所以一开始把每个数都提升成偶数（即提升到最大可能值），那么要想找到更优解，就只能对每个元素做向下砍半操作，更确切的说是对最大值砍半（因为操作别的数要么不改变偏差值要么扩大了差值），重复该操作直到最大值变成奇数为止，因为奇数无法再向下砍半了，在此过程中为了方便取到最大最小值，我们用TreeSet这类数据结构来维护

　　【连接连续二进制数字】数字的二进制表示长度是随着数字大小的增加而增加的，在每个2的次方时增加1位，另外记得用long来代替int计算，避免溢出

　　【寻找数组的中心索引】很多种做法，这里采用的是事先求得每个位置上的前缀和与后缀和，然后再从左遍历一遍，找到第一个前缀和等于后缀和的位置

　　【等价多米诺骨牌对的数量】同样也是多种做法，笨办法是保存每种骨牌（正反可看作一种）的数量，然后分别求组合数：n个里面取2个为一等价骨牌对，就是C（n，2），最后加总所有的组合数

　　【是否所有 1 都至少相隔 k 个元素】如题就按顺序判断和前一个1是否间隔k个元素就好，没有什么深意和技术