【Fifty Project - D21】

今日完成记录

Time	Plan	完成情况
9：00 - 10：00	爬楼梯	√
12：00 - 14：00	Leetcode	√
14：00 - 15：00	《挪威的森林》	√

Leetcode

每日一题

今天的每日一题是个easy：给定一个数组，要求统计其中数位为偶数的数的数量。数字范围在0-1e5 我就直接写了个遍历加if判断了。

hard我唯唯诺诺，easy我重拳出击！
每日一题居然这么快就不滑动窗口了？

树上倍增算法

上周周赛当时说要补的题结果转头就忘光光了，昨天重新去看了题目，发现自己的思路还是太暴力了，看了0x3f的题解发现原来要用树上倍增，今天就来重新复习一下树上倍增算法吧

树上倍增算法是一种典型的空间换时间算法，通过记忆更多的祖先以实现快速查找第k个祖先，也是一个典型的充分利用二进制思想的算法。
具体来说，给定一棵n个节点的树，对于任意节点记忆最多指定的$2^m$个祖先，其中$2^m>=n$,也就是m = 32 - Integer.numberOfLeadingZeros(n)，用pa数组记录，pa是一个n * m的数组，其中pa[i][j]表示节点i的第$2^j$个祖先，便可以通过特定的方法实现O(logn)复杂度查询任意节点的第k个祖先。

接下来我们说一下为什么要这么构造pa，以及如何利用pa查询任意祖先。

如下图是一个15个节点的满二叉树，根据上面的定义得到pa数组是一个15*4的数组

该算法的目的是通过每个节点记录m个祖先实现O(logn)查询任意节点的任意祖先。

先不考虑如何实现O(logn)的问题，我们通过最暴力的做法从一般到特殊地去实现。最暴力的做法是每次向上跳一级，每次都找自己的父节点，然后k–直到k=0就找到了目标祖先，这种方法因为每次只跳一级，所以需要跳k次。那么想一想如果每次多跳几级，是不是可以少跳几次呢？假设每次跳2级（先不考虑复杂情况，也就是k为奇数，也不考虑怎么实现每次跳2级），那么实际上我们只需要跳k / 2次。至此我们发现了一点：目标是k，实际上每次可以跳任意次数，可以直接找爹，也可以找爷爷，当然如果你能实现也可以直接找祖先。也可以得到一个结论：记一次寻找祖先需要j次，那么$k=a_0+a_1+...+a_{j-1}$,其中$a_i$表示第i次跳的级数。

接下来我们需要想一想，怎么用一种通用的方法拆解这个k，以及如何记忆节点的这些祖先节点，首先我们不难发现如果希望得到k祖先的跳跃次数更少，那么相应的记忆的祖先就会更多，相反亦然。那么接下来我们从最暴力的方法开始，从两个极端开始考虑：时间最小和空间最小。
时间最小：每次都是O(1)查询到k祖先，也就是只跳一次，对于任意k都可以直接查询到，那只能是记忆每个节点的每个祖先，那么pa数组大小应该是n * n，并且构造这个数组也得花费n * n 时间。
空间最小：极端情况就是上面提到的暴力解法，pa只记录每个节点的父节点，那么大小是 n * 1，而每次查询只能逐级向上跳，也就是时间复杂度O(n)。

很明显上面两种极端思想都不是我们想要的，我们需要在时间和空间上有所折中。树上倍增算法就利用了二进制实现了对k的拆分以及pa数组的记忆。首先任意一个数可以很容易实现二进制拆分，如15 = 1 + 2 + 4 + 8. 然后pa数组记录每个节点的$2^i$的祖先，上面的满二叉树对应的pa数组如下表

node\pa	0	1	2	3
1	-1	-1	-1	-1
2	1	-1	-1	-1
3	1	-1	-1	-1
4	2	1	-1	-1
5	2	1	-1	-1
6	3	1	-1	-1
7	3	1	-1	-1
8	4	2	-1	-1
9	4	2	-1	-1
10	5	2	-1	-1
11	5	2	-1	-1
12	6	3	-1	-1
13	6	3	-1	-1
14	7	3	-1	-1
15	7	3	-1	-1

说完树上倍增是如何实现k的拆分以及pa数组的构造，接下来说一下如何利用二进制和pa进行k数组的查询，如上例子，我们查询节点10的第三个祖先，根据二进制拆分k = 1 + 2，那么接下来只需要从节点10向上跳两次，一次跳1个祖先一次跳2个祖先。pa存储的便是每个节点的2的整数幂个祖先，所以从pa可以直接取到节点10的$2^0$祖先即pa[10][0] = 5，接下来找节点5的$2^1$祖先即pa[5][1] = 1，得节点10的第三个祖先是1.

代码实现pa数组的构造

private void buildPa(int[] p){int n = p.length;int m = 32 - Integer.numberOfLeadingZeros(n);this.pa = new int[n][m];for(int i = 0; i < n; i ++) pa[i][0] = p[i];for(int i = 1; i < m; i ++){// 这层循环逐步构造pa[j][i] 因为pa[j][0]已经初始化好了，就可以根据pa[j][0]构造pa[j][1],如此循环下去for(int j = 0; j < n; j ++ ){// 谨记摇摇车上唱的“爸爸的爸爸是爷爷”// pa[j][i]就是我们要找的爷爷，所以先看看爸爸是否存在 -1则不存在 存在的话就找一下爸爸的爸爸pa[j][i] = pa[j][i - 1] == -1 ? -1 : pa[pa[j][i - 1]][i - 1];}}
}

代码实现如何通过pa找到节点的k祖先

public int findKthAncestor(int node, int k){// 分解k 实际实现就是从他的二进制表示中最高位（非0）开始向低位遍历for(int i = 32 - Integer.numberOfLeadingZeros(k); i > 0 && node != -1; i --){if((k >> (i - 1) & 1) == 1) node = pa[node][i];}return node;
}

树上倍增算法拓展还可以用于两个节点u和v的最近公共祖先查询，首先利用一次dfs标记每个节点的深度并存储。查询u和v的最近公共祖先首先通过深度对比，统一二者的深度（更深的那个先跳到更浅节点的同一高度），此时有两种情况，一个是指向了同一个节点（浅者为两者最近公共祖先），另一个则是不同节点，那么此时两者共同向上跳，尽可能远地向上跳。
对于情况2，设i = log(n) 下取整，让u和v按照下面策略同时向上跳， 直到i为0：

• 如果pa[u][i] == -1 那么说明跳不了这么高，lca在下面，i–
• 如果pa[u][i] != -1, 如果pa[u][i] == pa[v][i]，那么说明lca在当前点或者在当前点的下面，令i–；如果pa[u][i] != pa[v][i] 说明lca在当前的上面，那么令u = pa[u][i], v = pa[v][i]，i–

重复上述操作直到i = 0，此时lca = pa[u][0]。也就是走到最后会停在lca的子节点处，这也正是为什么pa[u][i] == pa[v][i]时依然直接i-- 而不是赋值u和v到新的节点。
树上倍增算法板子题
针对图的路径存在性查询II：上周周赛要补的题，题干是给定长度为n的数组nums（无序），这是n个节点的权重，现规定如果两个节点权重的差值小于等于maxDiff则存在一条无向边，现给出q个询问，每次询问两个节点的最短路径长度，不通则返回-1.
思路：这个题从针对图的路径存在性查询I的思路过来，自然想到首先应该处理nums数组，带下标排序，使nums升序，这样可以用双指针很快处理出哪些节点存在边。题目的q数据规模是1e5，n也是1e5，所以每次查询应该是O(logn)，这里就需要结合树上倍增算法，通过双指针得到直接父节点，然后用树上倍增记忆每个节点的$2^i$祖先，然后用求lca的方法找到从孙节点到祖先节点的跳数，即为两点的最小路径长度。详细讲解请参考0x3f大佬的题解。

其中还学到了很好的带下标排序写法（之前都是写一个内部类存排序元素和下标再排序）

Integer[] idx = new Integer[n];
Arrays.setAll(idx, i -> i);
Arrays.sort(idx, (o1, o2) -> nums[o1] - nums[o2]);

《挪威的森林》

今天阅读了第四章，绿子出场了，好像也是一个过往很艰难的女孩，然后莫名其妙地两人就在一起了，emm算在一起吗，“我”还在等着直子新的回信… 复杂的剧情下“我”又和一个被绿了的女孩one night stand。很难评~